Князева М.А, Молчанова Л.А., Тарасов Г.В. Параллельное программирование. Методические указания и задания для cтудентов специальноcти 351500

Подождите немного. Документ загружается.

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Дальневосточный государственный университет

М.А. КНЯЗЕВА

Л.А. МОЛЧАНОВА

Г.В ТАРАСОВ

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ

Методические указания и задания для

студентов специальноcти 351500

Математическое обеспечение и администрирование информационных систем

Владивосток

Издательство Дальневосточного университета

2007

ББК

Рецензенты:

Е.А.Нурминский, д.ф.-м.н. (ИМКН ДВГУ, РАН);

Князева М.А, Молчанова Л.А., Тарасов Г.В. Параллельное программирование.

Методические указания и задания для cтудентов специальноcти 351500. - Владивосток: Изд-

во Дальневост. ун-та, 2006. - 61 с.

Методические указания разработаны для студентов Института

математики и компьютерных наук ДВГУ. Пособие представляет собой введение в методы

программирования для параллельных ЭВМ. Вопросы распараллеливания конкретных

алгоритмов рассматриваются на примерах на языке программирования Си.

Для студентов математических специальностей.

ББК

@ Князева М.А., 2007

@ Молчанова Л.А., 2007

@ Тарасов Г.В. , 2007

@ ИМКН ДВГУ, 2007

Содержание

Часть 1. Функции системы программирования MPI 4

Введение 4

Общие функции MPI 5

Сообщения 6

Коммуникаторы 7

Прием/передача сообщений между отдельными процес

Совмещение приема и передачи сообщений 15

Коллективные взаимодействия процессов 15

Синхронизация процессов 18

Работа с группами процессов 18

Часть 2. Примеры использования MPI 19

Задание 1. 19

Задание 2. 23

Задание 3. 25

Задание 4. 29

Задание 5. 31

Задание 6. 34

Задание 7. 36

Часть 3. Правила работы в среде MPI

1. Архитектура кластера 40

1.1. Командный интерфейс 40

2. Основные команды Linux 41

2.1. Команда ls 41

2.2. Команда cd 42

2.3. Команда md 42

2.4. Команда less 42

2.5. Команда vim 42

2.6. Команда cp 43

2.7. Команда mv 43

2.8. Команда rm 43

2.9.

Команда passwd 43

3. Файловый интерфейс 43

4. Компиляция параллельных программ 43

5. Запуск параллельных программ 45

6. Рекомендации по отладке программ 46

6.1. Применение printf() 46

6.2. Утилита xmpi 46

6.2.1. Запуск параллельной программы 47

6.2.2. Просмотр результатов 47

6.2.3. Завершение работы 47

Задания 49

Литература 51

Приложение 1 53

Приложение 2 54

Приложение 3 56

Часть 1. Функции системы программирования MPI

Введение

Широкое распространение компьютеров с распределенной памятью определило и

появление соответствующих систем программирования. Как правило, в таких системах

отсутствует единое адресное пространство, и для обмена данными между параллельными

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

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

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

практически все системы программирования, основанные на явной передаче сообщений,

существуют не в виде новых языков, а в виде интерфейсов и библиотек.

К настоящему времени примеров известных систем программирования на основе

передачи сообщений накопилось довольно много: Shmem, Linda, PVM, MPI и др.

МРI представляет собой набор утилит и библиотечных функций (для языка С/С++,

Fortran), позволяющих создавать и запускать приложения, работающие на параллельных

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

Все дополнительные объекты: имена функций, константы, предопределенные типы

данных и т. п., используемые в МРI, имеют префикс MPI_. Например, функция посылки

сообщения от одного процесса другому имеет имя MPI_Send. Все описания интерфейса МРI

собраны в файле mpi.h, поэтому в начале МРI-программы должна стоять директива #inciude

<mpi.h>.

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

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

выполнения MPI-программы порождение дополнительных процессов или уничтожение

существующих не допускается.

Каждый процесс работает в своем адресном пространстве, никаких общих переменных

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

явная посылка сообщений.

Для локализации взаимодействия параллельных процессов программы можно

создавать группы процессов, предоставляя им отдельную среду для общения -

коммуникатор. Состав образуемых групп произволен. Группы могут полностью входить

одна в другую, не пересекаться или пересекаться частично. При старте программы всегда

считается, что все порожденные процессы работают в рамках всеобъемлющего

коммуникатора, имеющего предопределенное имя MPI_COMM_WORLD. Этот

коммуникатор существует всегда и служит для взаимодействия всех процессов MPI-

программы.

