Программирование для многопроцессорных систем в стандарте MPI - Шпаковский Г.И., Серикова Н.В

долей секунды (образцовое решение делает 100000/size итераций для целых size), повторить тестирование несколько раз (например, 10) и усреднить результаты.

4.8.Напишите программу для измерения времени, необходимого для выполнения MPI_Allreduce на MPI_COMM_WORLD. Как изменяются характеристики для MPI_Allreduce при изменении размера MPI_COMM_WORLD?

4.9.Напишите программу для измерения времени, необходимого для выполнения MPI_Barrier на MPI_COMM_WORLD. Как изменяются характеристики для

MPI_Barrier при изменении размера MPI_COMM_WORLD?

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

4.11.Пусть A(n,m) – матрица, созданная в процессе 0. Например, может быть прочитана из памяти или уже была вычислена. Пусть имеем 4 процесса и процесс 0 посылает части этой матрицы другим процессам. Процессор 1 получает

A(i,j) для i=n/2+1,...,n, и j=1,...,m/2. Процессор 2 получает A(i,j) для i=1,...,n/2 и j=m/2+1,...,m и процессор 3 получает A(i,j) для i=n/2+1,...,n and j=m/2,...,m . Это двумерная декомпозиция А на четыре процесса. Напишите программу рассылки частей матрицы по процессам, используйте MPI_Scatterv, чтобы послать данные из процессора 0 всем другим процессам (включая процесс 0).

4.12.Пусть имеем двумерный массив X размера maxn*maxn. Эта структура есть двумерная регулярная сетка точек, которую разделим на слои, каждый из которых будет обрабатывать отдельный процесс. Пусть вычисления, которые необходимо выполнить, нуждаются в смежных значениях. Это означает, что для вычисления нового значения x[i][j] необходимо знать: x[i][j+1], x[i][j-1], x[i+1][j], x[i-1][j]. Последние два могут быть проблемой, если они находятся в смежных процессах. Чтобы разрешить это, определим теневые точки в каждом процессе, которые будут содержать эти смежные точки. Элементы среды, которые используются, чтобы сохранять данные из других процессов, называются «теневыми». Напишите программу для правильного заполнения теневых точек в каждом процессе. Для простоты предположите:

1)maxn = 12 и количество процессов =4;

2)каждый процесс заполняет свою часть массива собственным номером в коммуникаторе, а теневые точки значениями -1. После обмена с соседними процессами необходимо проверить правильность заполнения теневых точек;

3)область непериодическая, то есть верхний процесс (номер = size-1) только посылает и принимает данные от нижележащего процесса (номер = size–2), а самый нижний процесс (номер = 0) передает и принимает данные только от процесса выше него (номер = 1).

4.13.Выполните задание 4.12, используя неблокируемые парные обмены

вместо блокируемых. Замените MPI_Send и MPI_Recv процедурами MPI_ISend и MPI_IRecv и используйте MPI_Wait или MPI_Waitall для теста на окончание неблокируемой операции.

4.14. Выполните задание 4.12, заменив в решении вызовы MPI_Send и MPI_Recv двумя вызовами MPI_SendRecv. Первый вызов должен сдвинуть данные вверх, то есть послать данные процессору, который расположен выше и при-

141

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

4.15. Выполните задание 4.12, используя MPI_SendRecv для обмена данными с соседними процессами. Это означает, что обмениваются процессы 0 и 1, 2 и 3 и так далее.

4.16. В этом задании необходимо решить уравнение Лапласа на сетке двух измерений методом итераций Якоби. Любой текст численного анализа показывает, что итерации будут вычислять аппроксимацию для решения уравнения Лапласа, причем новое значение xnew замещается средним значением точек вокруг него для внутренних точек, а граничные значения остаются фиксированными.

