Ответы 190 страниц (1184228), страница 29

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 29)

Семафоры позволяют:

- синхронизировать работу процессов,

- управлять распределением ресурсом (использованием положительного диапазона значений семафора как счетчика ресурсов) ,

- организовывать очередь блокированных процессов (отрицательные значения семафора показывают число блокированных процессов).

В системах программирования вводится специальный тип данных, оп­ределяющий структуру семафора, например, SEMAPHOR,SIGNAL,GETA.

Использование семафоров

begin integer S; S:=1;

parbegin

task1: begin

do while (true)

P(S);

<критический участок 1>;

V(S);

<обычный участок>;

enddo

end;

task2: begin

do while (true)

P(S);

<критический участок 2>;

V(S);

<обычный участок>;

enddo

end

parend

end

Упорядоченные секции. Распараллелить цикл, используя упорядоченные секции и семафоры:

DO I=2,N

A(I) = 2*A(I) + C(I)

B(I) = C(I)*sin(X(I))

Y(I) = Y(I-1) + X(I)

D(I) = P(I)*B(I)/A(I)

ENDDO

Что-то на тему

Директива синхронизации OpenMP:

ORDERED ... END ORDERED //видиимо,это и есть упорядоченные секци… прим. А.Е.

Определяет блок внутри тела цикла, который должен выполняться в том порядке, в котором итерации идут в последовательном цикле. Может использоваться для упорядочения вывода от параллельных нитей.

Ограничения на использования Ordered

Может появляться только в динаических расширениях следующих деректив:

DO or PARALLEL DO (Fortran)

for or parallel for (C/C++)

В упорядоченную секцию допускается только одна нить в единицу времени.

Переходы на другие процессоры внутри Ordered-блока запрещены.

Итерация цикла не может исполнять одну и ту же Odered-директиву более 1 раза и должна не исполнять более 1 Ordered-директивы.

Цикл, имеющий внутри Ordered-директиву должен быть циклом, определенным как Ordered

DO I=2,N

A(I) = 2*A(I) + C(I)

B(I) = C(I)*sin(X(I))

Y(I) = Y(I-1) + X(I)

D(I) = P(I)*B(I)/A(I)

ENDDO

Иногда, почти полностью распараллеливающийся по данным, алгоритм имеет единственную зависимость данных, которая на векторных машинах может потребовать расщепления цикла, чтобы изолировать зависимость.

Например:

DO I = 1,N

A(I) = EXP(SIN(B(I))) * EXP(COS(B(I)))

C(I) = (D(I) + E(I)) / F(I) * A(I)

X(I) = S * X(I-1) + C(I)

Z(I) = X(I) * Y(I) + EXP(Z(I))

ENDDO

Оператор присваивания X(I) включает рекурсию, что запрещает векторизацию. Обычно либо компилятор, либо программист выделит этот оператор в отдельный скалярный цикл, чтобы позволить другим трем операторам присваивания выполняться в параллельном режиме.

Это не всегда необходимо делать при распараллеливании. Если имеется достаточно работы выше и/или ниже оператора присваивания X(I) и N достаточно велико, можно достичь эффективного параллельного выполнения цикла путем помещения оператора присваивания X(I) в упорядоченную критическую секцию. Она будет обеспечивать доступ только одной нити в один и тот же момент явным или неявным замковым (lock) механизмом. В данном случае требуется выполнять итерации в таком порядке, чтобы удовлетворить требования рекурсии для вычисления X.

Реальная система синхронизации для SEQ

CALL SETSEQ (SEQ,0)

* инициализация, установка SEQ=0

С$DIR DO_PARALLEL (ORDRED)

DO I = 1,N

A(I) = EXP(SIN(B(I))) * EXP(COS(B(I)))

C(I) = (D(I) + E(I)) / F(I) * A(I)

CALL WAITSEQ (SEQ,I-1)

* ждать, пока SEQ будет равно I-1

X(I) = S * X(I-1) + C(I)

CALL POSTSEQ (SEQ,I)

* установить SEQ в I

Z(I) = X(I) * Y(I) + EXP(Z(I))

ENDDO

Семантика (для случая четырех процессоров):

Инициализируются вычисления первых четырех итераций в заданном порядке на четырех параллельных процессорах. Все четыре процессора вычисляют свои A(I),C(I) одновременно. Первый процессор выполнит для I=1 присваивание X(1), в то время как другие ждут. Первый процессор для I=1 вычисляет Z(1), в то время как X(2) вычисляется вторым процессором для I=2. Первый процессор начинает вычислять новую итерацию для I=5, в то время как другие три процессора проходят сквозь критическую секцию также упорядочено.

