Архитектура параллельных вычислений

Occam

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

Sisal

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

ZPL

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

3.2 Технологии параллельного  программирования 

Введение  в технологию Open MP

      В технологии Open MP за основу берется последовательная программа. Для создания параллельной версии пользователю представляются наборы:

1) директив,

2) процедур,

3) переменных  окружения.

      Стандарт  Open MP разработан для языков Fortran и C (Fortran 77, 90, 95 и C, C++) и поддерживается производителями всех больших параллельных систем. Реализации стандарта доступны в UNIX и в среде Windows NT.

      Конструкции Open MP в различных языках мало отличаются, поэтому ограничимся языком Fortran.

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

Для поддержки  параллелизма используется схема

FORK/JOIN.

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

      В параллельной области все переменные в программе делятся на два  класса:

1) общие  (shared – разделяемые);

2) локальные  (private – собственные).

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

      Понятия областей программы и классов  переменных вместе с порождением (расщеплением) и уничтожением (соединением) нитей  определяют общую идею написания  программы с использованием технологии Open MP. Все директивы Open MP располагаются в комментариях и начинаются с одной из следующих комбинаций !$OMP, C$OMP или*$OMP (по правилам языка Fortran строки, начинающиеся с символов !,С или *, означают комментарии).

      Все переменные окружения и функции, реализующие стандарт Open MP, начинаются с префикса OMP_.

      Описание  параллельных областей: для такого описания используются две директивы

!$OMP PARALLEL

< параллельная  область программы >

!$OMP END PARALLEL

      Для выполнения фрагмента программы, расположенного между данными директивами, основная нить порождает нити в количестве OMP_NUM_THREADS-1, где OMP_NUM_THREADS переменная окружения, значение которой пользователь задаёт перед запуском программы. Все порожденные нити исполняют программу, находящуюся между указанными директивами.

      На  директиве !$OMP END PARALLEL происходит неявная синхронизация нитей: сначала все нити достигают директиву!$OMP END PARALLEL, и лишь после этого происходит слияние всех нитей в основную нить, которая и продолжает процесс.

      В параллельной области каждой имеющейся  нитью может быть порождена параллельная секция (порождение нитью параллельных нитей) и последующее их соединение (с сохранением главенства порождающей  нити). Число нитей в параллельной секции можно задавать с помощью  функции OMP_SET_NUM_THEADS, которая устанавливает значение переменной OMP_ NUM_THEADS(при этом значения переменной OMP_DYNAMIC должно быть установлено в 1 с помощью функции OMP_SET_DYNAMIC). Стратегию обработки вложенных секций можно менять с помощью функции OMP_SET_NESTED.

       Необходимость порождения нитей и параллельного  исполнения может определяться динамически  в ходе исполнения программы с  помощью условия IF:

       !$OMP PARALLEL IF (< условие >).

       Если < условие > не выполнено, то директива  не выполняется и программа обрабатывается в прежнем режиме.

       Распределение работы в Open MP можно проводить следующими способами:

       1) программировать на низком уровне;

       2) использовать директиву !$OMP DO для параллельного выполнения циклов;

       3) использовать директиву!$OMP SECTIONS для  параллельного выполнения независимых  фрагментов программы;

       4) применить директиву !$OMP SINGLE для однократного выполнения участка программы.

Возможности Open MP.

      1. Синхронизация. Для синхронизации  работы нитей в Open MP предусмотрено много возможностей; простейшая из них использование директивы !$OMP BARIER. Нити, дошедшие до этой директивы, останавливаются, поджидая остальные нити; после достижения этой директивы всеми нитями работа продолжается.

      2. Участок нити-мастера. Фрагмент  программы, который должна выполнить  лишь основная нить, определяется  директивами 

      !$OMP MASTER

            <участок программы  для нити-мастера>

      !$OMP END MASTER

Остальные нити пропускают этот участок программы; синхронизация по умолчанию здесь  не проводится.

      3. Последовательное выполнение отдельного оператора. Директива !$OMP ATOMIC относится к непосредственно идущему за ней оператору, и её применение приводит к последовательному выполнению этого оператора всеми нитями.  4. Гарантированное поддержание когерентности. Вычислительная система может иметь сложную иерархию различных областей памяти, когерентность которых поддерживается автоматически. Однако, в некоторых случаях пользователь должен иметь особые гарантии того, что память, к которой он обращается, своевременно обновлена (синхронизирована). Для этого служит

Директива !$OMP FLASH[список переменных]

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

Стандарт  MPI.Элементы идеологии стандарта MPI

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

      Основными понятиями MPI являются:

- процесс;

- группа  процессов;

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

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

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

      В структуре языков Фортран и Си стандарт MPI реализуется как библиотека процедур с вызовами определенного вида. Требуется, чтобы программа, написанная с использованием стандарта MPI, могла быть выполнена на любой параллельной системе без специальной настройки. Для применения MPI на параллельной системе к программе должна быть подключена библиотека процедур MPI. Перед использованием процедур стандарта MPI следует вызвать процедуру MPI_INIT; она подключает коммуникатор.

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

Перечень  основных процедур стандарта MPI.

      Исходной  нумерацией n процессов в группе являются числа . Для определения числа процессов в группе и номера данного процесса служат процедуры MPI_GROUP_SIZE(group,size) и MPI_GROUP_RANK(group,rank).

      Процедура MPI_GROUP_SIZE(group,size) присваивает параметру size значение, равное числу процессов группы с именем group.

      Процедура MPI_GROUP_RANK(group, rank) присваивает параметру rank значение, равное номеру процесса в группе с именем group.

      Однако  иногда такая нумерация является неудобной; поэтому есть возможность  изменять нумерацию в группе. В  частности, если необходимо использовать топологию n-мерных кубов (или торов), то используется процедура MPI_CART_CREATE; обращение  к ней имеет вид:

      MPI_CART_CREATE(comm_old, ndims, dims, periods,

                  reorder, comm_cart),

где

      comm_old- исходный коммутатор;

      ndims- размерность создаваемой решетки;

      dims- массив размерности ndims, задающий размер в каждом направлении;

      periods- массив размерности ndims, каждый элемент которого принимает значения FALSE или TRUE; если элемент имеет значение TRUE, то направление периодическое (это направление замыкается кольцевой связью) и FALSE в противном случае;

      reorder- параметр, принимающий значения FALSE или TRUE; нумерация будет сохранена в случае значения FALSE, или назначена другой - в случае значения TRUE;

      comm_cart- вновь созданный коммутатор с декартовой топологией.

      Основными процедурами для целей обмена двух процессов служат процедура  посылки сообщения MPI_SEND и процедура  приема сообщения MPI_RECV; обращения к  этим процедурам имеют вид

            MPI_SEND(buf0,count0,datatype0,dest,tag0,comm),

            MPI_RECV(buf1,count1,datatype1,source,tag1,comm,status),

где

      buf0, buf1 - начальные адреса передающего  и принимающегобуферов (соответственно);

      count0, count1 - числа элементов данных в  передающем и в принимающем буферах;

      datatype0, datatype1 - типы передаваемых и получаемых

данных;

      dest- номер принимающего процесса;

      source- номер посылающего процесса;

      tag- тэг сообщения (тэг служит для указания типа сообщения и может принимать целочисленные значения от 0 до натурального числа UB, значение которого зависит от реализации);

      comm- коммуникатор группы.