while (not converged) {

На практике это означает, что если сетка имеет размер n*n, тогда значения x[0][j], x[n-1][j], x[i][0], x[i][n-1] не изменяются. Для проверки сходимости выбе-

рем следующий критерий:

diffnorm = 0; for (i,j)

diffnorm += (xnew[i][j] – x[i][j]) * (xnew[i][j] – x[i][j]); diffnorm = sqrt(diffnorm).

Когда diffnorm станет меньше 1.0e-2, будем считать, что результат достигнут. Напишите программу исполнения этой аппроксимации. Для простоты рассмотрите сетку 12*12 на 4 процессах, заполненную значениями предыдущего примера: это значения равные -1 на границах, значения, равные номеру процесса

во внутренних точках сетки.

4.17. Выполните задание 4.16, модифицируя его так, чтобы вычисленное решение собиралось в процессоре 0, который затем выводит этот результат.

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

4.19.Выполните задание 4.17 при условии, что распределяемый массив заполняется значениями из файла.

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

4.21. Напишите программу нахождения максимального значения и его индекс из массива чисел равномерно распределенного по процессам.

142

Глава 5. ГРУППЫ И КОММУНИКАТОРЫ

5.1.ВВЕДЕНИЕ

Вэтом разделе рассматриваются средства MPI для поддержки разработки параллельных библиотек. Для создания устойчивых параллельных библиотек интерфейс MPI должен обеспечить:

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

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

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

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

Для поддержки библиотек MPI обеспечивает группы процессов

(groups), виртуальные топологии (virtual topologies), коммуникаторы

(communicators).

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

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

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

143

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

5.2. БАЗОВЫЕ КОНЦЕПЦИИ

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

Имеется предопределенная группа: MPI_GROUP_EMPTY, которая является группой без членов. Предопределенная константа MPI_GROUP_NULL является значением, используемым для ошибочных дескрипторов группы.

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

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

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

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

Начальный для всех возможных процессов интра-коммуникатор MPI_COMM_WORLD создается сразу при обращении к функции MPI_INIT. Кроме того, существует коммуникатор, который cодержит

144

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

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

Все реализации MPI должны обеспечить наличие коммуникатора MPI_COMM_WORLD. Он не может быть удален в течение времени существования процесса. Группа, соответствующая этому коммуникатору, не появляется как предопределенная константа, но к ней можно обращаться, используя MPI_COMM_GROUP. MPI не определяет соответствия между номером процесса в MPI_COMM_WORLD и его абсолютным адресом.

5.3. УПРАВЛЕНИЕ ГРУППОЙ

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

int MPI_Group_size(MPI_Group group, int *size)

MPI_GROUP_SIZE(GROUP, SIZE, IERROR) INTEGER GROUP, SIZE, IERROR

int MPI::Group::Get_size() const

Функция MPI_GROUP_SIZE позволяет определить размер группы.

MPI_GROUP_RANK (group, rank)

int MPI_Group_rank(MPI_Group group, int *rank)

MPI_GROUP_RANK(GROUP, RANK, IERROR) INTEGER GROUP, RANK, IERROR

int MPI::Group::Get_rank() const

Функция MPI_GROUP_RANK служит для определения номера процесса в группе.

MPI_GROUP_TRANSLATE_RANKS(group1, n, ranks1, group2, ranks2)

int MPI_Group_translate_ranks (MPI_Group group1, int n, int *ranks1, MPI_Group group2, int *ranks2)

MPI_GROUP_TRANSLATE_RANKS(GROUP1, N, RANKS1, GROUP2, RANKS2, IERROR)

INTEGER GROUP1, N, RANKS1(*), GROUP2, RANKS2(*), IERROR

static void MPI::Group::Translate_ranks(const MPI::Group& group1, int n,

const int ranks[], const MPI::Group& group2, int ranks2[])

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

MPI_GROUP_COMPARE(group1, group2, result)

int MPI_Group_compare(MPI_Group group1,MPI_Group group2, int *result)

MPI_GROUP_COMPARE(GROUP1, GROUP2, RESULT, IERROR) INTEGER GROUP1, GROUP2, RESULT, IERROR

static int MPI::Group::Compare(const MPI::Group& group1, const MPI::Group& group2)

Если члены группы и их порядок в обеих группах совершенно одинаковы, вырабатывается результат MPI_IDENT. Это происходит,

146

например, если group1 и group2 имеют тот же самый дескриптор. Если члены группы одинаковы, но порядок различен, то вырабатывается результат MPI_SIMILAR. В остальных случаях получается значение

MPI_UNEQUAL.

5.3.2. Конструкторы групп

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

MPI не имеет механизма для формирования группы с нуля – группа может формироваться только на основе другой, предварительно определенной группы. Базовая группа, на основе которой определены все другие группы, является группой, связанной с коммуникатором

MPI_COMM_WORLD (через функцию MPI_COMM_GROUP).

MPI_COMM_GROUP(comm, group)

int MPI_Comm_group(MPI_Comm comm, MPI_Group *group)

MPI_COMM_GROUP(COMM, GROUP, IERROR) INTEGER COMM, GROUP, IERROR

MPI::Group MPI::Comm::Get_group() const

Функция MPI_COMM_GROUP возвращает в group дескриптор группы из comm.

MPI_GROUP_UNION(group1, group2, newgroup)

int MPI_Group_union(MPI_Group group1, MPI_Group group2, MPI_Group *newgroup)

MPI_GROUP_UNION(GROUP1, GROUP2, NEWGROUP, IERROR) INTEGER GROUP1, GROUP2, NEWGROUP, IERROR

static MPI::Group MPI::Group::Union(const MPI::Group& group1, const MPI::Group& group2)

147

Операции над множествами определяются следующим образом:

•Объединение (union) – содержит все элементы первой группы (group1) и следующие за ними элементы второй группы (group2), не входящие в первую группу.

•Пересечение (intersect) – содержит все элементы первой группы, которые также находятся во второй группе, упорядоченные, как в первой группе.

•Разность (difference) – содержит все элементы первой группы, которые не находятся во второй группе.

MPI_GROUP_INTERSECTION(group1, group2, newgroup)

int MPI_Group_intersection(MPI_Group group1, MPI_Group group2, MPI_Group *newgroup)

MPI_GROUP_INTERSECTION(GROUP1, GROUP2, NEWGROUP, IERROR) INTEGER GROUP1, GROUP2, NEWGROUP, IERROR

static MPI::Group MPI::Group::Intersect(const MPI::Group& group1, const MPI::Group& group2)

MPI_GROUP_DIFFERENCE(group1, group2, newgroup)

int MPI_Group_difference(MPI_Group group1, MPI_Group group2, MPI_Group *newgroup)

MPI_GROUP_DIFFERENCE(GROUP1, GROUP2, NEWGROUP, IERROR) INTEGER GROUP1, GROUP2, NEWGROUP, IERROR

static MPI::Group MPI::Group::Difference(const MPI::Group& group1, const MPI::Group& group2)

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

MPI_GROUP_EMPTY).