Теперь, если работа по выполнению цикла хорошо сбалансирована, первый процессор для I=5 достигает точки WAITSEQ как раз тогда, когда четвертый процессор для I=4 закончит POSTSEQ. С этой точки все процессоры работают без простоя, пока они не достигнут последние четыре итерации цикла.

Системы передачи сообщений. Фортран-GNS.

Статический и динамический способы образования параллельных процессов.

"Процесс - группа ячеек памяти, содержимое которых меняется по определенным правилам. Эти правила описываются программой, которую ин­терпретирует процессор." /Цикритзис Д./.

Вычислительный процесс можно рассматривать как последовательность команд ЭВМ, которая работает с данными ей ресурсами. (Задача, задание, процесс, нить, TASK). Так, на микропроцессоре могут работать одновременно несколько независимых процессов: счет вычислительной задачи, редактирование текстов и т.д. Далее рассматриваются вычислительные процессы, одновременно выполняющиеся на нескольких процессорах для решения общей задачи. Работа такой задачи может начинаться с порождения главного процесса, который при работе может порождать другие процессы динамически. Эти процессы могут работать параллельно с главной и также порождать другие процессы.

Другим способом порождения процессов является статический способ, когда производится одновременная инициализация на всех процессорах одинаковых процессов (SPMD – Single Program Multiple Data). Эти процессы опрашивают состояние решающего поля и настраиваются на выполнение своей части вычислений.(Они могут узнать: сколько их порождено, свои уникальные, внутренние имена, и т.д.)

Процессы, работающие на равных правах (не вызовы процедур и не процессы, связанные понятиями "главная-подчиненная"), иногда называемые сопроцессами, могут выполняться параллельно и при этом общаться друг с другом - не часто (слабо связанные процессы).

Требования с системам программирования методом передачи сообщений.

Кое-что…

Основной моделью параллельного выполнения программы на кластере является модель передачи сообщений .

В этой модели параллельная программа представляет собой систему процессов, взаимодействующих посредством передачи сообщений .

Можно выбрать модель передачи сообщений и в качестве модели программирования. При этом возможны три способа построения языка программирования:

· Расширение стандартного языка последовательного программирования библиотечными функциями (например, Фортран+MPI);

· Расширение стандартного языка последовательного программирования специальными конструкциями (например, Fortran-GNS);

· Разработка нового языка (например, Occam).

Однако модель передачи сообщений является слишком низкоуровневой, непривычной и неудобной для программистов, разрабатывающих вычислительные программы. Она заставляет программиста иметь дело с параллельными процессами и низкоуровневыми примитивами передачи сообщений .

Поэтому вполне естественно, что прикладной программист хотел бы получить инструмент, автоматически преобразующий его последовательную программу в параллельную программу для кластера. К сожалению, такое автоматическое распараллеливание невозможно в силу следующих причин.

Во-первых, поскольку взаимодействие процессоров через коммуникационную систему требует значительного времени (латентность – время самого простого взаимодействия - велика по сравнению со временем выполнения одной машинной команды), то вычислительная работа должна распределяться между процессорами крупными порциями.

Совсем другая ситуация была на векторных машинах и на мультипроцессорах, где автоматическое распараллеливание программ на языке Фортран реально использовалось и давало хорошие результаты. Для автоматического распараллеливания на векторных машинах (векторизации) достаточно было проанализировать на предмет возможности параллельного выполнения (замены на векторные операции) только самые внутренние циклы программы. В случае мультипроцессоров приходилось уже анализировать объемлющие циклы для нахождения более крупных порций работы, распределяемых между процессорами.

Укрупнение распределяемых порций работы требует анализа более крупных фрагментов программы, обычно включающих в себя вызовы различных процедур. Это, в свою очередь, требует сложного межпроцедурного анализа. Поскольку в реальных программах на языке Фортран могут использоваться конструкции, статический анализ которых принципиально невозможен (например, косвенная индексация элементов массивов), то с увеличением порций распределяемой работы увеличивается вероятность того, что распараллеливатель откажется распараллеливать те конструкции, которые на самом деле допускают параллельное выполнение.

Во-вторых, в отличие от многопроцессорных ЭВМ с общей памятью, на системах с распределенной памятью необходимо произвести не только распределение вычислений, но и распределение данных, а также обеспечить на каждом процессоре доступ к удаленным данным - данным, расположенным на других процессорах. Для обеспечения эффективного доступа к удаленным данным требуется производить анализ индексных выражений не только внутри одного цикла, но и между разными циклами. К тому же, недостаточно просто обнаруживать факт наличия зависимости по данным, а требуется определить точно тот сегмент данных, который должен быть переслан с одного процессора на другой.

В третьих, распределение вычислений и данных должно быть произведено согласованно.

