V(S);

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

enddo

end

parend

end

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

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. С этой точки все процессоры работают без простоя, пока они не достигнут последние четыре итерации цикла.

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

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

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

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

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

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

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

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

• Создать интерфейс прикладного программирования для МРР систем;

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

• Допускать удобное сопряжение с языками C, Fortran 77, Fortran 90 и C++;

• Простой способ создания процессов для модели SPMD (одна программа используется для обработки разных данных на разных процессорах);

Основные понятия языка

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

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

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

Имеются предопределенные коммуникаторы (точнее, создавае­мые при инициализации MPI-системы): * MPI_COMM_ALL - все процессы и операции над группами (локальные, без обмена сообщениями), например, Дай размер группы. MPI_GROUP_SIZE(IN group, OUT size) Дай номер в группе обратившегося процесса. MPI_GROUP_RANK(IN group, OUT rank)

Основные операции - send, receive

Операции могут быть блокирующими и неблокирующими.

В операции send задается:

• адрес буфера в памяти;

• количество посылаемых элементов;

• тип данных каждого элемента;

• номер процесса-адресата в его группе;

• тег сообщения;

• коммуникатор.

MPI_SEND(IN start, IN count, IN datatype, IN dest, IN tag, IN comm) Типы данных - свои в MPI, но имеется соответствие между ними и типами Fortran и С.

В операции receive задается:

• адрес буфера в памяти;

• количество принимаемых элементов;

• тип данных каждого элемента;

• номер процесса-отправителя в его группе;

• тег сообщения;

• коммуникатор;

• ссылка на объект-статус, содержащий необходимую инфор­мацию о состоянии и результате операции.

Имеется возможность указать "любой отправитель" и "любой тег".

Имеется три режима коммуникаций - стандартный, режим готовности и синхронный.

В стандартном режиме последовательность выдачи операций send и receive произвольна, операция send завершается тогда, когда сообщение изъято из буфера и он уже может использоваться процессом.

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

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

MPI относится к классу систем параллельного программирования, основанного на расширении стандартного последовательного языка описания процессов, библиотечными функциями для обмена сообщениями между процессами. В настоящее время MPI становится стандартом de facto и вытесняет ранние версии библиотечных расширений последовательных языков для параллельного программирования, например, таких как p4, PVM,Express и PARMACS. MPI - сложная система. Полностью она включает 129 функций, многие из которых имеют разнообразные параметры или варианты. Однако ключевая концепция MPI сосредоточена примерно в наборе из 20-25 функций, которые обеспечивают более чем адекватную поддержку для широкого спектра приложений.

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

В модели программирования MPI вычисление включает один или большее количество процессов (потоков команд), связь между которыми осуществляется сообщениями, инициируемыми вызовом библиотечных подпрограмм. В большинстве MPI реализациях набор процессов зафиксирован и создан на этапе инициализации программы по одному процессу на процессор. Однако эти процессы могут выполнять различные программы. Следовательно, модель программирования MPI относится к классу multiple program multiple data (MPMD) в отличие от SPMD модели (simple program multiple data), в которой все процессоры выполняет одну программу. Во многих реализациях MPI параллельных процессов может быть и больше, чем реальных процессоров в вычислительной системе, тогда в функции MPI входит и распределение процессов. Псевдопараллелизм обеспечивает операционная система.

Поскольку число процессов в MPI вычислениях обычно зафиксировано, центральными в идеологии MPI являются механизмы синхронизации и обмена данными между процессами. Операции связи между процессами можно подразделить на:

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

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

• MPI поддерживает асинхронную связь

Эффективность и надежность обеспечиваются:

• определением MPI операций не процедурно, а логически, т.е. внутренние механизмы выполнения операций скрыты от пользователя;

• использованием непрозрачных объектов в MPI (группы, коммуникаторы, типы и т.д.);

• хорошей реализацией функций передачи данных, адаптирующихся к структуре физической системы.

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

Переносимость обеспечивается:

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

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

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

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

• В пятых, компиляторами для Fortran(a) и C.

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

1. Средства описания и создания процессов в языке Фортран-GNS.

По семантике языка Fortran GNS все процессы программы получают уникальные имена - системные идентификаторы, по которым производится отождествление корреспондентов при обмене сообщениями между процессами и в терминах которых задается среда выполнения функций редукции. Эти имена вырабатываются функцией порождения процессов - встроенной функ­цией языка NEWTASK. Структура системного идентификатора определяется реализацией, это имя не имеет внешнего представления.

Для манипулирования именами процессов внутри программы в язык Fortran GNS вводится новый для Фортрана тип данных - тип TASKID. Зна­чения этого типа представляют собой имена процессов, которые вырабаты­ваются функцией порождения процессов.

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

Добавляется константа .NOTASKID., которая представляет собой "ну­левое" значение для объектов этого типа. Данные типа TASKID должны быть описаны в операторе TASKID, син­таксис которого аналогичен синтаксису операторов объявления типа в Фортране 77. Данные этого типа могут использоваться в операторах EQUI­VALENCE, но при этом могут быть эквивалентными только данным типа TASKID. Допускается использование TASKID в качестве описателя типа подп­рограммы-функции.