148

MPI_GROUP_INCL(group, n, ranks, newgroup)

int MPI_Group_incl(MPI_Group group, int n, int *ranks, MPI_Group *newgroup)

MPI_GROUP_INCL(GROUP, N, RANKS, NEWGROUP, IERROR) INTEGER GROUP, N, RANKS(*), NEWGROUP, IERROR

MPI::Group MPI::Group::Incl(int n, const int ranks[]) const

Функция MPI_GROUP_INCL создает группу newgroup, которая состоит из n процессов из group с номерами rank[0],..., rank[n-1]; процесс с номером i в newgroup есть процесс с номером ranks[i] в group. Каждый из n элементов ranks должен быть правильным номером в group, и все элементы должны быть различными, иначе программа будет неверна. Если n = 0, то newgroup имеет значение MPI_GROUP_EMPTY. Эта функция может, например, использоваться, чтобы переупорядочить элементы группы.

MPI_GROUP_EXCL(group, n, ranks, newgroup)

int MPI_Group_excl(MPI_Group group, int n, int *ranks, MPI_Group *newgroup)

MPI_GROUP_EXCL(GROUP, N, RANKS, NEWGROUP, IERROR) INTEGER GROUP, N, RANKS(*), NEWGROUP, IERROR

MPI::Group MPI::Group::Excl(int n, const int ranks[]) const

Функция MPI_GROUP_EXCL создает группу newgroup, которая получена путем удаления из group процессов с номерами ranks[0] ,...

ranks[n-1]. Упорядочивание процессов в newgroup идентично упорядочиванию в group. Каждый из n элементов ranks должен быть правильным номером в group, и все элементы должны быть различными;

149

в противном случае программа неверна. Если n = 0, то newgroup идентична group.

5.3.3. Деструкторы групп

MPI_GROUP_FREE(group)

INOUT group идентификатор группы (дескриптор) int MPI_Group_free(MPI_Group *group)

MPI_GROUP_FREE(GROUP, IERROR) INTEGER GROUP, IERROR

void MPI::Group::Free()

Эта операция маркирует объект группы для удаления. Дескриптор group устанавливается вызовом в состояние MPI_GROUP_NULL. Любая выполняющаяся операция, использующая эту группу, завершитcя нормально.

5.4. УПРАВЛЕНИЕ КОММУНИКАТОРАМИ

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

5.4.1. Доступ к коммуникаторам

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

MPI_COMM_SIZE(comm, size)

int MPI_Comm_size(MPI_Comm comm, int *size)

MPI_COMM_SIZE(COMM, SIZE, IERROR) INTEGER COMM, SIZE, IERROR

int MPI::Comm::Get_size() const

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

150