Несогласованность распределения вычислений и данных приведет, вероятнее всего, к тому, что параллельная программа будет выполняться гораздо медленнее последовательной. Если на системе с общей памятью распараллелить один цикл, занимающий 90 процентов времени решения задачи, то можно рассчитывать на почти десятикратное ускорение программы (даже если оставшиеся 10 процентов будут выполняться последовательно). На системе с распределенной памятью распараллеливание этого цикла без учета последовательной части может вызвать не ускорение, а замедление программы. Последовательная часть будет выполняться на одном процессоре или на всех процессорах. Если в этой части используются распределенные массивы, то для такого выполнения потребуется интенсивный обмен данными между процессорами.

Согласованное распределение вычислений и данных требует тщательного анализа всей программы, и любая неточность анализа может привести к катастрофическому замедлению выполнения программы.

Невозможность полностью автоматического распараллеливания имеющихся последовательных программ для их выполнения на кластерах, не означает, конечно, неактуальности работ в этом направлении. Если ввести некоторую дисциплину при написании программ, и, возможно, позволить вставлять в программу некоторые подсказки распараллеливателю, то такие программы могут автоматически преобразовываться в программы, способные выполняться параллельно на кластере. Однако в этом случае следует говорить скорее не о распараллеливании имеющихся последовательных программ, а о написании новых параллельных программ на традиционных языках последовательного программирования или их расширениях.

Система программирования MPI.

MPI является на данный момент самой развитой системой параллельного программирования с передачей сообщений. MPI позволяет создавать эффективные и надежные, переносимые параллельные программы высокого уровня. Эффективность и надежность обеспечиваются такими механизмами как: определение MPI операций не процедурно, а логически, т.е. внутренние механизмы выполнения операций скрыты от пользователя; использование непрозрачных объектов в MPI (группы, коммуникаторы, типы и т.д.);хорошей реализацией функций передачи данных, адаптирующихся к структуре системы и обеспечивающих необходимую буферизацию данных. Переносимость обеспечивается такими механизмами, как: определение одного вычислительного компьютера в виде виртуального компьютера и возможность задания произвольного количества таких виртуальных компьютеров в системе не зависимо от количества физических компьютеров (зависимость только от объема оперативной памяти в системе); компиляторы для соответствующих языков на компьютерах вычислительной системы. Уровень языка параллельного программирования определяется языковыми конструкциями, с помощью которых создаются параллельные программы. Чтобы более четко представить себе этот уровень нужно ответить на вопрос: - В чем одно из важных отличий в написании последовательной и параллельной программ? Здесь имеется ввиду параллельная программа для рассматриваемых MIMD систем. Прежде чем создавать параллельную программу, необходимо знать общую архитектуру (виртуальной) параллельной машины и топологию (виртуальных) межпроцессорных связей, которая существенно используется при программировании. Это связано с тем, что невозможно создание автоматического распараллеливателя, который позволял бы превращать последовательную программу в параллельную, и обеспечивал бы ее высокую производительность. Поэтому в программе приходится в явном виде задавать операторы инициации виртуальных топологий и операторы обменов данными между (виртуальными) процессорами. При написании же последовательной программы знать архитектуру процессора, на котором будет исполняться программа, зачастую нет необходимости, поскольку учет особенностей архитектуры скалярного процессора может быть сделан компилятором с приемлемыми потерями в производительности программы. Поэтому языковый уровень параллельной программы является заведомо ниже уровня последовательной программы, т.к. пользователю нужно в явном виде увязывать структуру алгоритма своей задачи со структурой вычислительной системы. Таким образом языковый уровень рассматривается в рамках уровней параллельных конструкций, для создания параллельных программ. Для решения своей задачи, пользователь с помощью команды (в командной строке): mpirun […] -np N, задает вычислительную систему из N виртуальных компьютеров, соединенных между собой виртуальными каналами с топологией связи - "полный граф". В дополнение к этому, наличие операторов парных взаимодействий между процессорами в такой среде, достаточно для реализации всего спектра используемых в программах схем системных взаимодействий. Но отображение структуры задачи на архитектуру системы с помощью таких операторов требует некоторых усилий при программировании. Параллельная программа в этом случае будет громоздкой, плохо отлаживаемой, с неэффективным отображением структуры алгоритма на структуру системы. Наличие в системе таких средств как: виртуальные топологии, коллективные взаимодействия, создаваемые пользователем типы данных и др., значительно повышают уровень параллельного программирования. Виртуальные топологии обеспечивают оптимальное приближение архитектуры системы к структурам задач при хорошей переносимости задач.

Главные цели создания системы параллельного программирования:

Характеристики

Список файлов ответов (шпаргалок)