Каждый процесс MPI-программы имеет уникальный атрибут номер процесса, который

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

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

коммуникаторе все процессы имеют различные номера. Но поскольку процесс может

одновременно входить в разные коммуникаторы, то его номер в одном коммуникаторе

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

коммуникатор и номер в коммуникаторе.

Если группа содержит n процессов, то номер любого процесса в данной группе лежит в

пределах от 0 до n - 1.

Основным способом общения процессов между собой является посылка cообщений.

Сообщение - это набор данных некоторого типа. Каждое сообщение имеет несколько

атрибутов, в частности, номер процесса-отправителя, номер процесса-получателя,

идентификатор сообщения и др. Одним из важных атрибутов сообщения является его

идентификатор или тэг. По идентификатору процесс, принимающий сообщение, например,

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

идентификатор сообщения является целым неотрицательным числом, лежащим в диапазоне

от 0 до 32767. Для работы с атрибутами сообщений введена структура MPI_Status, поля

которой дают доступ к значениям атрибутов.

На практике сообщение чаще всего является набором однотипных данных,

расположенных подряд друг за другом в некотором буфере. Такое сообщение может

состоять, например, из двухсот целых чисел, которые пользователь разместил в

соответствующем целочисленном векторе. Это типичная ситуация, на нее ориентировано

большинство функций MPI, однако такая ситуация имеет, по крайней мере, два ограничения.

Во-первых, иногда необходимо составить сообщение из разнотипных данных. Конечно же,

можно отдельным сообщением послать количество вещественных чисел, содержащихся в

последующем сообщении, но это может быть и неудобно программисту, и не столь

эффективно. Во-вторых, не всегда посылаемые данные занимают непрерывную область в

памяти. Если в Fortran элементы столбцов матрицы расположены в памяти друг за другом, то

элементы строк уже идут с некоторым шагом. Чтобы послать строку, данные нужно сначала

упаковать, передать, а затем вновь распаковать.

Чтобы снять указанные ограничения, в MPI предусмотрен механизм для введения

производных типов данных. Описав состав и схему размещения в памяти посылаемых

данных, пользователь в дальнейшем

работает с такими типами так же, как и со

стандартными типами данных MPI.

Общие функции MPI

Имена всех функций, типов данных, констант и т.д., относящихся к MPI-библиотеке,

начинаются с префикса MPI_ и описаны в заголовочном файле mpi.h. Все функции (за

исключением MPI_Wtime и MPI_Wtick) имеют тип возвращаемого значения int и

возвращают код ошибки или MPI_SUCCESS в случае успеха. Однако в случае ошибки

перед возратом из вызвавшей ее функции вызывается стандартный обработчик ошибки,

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

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

До первого вызова любой MPI-функции необходимо вызывать функцию MPI_Init. Ее

прототип:

int MPI_Init(int *argc, char ***argv);

где argc, argv - указатели на число аргументов программы и на вектор аргументов

соответственно (это адреса аргументов функции main программы). Многие реализации МРI

требуют, чтобы процесс до вызова MPI_Init не делал ничего, что могло бы изменить его

состояние, например открытие или чтение/запись файлов, включая стандартный ввод и

вывод.

Поскольку для сложных

приложений, которые состоят из многих модулей и пишутся

разными людьми, это отследить трудно, введена дополнительная функция MPi_Initialized:

MPI_Initialized (int *flag)

Здесь OUT flag - признак инициализации параллельной части программы.

Если функция MPi_Init уже была вызвана, то через параметр flag возвращается

значение 1, в противном случае 0.

После окончания работы с MPI-функциями необходимо вызывать функцию

MPI_Finalize. Ее прототип:

MPI_Finalize (void);

Все последующие

обращения к любым MPI-функциям, в том числе к MPI_Init,

запрещены. К моменту вызова MPI_Finalize каждым процессом программы все действия,

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

Общий вид MPI-программы:

#include "mpi.h"

/* Другие описания */

main(int argc, char *argv[])

{

/* Описания локальных переменных */

MPI Init(&argc, &argv);

/* Тело программы */

MPI_Finalize();

return 0;

}

Сообщения

Различают обмен сообщениями:

попарный - сообщение посылается одним процессом другому, в обмене участвуют

только два процесса.

коллективный - сообщение посылается процессом всем процессам из его группы

(коммуникатора) и получается всем процессами из его группу (коммуникатора).

Коллективный обмен может быть представлен как последовательность попарных обменов,

однако специализированные МPI-функции для коллективных обменов учитывают

специфику построения конкретной вычислительной установки и могут выполняться

значительно быстрее соответствующей последовательности попарных обменов.

