Глобальные вычислительные операции над распределенными данными

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

В MPI глобальные операции редукции представлены в нескольких вариантах:

  • с сохранением результата в адресном пространстве одного процесса (MPI_Reduce).
  • с сохранением результата в адресном пространстве всех процессов (MPI_Allreduce).
  • префиксная операция редукции, которая в качестве результата операции возвращает вектор. i-я компонента этого вектора является результатом редукции первых i компонент распределенного вектора (MPI_Scan).
  • совмещенная операция Reduce/Scatter (MPI_Reduce_scatter).

Функция MPI_Reduce выполняется следующим образом. Операция глобальной редукции, указанная параметром op, выполняется над первыми элементами входного буфера, и результат посылается в первый элемент буфера приема процесса root. Затем то же самое делается для вторых элементов буфера и т.д.

С:

int MPI_Reduce(void* sendbuf, void* recvbuf, int count, MPI_Datatype datatype,

MPI_Op op, int root, MPI_Comm comm)

IN sendbuf - адрес начала входного буфера;
OUT recvbuf - адрес начала буфера результатов (используется только в процессе-получателе root);
IN count - число элементов во входном буфере;
IN datatype - тип элементов во входном буфере;
IN op - операция, по которой выполняется редукция;
IN root - номер процесса-получателя результата операции;
IN comm - коммуникатор.

На рис. 4.8 представлена графическая интерпретация операции Reduce. На данной схеме операция "+" означает любую допустимую операцию редукции.

Глобальные вычислительные операции над распределенными данными - student2.ru

Рис. 4.8. Графическая интерпретация операции Reduce.

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

Таблица 4.1. Предопределенные операции в функциях редукции MPI
Название Операция Разрешенные типы
MPI_MAX MPI_MIN Максимум Минимум C integer, FORTRAN integer, Floating point</TD< tr>
MPI_SUM MPI_PROD Сумма Произведение C integer, FORTRAN integer, Floating point, Complex</TD< tr>
MPI_LAND MPI_LOR MPI_LXOR Логическое AND Логическое OR Логическое исключающее OR C integer, Logical</TD< tr>
MPI_BAND MPI_BOR MPI_BXOR Поразрядное AND Поразрядное OR Поразрядное исключающее OR C integer, FORTRAN integer, Byte</TD< tr>
MPI_MAXLOC MPI_MINLOC Максимальное значение и его индекс Минимальное значение и его индекс Специальные типы для этих функций</TD< tr>

В таблице используются следующие обозначения:

C integer: MPI_INT, MPI_LONG, MPI_SHORT, MPI_UNSIGNED_SHORT, MPI_UNSIGNED, MPI_UNSIGNED_LONG
Floating point: MPI_FLOAT, MPI_DOUBLE, MPI_REAL, MPI_DOUBLE_PRECISION, MPI_LONG_DOUBLE
Logical: MPI_LOGICAL
Complex: MPI_COMPLEX
Byte: MPI_BYTE

Операции MAXLOC и MINLOC выполняются над специальными парными типами, каждый элемент которых хранит две величины: значения, по которым ищется максимум или минимум, и индекс элемента. В MPI имеется 9 таких предопределенных типов.

C:  
MPI_FLOAT_INT float and int  
MPI_DOUBLE_INT double and int  
MPI_LONG_INT long and int  
MPI_2INT int and int  
MPI_SHORT_INT short and int  
MPI_LONG_DOUBLE_INT long double and int  

Функция MPI_Allreduce сохраняет результат редукции в адресном пространстве всех процессов, поэтому в списке параметров функции отсутствует идентификатор корневого процесса root. В остальном, набор параметров такой же, как и в предыдущей функции.

С:

int MPI_Allreduce(void* sendbuf, void* recvbuf, int count,

MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)

IN sendbuf - адрес начала входного буфера;
OUT recvbuf - адрес начала буфера приема;
IN count - число элементов во входном буфере;
IN datatype - тип элементов во входном буфере;
IN op - операция, по которой выполняется редукция;
IN comm - коммуникатор.

На рис. 4.9 представлена графическая интерпретация операции Allreduce.

Глобальные вычислительные операции над распределенными данными - student2.ru

Рис. 4.9. Графическая интерпретация операции Allreduce.

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

С:

MPI_Reduce_scatter(void* sendbuf, void* recvbuf, int *recvcounts,

MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)

IN sendbuf - адрес начала входного буфера;
OUT recvbuf - адрес начала буфера приема;
IN revcount - массив, в котором задаются размеры блоков, посылаемых процессам;
IN datatype - тип элементов во входном буфере;
IN op - операция, по которой выполняется редукция;
IN comm - коммуникатор.

Функция MPI_Reduce_scatter отличается от MPI_Allreduce тем, что результат операции разрезается на непересекающиеся части по числу процессов в группе, i-ая часть посылается i-ому процессу в его буфер приема. Длины этих частей задает третий параметр, являющийся массивом. На рис. 4.10 представлена графическая интерпретация операции Reduce_scatter.

Глобальные вычислительные операции над распределенными данными - student2.ru

Рис. 4.10. Графическая интерпретация операции Reduce_scatter.

Функция MPI_Scan выполняет префиксную редукцию. Параметры такие же, как в MPI_Allreduce, но получаемые каждым процессом результаты отличаются друг от друга. Операция пересылает в буфер приема i-го процесса редукцию значений из входных буферов процессов с номерами 0, ... i включительно.

С:

int MPI_Scan(void* sendbuf, void* recvbuf, int count,

MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)

IN sendbuf - адрес начала входного буфера
OUT recvbuf - адрес начала буфера приема
IN count - число элементов во входном буфере
IN datatype - тип элементов во входном буфере
IN op - операция, по которой выполняется редукция
IN comm - коммуникатор

На Рис. 4.11 представлена графическая интерпретация операции Scan.

Глобальные вычислительные операции над распределенными данными - student2.ru

Рис. 4.11. Графическая интерпретация операции Scan.

Наши рекомендации