31 Вопрос. Модели параллельных программ: spmd, мастер/рабочие.

Схема мастер/рабочие (master/slaves). Процесс-мастер порождает какое-то число одинаковых процессов-рабочих, распределяет между ними работу и собирает результат.

Приведём для примера текст подобной программы написанной для системы Linda.

m ain(argc, argv)

int argc;

char *argv[];

{

int nworker, j, hello();

nworker = atoi (argv[l]);

for (j = 0; j < nworker; j++)

eval ("worker", hello(j));

for(j =0; j < nworker; j++)

in("done");

printf("Hello_world is finished.\n");

}

int hello (num) /** function hello **/

int num;

{

printf("Hello world from number %d.\n", num);

out("done");

return(0);

}

Если много рабочих то мастер не сможет их всех обслужить.

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

32 Вопрос. Модели передачи сообщений Send/Recv и Put/Get; свойства программ, написанных в терминах Put/Get.

Обмен сообщениями по традиционной схеме send/Receive не всегда является удобным. Иногда активной стороной вполне может быть только один процесс. Если он знает, какому процессу нужно передать данные и где их разместить, то зачем требовать активности получателя? Аналогично и в случае приема сообщений. Практика показала, что схема Put /Get для многих приложений является более приемлемой, что и послужило поводом для ее включения в MPI-2. Следует учесть, что схема Put /Get особенно актуальна на компьютерах с общей памятью, которые активно появляются в последнее время.

MPI2

1. Динамическое порождение процессов

2. Односторонние коммуникации Send_receive put/get 1 активный участник

3. Параллельный ввод вывод

4. Расширение функциональности коллективных операций

5. С++

33 Вопрос. OpenMp: общая концепция.

Одним из наиболее популярных средств программирования компьютеров с общей памятью, построенных на подобных принципах, в настоящее время является технология ОрепМР. За основу берется последовательная програм­ма, а для создания ее параллельной версии пользователю предоставляется набор директив, процедур и переменных окружения. Стандарт ОрепМР разра­ботан для языков Fortran (77, 90, и 95), С и C++ и поддерживается практи­чески всеми производителями больших вычислительных систем. Реализации стандарта доступны как на многих UNIX-платформах, так и в среде Win­dows NT. Поскольку все основные конструкции для этих языков похожи, то рассказ о данной технологии мы будем вести на примере только одного из них, а именно на примере языка Fortran.

Как в рамках правил ОрепМР пользователь должен представлять свою па­раллельную программу? Весь текст программы разбит на последовательные и параллельные области (рис. 5.2). В начальный момент времени порожда­ется нить-мастер или "основная" нить, которая начинает выполнение про­граммы со стартовой точки. Здесь следует сразу оговориться, почему вместо традиционного для параллельного программирования термина "процесс" появился новый термин — "нить" {thread, легковесный процесс, иногда "поток"). Технология ОрепМР опирается на понятие общей памяти, и по­этому она, в значительной степени, ориентирована на SMP-компьютеры. На подобных архитектурах возможна эффективная поддержка нитей, испол­няющихся на различных процессорах, что позволяет избежать значительных накладных расходов на поддержку классических UNIX-процессов.

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

В параллельной области все переменные программы разделяются на два класса: общие (SHARED) и локальные (PRIVATE). Общие переменные всегда существуют лишь в одном экземпляре для всей программы и доступны всем нитям под одним и тем же именем. Объявление локальных переменных вы­зывает порождение своего экземпляра каждой переменной для каждой нити. Изменение нитью значения своей локальной переменной, естественно, ни­как не влияет на изменение значения этой же локальной переменной в других нитях.

Рассмотрим базовые положения и основные конструкции ОрепМР. Все ди­рективы ОрепМР располагаются в комментариях и начинаются с одной из следующих комбинаций: !$омр, с$омр или *$омр (напомним, что строка, начинающаяся с одного из символов '! ', ' с' или ' *' по правилам языка Fortran считается комментарием). В дальнейшем изложении при описании конкретных директив для сокращения записи мы иногда будем опускать эти префиксы, хотя в реальных программах они, конечно же, всегда должны присутствовать. Все переменные среды окружения и функции, относящиеся к ОрепМР, начинаются с префикса омр_.

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

!$ОМР PARALLEL

<параллельный код программы> !$ОМР END PARALLEL

Для выполнения кода, расположенного между данными директивами, ни­тью-мастером дополнительно порождается omp_num_threads - 1 нитей, где omp_num_threads — это переменная окружения, значение которой пользова­тель задает перед запуском программы и, вообще говоря, может изменять. Нить-мастер всегда получает номер 0. Все нити исполняют код, заключен­ный между данными директивами.

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

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

Число нитей в параллельной секции можно менять. Если значение переменной

OMP_DYNAMIC раВНО 1, ТО С ПОМОЩЬЮ фуНКЦИИ OMP_SET_NUM_THREADS ПОЛЬЗО-

ватель может изменить значение переменной omp_num_threads, а значит и число порождаемых при входе в параллельную секцию нитей. Значение пе­ременной OMP_DYNAMIC Контролируется функцией OMP_SET_DYNAMIC.

Необходимость порождения нитей и параллельного исполнения кода парал­лельной секции пользователь может определять динамически с помощью дополнительной опции if в директиве:

!$ОМР PARALLEL IF(<условие>)

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