Различают обмен сообщениями:

синхронный - процесс-отправитель сообщения переходит в состояние ожидания, пока

процесс-получатель не будет готов взять сообщение, а процесс-получатель сообщения

переходит в состояние ожидания, пока процесс-отправитель не будет готов послать

сообщение;

асинхронный - процесс-отправитель сообщения не ждет готовности процесса-

получателя, сообщение копируется под системой MPI во внутренний буфер, и отправитель

продолжает работу.

Поведение некачественной программы может быть разным при использовании

синхронного или асинхронного режима. Например, если процесс А посылает сообщение

процессу В, который не вызывает функцию получения сообщения, то это приводит к

"зависанию" процесса А в синхронном режиме. В асинхронном режиме такая программа

будет работать.

Основные составляющие сообщения:

1. Блок данных сообщения - представляется типом void*.

2. Информация о данных сообщения:

(a) тип данных - представляется типом MPI_Datatype; соответствие MPI-типов данных

и типов языка С приведены в табл. 1.

(b) количество данных - количество единиц данного типа в блоке сообщения.

Представляется типом int.

Таблица 1. Соответствие типов данных MPI и типов языка С

Тип MPI Тип С

MPI_CHAR signed char

MPI_SHORT signed short int

MPI_INT signed int

MPI_LONG signed long int

MPI_UNSIGNED_CHAR unsigned char

MPI_UNSIGNED_SHORT unsigned short int

MPI_UNSIGNED_INT unsigned int

MPI_UNSIGNED_LONG unsigned long int

MPI_FLOAT float

MPI_DOUBLE double

MPI_LONG_DOUBLE long double

MPI_BYTE unsigned char

3. Информация о получателе и отправителе сообщения:

(a) коммуникатор - идентификатор группы запущенных программой параллельных

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

MPI_Comm. Как получатель, так и отправитель, должны принадлежат указанной группе.

Процесс может принадлежать одновременно многим группам, все запущенные процессы

принадлежат группе с идентификатором MPI_COMM_WORLD.

(b) ранг получателя - номер процесса-получателя в указанной группе

(коммуникаторе). Представляется типом int. Это поле отсутствует при коллективных

обменах сообщениями.

(коммуникаторе). Представляется типом int. Получатель может указать, что он будет

принимать только сообщения от отправителя с определенным рангом, или использовать

константу MPI_ANY_SOURCE, позволяющую принимать сообщения от любого

отправителя в группе с указанным идентификатором. Это поле отсутствует при

коллективных обменах сообщениями.

4. Тег сообщения - произвольное число типа int (стандарт гарантирует возможность

использования чисел от 0 до 2

15)

, приписываемое отправителем сообщению. Получатель

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

использовать константу MPI_ANY_TAG, позволяющую принимать сообщения с любым

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

процессы обмениваются одинаковыми по структуре данными.

Коммуникаторы

Коммуникатор - это объект типа MPI_Comm, представляющий собой идентификатор

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

сообщениями. Коммуникатор является аргументов всех функций, осуществляющих обмен

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

идентифицируемую коммуникатором MPI_COMM_WORLD, на подгруппы для:

организации коллективного обмена внутри этих подгрупп,

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

функции, чтобы их сообщения не пересекались с сообщениями вызвавшего их процесса),

учета топологии распределенной вычислительной установки (например, часто

распределенный кластер можно представить в виде пространственной решетки,

составленной из скоростных линий связи, в узлах которой находятся рабочие станции;

скорости обмена данными между узлами тут различны и это можно учесть введением

соответствующих коммуникаторов).

Получить количество процессов в группе (коммуникаторе) можно с помощью функции

MPI_Comm_size. Ее прототип:

int MPI_Comm_size (MPI_Comm comm, int *size)

где comm - идентификатор коммуникатора (входной параметр), size - указатель на результат.

Например, общее количество запущенных процессов можно получить следующим образом:

int p;

MPI_Comm_size(MPI_COMM_WORLD,&p);

Получить ранг (номер) процесса в группе (коммуникаторе) можно с помощью функции

MPI_Comm_rank. Ее прототип:

int MPI_Comm_rank(MPI_Comm comm, int *rank)

где comm - идентификатор коммуникатора, OUT rank - номер процесса в коммуникаторе

comm.

Значение, возвращаемое функцией MPI_comm_rank через переменную rank, лежит в

диапазоне от 0 до size-1.

Например, номер текущего процесса среди всех запущенных можно получить

следующим образом:

Int my_rank;

MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);

double MPI_Wtime(void)

Эта функция возвращает астрономическое время в секундах (вещественное число),

