В параллельном программировании математические операции над блоками данных, распределенных по процессорам, называют глобальными операциями редукции. В общем случае операцией редукции называется операция, аргументом которой является вектор, а результатом - скалярная величина, полученная применением некоторой математической операции ко всем компонентам вектора. В частности, если компоненты вектора расположены в адресных пространствах процессов, выполняющихся на различных процессорах, то в этом случае говорят о глобальной (параллельной) редукции. Например, пусть в адресном пространстве всех процессов некоторой группы процессов имеются копии переменной 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)

FORTRAN:

MPI_REDUCE(SENDBUF, RECVBUF, COUNT, DATATYPE, OP, ROOT,

COMM, IERROR)

<type> SENDBUF(*), RECVBUF(*)

INTEGER COUNT, DATATYPE, OP, ROOT, COMM, IERROR

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

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

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

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

C integer:	MPI_INT, MPI_LONG, MPI_SHORT, MPI_UNSIGNED_SHORT, MPI_UNSIGNED, MPI_UNSIGNED_LONG
FORTRAN integer:	MPI_INTEGER
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 таких предопределенных типов.

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

С:

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

MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)

FORTRAN:

MPI_ALLREDUCE (SENDBUF, RECVBUF, COUNT, DATATYPE, OP,

COMM, IERROR)

<type> SENDBUF(*), RECVBUF(*)

INTEGER COUNT, DATATYPE, OP, COMM, IERROR

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

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

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

С:

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

MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)

FORTRAN:

MPI_REDUCE_SCATTER(SENDBUF,RECVBUF,RECVCOUNTS,

DATATYPE, OP, COMM, IERROR)

<type> SENDBUF(*), RECVBUF(*)

INTEGER RECVCOUNTS(*), DATATYPE, OP, COMM, IERROR

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

Рис. 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)

FORTRAN:

MPI_SCAN(SENDBUF, RECVBUF, COUNT, DATATYPE, OP, COMM, IERROR)

<type>SENDBUF(*), RECVBUF(*)

INTEGER COUNT, DATATYPE, OP, COMM, IERROR

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

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