Мы уже говорили о том, что все порожденные нити исполняют один и тот же код. Теперь нужно обсудить вопрос, как разумным образом распределить между ними работу. Для распределения работы в рамках ОрепМР можно ис­пользовать четыре варианта:

□  программирование на низком уровне;

□  директива do для параллельного выполнения циклов;

□  директива sections для параллельного выполнения независимых фраг­ментов программы;

□  директива single для однократного выполнения участка кода. Программирование на низком уровне предполагает распределение работы с

помощью функций OMP_GET_THREAD_NUM И OMP_GET_NUM_THREADS, ВОЗВра-

щающих номер нити и общее количество порожденных нитей соответствен­но. Например, если написать фрагмент вида:

IF(OMP_GET_THREAD_NUM() .EQ. 3) THEN

<индивидуальный код для нити с номером 3> ELSE

<код для всех остальных нитей> ENDIF

то часть программы между директивами if. . .else будет выполнена только нитью с номером 3, а часть между else. . .endif — всеми остальными. Как и прежде, исходный код остается одинаковым для всех нитей. Однако ре­альная передача управления в нем будет идти для разных нитей по-разному, поскольку функция omp_get_thread_num () возвратит значение 3 только для нити с номером 3.

Если в параллельной секции встретился оператор цикла, то согласно обще­му правилу он будет выполнен всеми нитями, т. е. каждая нить выполнит все итерации данного цикла.

Для распределения итераций цикла между нитями нужно использовать дирек­тиву do:

!$ОМР DO [опция [[,] опция]...]

<о!о-цикл> [!$ОМР END DO]

Данная директива относится к идущему следом за ней оператору do.

□  Опция schedule определяет конкретный способ распределения итераций данного цикла по нитям.

□   static [,m] — блочно-циклическое распределение итераций. Первый блок из m итераций выполняет первая нить, второй блок — вторая и т. д. до последней нити, затем распределение снова начинается с первой ни­ти. Если значение m не указано, то все множество итераций делится на непрерывные куски примерно одинакового размера, и таким образом по­лученные куски распределяются между нитями.

□  dynamic [,m] — динамическое распределение итераций с фиксирован­ным размером блока. Сначала все нити получают порции из m итераций, а затем каждая нить, заканчивающая свою работу, получает следующую порцию, содержащую также m итераций. Если значение m не указано, оно принимается равным единице.

□  guided [,m] — динамическое распределение итераций блоками умень­шающегося размера. Сначала размер выделяемых блоков берется доста­точно большим, а в процессе работы программы он все время уменьша­ется. Минимальный размер блока итераций равен т. Размер первона­чально выделяемого блока зависит от реализации. Если значение m не указано, оно принимается равным единице. В ряде случаев такое распре­деление позволяет аккуратнее разделить работу и сбалансировать загрузку нитей.

□  runtime — способ распределения итераций цикла выбирается во время работы программы в зависимости от значения переменной omp_schedule.

Выбранный способ распределения итераций указывается в скобках после опции schedule, например:

!$ОМР DO SCHEDULE (DYNAMIC, 10)

В данном примере будет использоваться динамическое распределение ите­раций блоками по 10 итераций.

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

На организацию параллельных циклов накладывается несколько естествен­ных ограничений. В частности, предполагается, что корректная программа не должна зависеть от того, какая именно нить какую итерацию параллель­ного цикла выполнит. Нельзя использовать побочный выход из параллель­ного цикла. Размер блока итераций, указанный в опции schedule, не должен изменяться в рамках цикла.

Рассмотрим следующий пример. Будем предполагать, что он расположен в параллельной секции программы.

!$ОМР DO SCHEDULE (STATIC, 2) DO i = 1, n DO j = 1, m

A(i, j) = (B(i, j - 1) + B(i - 1, j)) /2.0

END DO END DO !$OMP END DO

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

Параллелизм на уровне независимых фрагментов оформляется в ОрепМР с помощью парной директивы sections. . .end sections и какого-то числа директив section, расположенных внутри этой пары. Например:

!$ОМР SECTIONS !$ОМР SECTION

<фрагмент 1> !$ОМР SECTION

<фрагмент 2> !$ОМР SECTION

<фрагментЗ> !$ОМР END SECTIONS

В данном примере программист описал, что все три фрагмента можно ис­полнять параллельно. Каждый из таких фрагментов будет выполнен только один раз какой-либо одной нитью. Если число нитей больше числа секций, то какие нити для каких секций задействовать, а какие нити не использо­вать вовсе, решают авторы конкретной реализации ОрепМР. В конце конст­рукции предполагается неявная синхронизация работы нитей. Если в по­добной синхронизации нет необходимости, то может быть использована директива END SECTIONS nowait.

В директивах do и sections можно использовать опции firstprivate и lastprivate, каждую со своим списком переменных. Эти опции управляют инициализацией локальных переменных перед входом в данные конструк­ции, а также определяют те значения, которые переменные будут иметь по­сле завершения параллельного цикла и обработки секций.

Если в параллельной секции какой-либо участок кода должен быть выпол­нен лишь один раз, то его нужно поставить между директи­вами single...end single. Подобная необходимость часто возникает при работе с общими переменными. Указанный участок будет выполнен только одной нитью. Если в конце не указана директива end single nowait, то выполнится неявная синхронизация всех нитей.