прошедшее с некоторого момента в прошлом. Если некоторый участок программы окружить

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

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

отсчета, не будет изменен за время существования процесса. Заметим, что эта функция

возвращает результат своей работы не через параметры, а явным образом.

Простейший пример программы, в которой использованы описанные выше функции,

выглядит так:

main(int argc, char **argv)

{ int me, size;

MPI_Init(&argc,&argv);

MPI_Comm_rank(MPI_COMM_WORLD,&me);

MPI_Comm_size(MPI_COMM_WORLD,&size);

printf("Process %d size %d \n", me, size);

...

MPI_Finalize();

...

Строка, соответствующая функции printf, будет выведена столько раз, сколько

процессов было порождено при вызове MPI_Init. Порядок появления строк заранее не

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

отдельных строк не будет перемешано друг с другом.

Прием/передача сообщений между отдельными процессами

Все функции данной группы делятся на два класса: функции с блокировкой (с

синхронизацией) и без блокировки (асинхронные).

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

Послать сообщение можно с помощью функции MPI_Send. Ее прототип:

int MPI_Send(void *buf,int count,MPI_Datatype datatype,int dest,int msgtag,

MPI_Comm соmm)

где

buf - адрес начала буфера с посылаемым сообщением;

count - число передаваемых элементов в сообщении;

datatype - тип передаваемых элементов;

dest - номер процесса-получателя;

msgtag-идентификатор сообщения;

соmm - идентификатор коммуникатора.

Блокирующая посылка сообщения с идентификатором msgtag, состоящей из count

элементов типа datatype, процессу с номером dest. Все элементы посылаемого сообщения

расположены подряд в буфере buf. Значение соunt может быть нулем. Разрешается

передавать сообщение самому себе. Тип передаваемых элементов datatype должен

указываться с помощью предопределенных констант типа, например, MPI_INT,

MPI_LONG, Mpi_SHORT, MPI_LONG_DOUBLE, MPI_CHAR, MPI_UNSIGNED_CHAR,

MPI_FLOAT или с помощью введенных производных типов. Для каждого типа данных

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

можно найти в файле mpi.h.

Эта функция может перевести текущий процесс в состояние ожидания, пока

получатель с номером dest в группе comm не примет сообщение с тегом tag (если

используется синхронный режим обмена).

Блокировка гарантирует корректность повторного использования всех параметров

после возврата из подпрограммы. Это означает, что после возврата из данной функции

можно использовать любые присутствующие в вызове функции переменные без опасения

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

копирование в промежуточный буфер или непосредственная передача процессу dest,

остается за разработчиками конкретной реализации MPI.

Возврат из функции MPI_Send не означает ни того, что сообщение получено

процессом dest, ни того, что сообщение покинуло процессорный элемент, на котором

выполняется процесс, запустивший MPI_Send. Предоставляется только гарантия

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

Чтобы расширить возможности передачи сообщений, в MPI введены дополнительные

три функции. Все параметры у этих функций такие же, как и у функции MPI_Send, однако у

каждой из них есть своя особенность.

MPI_Bsend - передача сообщения с буферизацией. Если прием посылаемого

сообщения еще не был инициализирован процессом-получателем, то сообщение будет

записано в буфер и произойдет немедленный возврат из функции. Выполнение данной

функции никак не зависит от соответствующего вызова функции приема сообщения. Тем не

менее, функция может вернуть код ошибки, если места под буфер недостаточно.

MPI_Ssend - передача сообщения с синхронизацией. Выход из данной функции

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

процессом-получателем. Таким образом, завершение передачи с синхронизацией говорит не

только о возможности повторного использования буфера, но и о гарантированном

достижении процессом-получателем точки приема сообщения в программе. Если приём

сообщения также выполняется с блокировкой, то функция MPI_Ssend сохраняет семантику

блокирующих вызовов.

MPI_Rsend - передача сообщения по готовности. Данной функцией можно

пользоваться только в том случае, если процесс-получатель уже инициировал прием

сообщения. В противном случае вызов функции, вообще говоря, является ошибочным и

результат ее выполнения не определен. Во многих реализациях функция MPI_Rsend

сокращает протокол взаимодействия между отправителем и получателем, уменьшая

накладные расходы на организацию передачи.

Получить сообщение можно с помощью функции MPI_Recv. Ее прототип:

int MPI_Recv(void *buf,int count,MPI_Datatype datatype,int source,

int msgtag, MPI Comm comm, MPI_Status *status)

где

OUT buf - адрес начала буфера для приема сообщения;

count - максимальное число элементов в принимаемом сообщении;

datatype - тип элементов принимаемого сообщения;

source - номер процесса-отправителя (может быть MPI_ANY_SOURCE);

msgtag - идентификатор принимаемого сообщения (может быть MPI_ANY_SOURCE);

comm - идентификатор коммуникатора;

OUT status - параметры принятого сообщения.

Прием сообщения

с идентификатором msgtag от процесса source с блокировкой. Число

элементов в принимаемом сообщении не должно превосходить значения count. Если число

принятых элементов меньше значения count, то гарантируется, что в буфере buf изменятся

только элементы, соответствующие элементам принятого сообщения.

Блокировка гарантирует, что после возврата из функции все элементы сообщения уже

будут приняты и расположены в буфере buf.

При

приеме сообщения в качестве номера процесса-отправителя можно указать

предопределенную константу MPI_ANY_SOURCE - признак того, что подходит сообщение

от любого процесса. В качестве идентификатора принимаемого сообщения можно указать

константу MPI_ANY_TAG - это признак того, что подходит сообщение с любым

идентификатором. При одновременном использовании этих двух констант будет принято

любое сообщение от любого процесса.

Параметры принятого сообщения всегда можно определить по соответствующим полям

структуры status. Предопределенный тип MPI_Status описан в файле mpi.h. В языке С

параметр status является структурой, содержащей поля с именами MPI_SOURCE,

MPI_TAG и MPI_ERROR. Реальные значения номера процесса-отправителя,

идентификатора сообщения и код ошибки доступны через status.MPI_SOURCE, status.

MPI_TAG и status.MPI_ERROR. В языке Fortran параметр status является целочисленным

массивом размера MPI_STATUS_SIZE. Константы MPI_SOURCE, MPI_TAG и

MPI_ERROR являются индексами по данному массиву для доступа к значениям

соответствующих полей, например, status(MPI_SOURCE).

Имеет место некоторая несимметричность операций посылки и приема сообщений. С

помощью константы MPI_ANY_SOURCE можно принять сообщение от любого процесса.

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

В стандарте оговорено, что если один процесс последовательно посылает два

сообщения другому процессу, и оба эти сообщения соответствуют одному и тому же вызову

MPI_Recv, то первым будет принято сообщение, которое было отправлено раньше. Вместе с

тем, если два сообщения были одновременно отправлены разными процессами и оба

сообщения соответствуют одному и тому же вызову MPI_Recv, то порядок их получения

принимающим процессом заранее не определен.

MPI не гарантирует выполнения свойства "справедливости" при распределении

приходящих сообщений. Предположим, что процесс Р1 послал сообщение, которое может

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

долгое время. Такое возможно, например, если процесс Р3, постоянно посылает сообщения

процессу Р2, также подходящие под шаблон MPI_Recv.

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

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

работают два параллельных процесса и они хотят обменяться данными. Было бы вполне

естественно в каждом процессе сначала воспользоваться функцией MPI_Send, а затем

MPI_Recv. Но именно этого и не стоит делать. Дело в том, что заранее неизвестно, как

реализована функция MPI_Send. Если разработчики для гарантии корректного повторного

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

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

функции посылки, поскольку второй не начинает прием сообщения. А второй процесс не

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

Выход из этой ситуации прост. Нужно использовать либо неблокирующие функции

приема/передачи, либо функцию совмещенной передачи и приема.

Для определения размера области памяти, выделяемой для хранения сообщения,

используется функция MPI_Probe. Ее прототип:

int MPI_Probe(int source, int msgtag, MPI_Соmm соmm, MPI Status *status)

Здесь:

source - номер процесса-отправителя или MPI_ANY_SOORCE;

msgtag - идентификатор ожидаемого сообщения или MPI_ANY_TAG;

comm - идентификатор коммуникатора;

OUT status - параметры найденного подходящего сообщения.

Возврата из функции не произойдет до тех пор, пока сообщение с подходящим

идентификатором и номером процесса-отправителя, не будет доступно для получения.

Атрибуты доступного сообщения можно определить обычным образом с помощью

параметра status. Функция определяет только факт прихода сообщения, но реально его не

принимает.

Прием/передача сообщений без блокировки.

В отличие от функций с блокировкой, возврат из функций данной группы происходит

сразу без какой либо блокировки процессов. На фоне дальнейшего выполнения программы

одновременно происходит и обработка асинхронно запущенной операции. В принципе,

данная возможность исключительно полезна для создания эффективных программ. В самом

деле, программист знает, что в некоторый момент ему потребуется массив, который

вычисляет другой процесс. Он заранее выставляет в программе асинхронный запрос на