Так вышло, что мне пришлось тесно столкнуться с изучением параллельных вычислений и в частности MPI. Пожалуй, направление это на сегодняшний день является весьма перспективным, так что хотелось бы показать хабраюзерам основы этого процесса.
В качестве примера будет использоваться расчет экспоненты (e). Один из вариантов ее нахождения — ряд Тейлора:
e^x=∑((x^n)/n!), где суммирование происходит от n=0 до бесконечности.
Данная формула легко поддается распараллеливанию, так как искомое число является суммой отдельных слагаемых и благодаря этому каждый отдельный процессор может заняться вычислением отдельных слагаемых.
Количество слагаемых, которое будет рассчитываться в каждом отдельно взятом процессоре, зависит как и от длины интервала n, так и от имеющегося количества процессоров k, которые смогут участвовать в процессе вычисления. Так, например, если длина интервала n=4, а в вычислениях участвуют пять процессоров (k=5), то с первого по четвертый процессоры получат по одному слагаемому, а пятый будет не задействован. В случае же если n=10, а k=5, каждому процессору достанется по два слагаемых для вычисления.
Изначально, первый процессор с помощью функции широковещательной рассылки MPI_Bcast отправляет остальным значение заданной пользователями переменной n. В общем случае функция MPI_Bcast имеет следующий формат:
int MPI_Bcast(void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm), где buffer – это адрес буфера с элементом, сount – количество элементов, datatype – соответствующий тип данных в MPI, root – ранг главного процессора, который занимается пересылкой, а comm- имя коммуникатора.
В моем случае в роли главного процессора, как уже говорилось, будет выступать первый процессор с рангом 0.
После того число n будет успешно отправлено, каждый процессор займется вычислением своих слагаемых. Для этого в каждом шаге цикла к числу i, которое изначально равно рангу процессора, будет прибавляться число, равное количеству процессоров участвующих в вычислениях. Если число в ходе следующих действий число i превысит заданное пользователем число n, выполнение цикла для данного процессора остановится.
В ходе выполнения цикла слагаемые будут прибавляться в отдельную переменную и, после его завершения, полученная сумма отправится в главный процессор. Для этого будет использоваться функция операции приведения MPI_Reduce. В общем виде она выглядит следующим образом:
int MPI_Reduce(void *buf, void *result, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)
Она объединяет элементы входного буфера каждого процесса в группе, используя операцию op, и возвращает объединенное значение в выходной буфер процесса с номером root. Результатом такой операции будет единственное значение, благодаря чему функция приведения и получила свое название.
После выполнения программы на всех процессорах, первый процессор получит общую сумму слагаемых, которая и будет являться нужным нам значение экспоненты.
Следует заметить, что и в параллельном и последовательном методах вычисления экспоненты, для нахождения факториала используется рекурсивная функция. В ходе принятия решения по способу распараллеливания выполняемой задачи, я рассматривал вариант нахождения факториала также на разных процессорах, но в итоге такой вариант был принят мной нерациональным.
Первостепенной задачей все же является нахождение значения экспоненты и если процессоры начнут вычислять каждый факториал каждого слагаемого раздельным образом, это может привести к прямо обратно эффекту, а именно значительной потери в производительности и скорости вычисления.
Объясняется это тем, что в данном случае начнется весьма большая нагрузка на коммуникационную среду, которая и без того зачастую является слабым звеном в системах параллельных вычислений. Если же вычисление факториала будет происходить на каждом процессоре частным образом, нагрузка на линии коммуникаций будет минимальна. Данный случай можно назвать хорошим примером того, что и задача распараллеливания тоже должна порой иметь свои границы.
1. Из визуальной оболочки в программу передается значение числа n, которое затем с помощью функции широковещательной рассылки отправляется по всем процессорам.
2. При инициализации первого главного процессора, запускается таймер.
3. Каждый процессор выполняет цикл, где значением приращения является количество процессоров в системе. В каждой итерации цикла вычисляется слагаемое и сумма таких слагаемых сохраняется в переменную drobSum.
4. После завершения цикла каждый процессор суммирует свое значение drobSum к переменной Result, используя для этого функцию приведения MPI_Reduce.
5. После завершения расчетов на всех процессорах, первый главный процессор останавливает таймер и отправляет в поток вывода получившееся значение переменной Result.
6. В поток вывода отправляется также и отмеренное нашим таймером значение времени в милисекундах.
Программа написана на С++, будем считать что аргументы для выполнения передаются из внешней оболочки. Код выглядит следующим образом:
Таким образом мы получили простенькую программу для подсчета экспоненты с использованием сразу нескольких процессоров. Наверное, узким местом является хранением самого результата, потому что с увеличением количества разрядов вмещать значение с использованием стандартных типов банально не выйдет и это место требует проработки. Пожалуй, достаточно рациональным решением является запись результата в файл, хотя, в виду чисто учебной функции этого примера, особо на этом внимание можно не акцентировать.
Основные принципы и пример
В качестве примера будет использоваться расчет экспоненты (e). Один из вариантов ее нахождения — ряд Тейлора:
e^x=∑((x^n)/n!), где суммирование происходит от n=0 до бесконечности.
Данная формула легко поддается распараллеливанию, так как искомое число является суммой отдельных слагаемых и благодаря этому каждый отдельный процессор может заняться вычислением отдельных слагаемых.
Количество слагаемых, которое будет рассчитываться в каждом отдельно взятом процессоре, зависит как и от длины интервала n, так и от имеющегося количества процессоров k, которые смогут участвовать в процессе вычисления. Так, например, если длина интервала n=4, а в вычислениях участвуют пять процессоров (k=5), то с первого по четвертый процессоры получат по одному слагаемому, а пятый будет не задействован. В случае же если n=10, а k=5, каждому процессору достанется по два слагаемых для вычисления.
Изначально, первый процессор с помощью функции широковещательной рассылки MPI_Bcast отправляет остальным значение заданной пользователями переменной n. В общем случае функция MPI_Bcast имеет следующий формат:
int MPI_Bcast(void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm), где buffer – это адрес буфера с элементом, сount – количество элементов, datatype – соответствующий тип данных в MPI, root – ранг главного процессора, который занимается пересылкой, а comm- имя коммуникатора.
В моем случае в роли главного процессора, как уже говорилось, будет выступать первый процессор с рангом 0.
После того число n будет успешно отправлено, каждый процессор займется вычислением своих слагаемых. Для этого в каждом шаге цикла к числу i, которое изначально равно рангу процессора, будет прибавляться число, равное количеству процессоров участвующих в вычислениях. Если число в ходе следующих действий число i превысит заданное пользователем число n, выполнение цикла для данного процессора остановится.
В ходе выполнения цикла слагаемые будут прибавляться в отдельную переменную и, после его завершения, полученная сумма отправится в главный процессор. Для этого будет использоваться функция операции приведения MPI_Reduce. В общем виде она выглядит следующим образом:
int MPI_Reduce(void *buf, void *result, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)
Она объединяет элементы входного буфера каждого процесса в группе, используя операцию op, и возвращает объединенное значение в выходной буфер процесса с номером root. Результатом такой операции будет единственное значение, благодаря чему функция приведения и получила свое название.
После выполнения программы на всех процессорах, первый процессор получит общую сумму слагаемых, которая и будет являться нужным нам значение экспоненты.
Следует заметить, что и в параллельном и последовательном методах вычисления экспоненты, для нахождения факториала используется рекурсивная функция. В ходе принятия решения по способу распараллеливания выполняемой задачи, я рассматривал вариант нахождения факториала также на разных процессорах, но в итоге такой вариант был принят мной нерациональным.
Первостепенной задачей все же является нахождение значения экспоненты и если процессоры начнут вычислять каждый факториал каждого слагаемого раздельным образом, это может привести к прямо обратно эффекту, а именно значительной потери в производительности и скорости вычисления.
Объясняется это тем, что в данном случае начнется весьма большая нагрузка на коммуникационную среду, которая и без того зачастую является слабым звеном в системах параллельных вычислений. Если же вычисление факториала будет происходить на каждом процессоре частным образом, нагрузка на линии коммуникаций будет минимальна. Данный случай можно назвать хорошим примером того, что и задача распараллеливания тоже должна порой иметь свои границы.
Алгоритм выполнения кода
1. Из визуальной оболочки в программу передается значение числа n, которое затем с помощью функции широковещательной рассылки отправляется по всем процессорам.
2. При инициализации первого главного процессора, запускается таймер.
3. Каждый процессор выполняет цикл, где значением приращения является количество процессоров в системе. В каждой итерации цикла вычисляется слагаемое и сумма таких слагаемых сохраняется в переменную drobSum.
4. После завершения цикла каждый процессор суммирует свое значение drobSum к переменной Result, используя для этого функцию приведения MPI_Reduce.
5. После завершения расчетов на всех процессорах, первый главный процессор останавливает таймер и отправляет в поток вывода получившееся значение переменной Result.
6. В поток вывода отправляется также и отмеренное нашим таймером значение времени в милисекундах.
Листинг кода
Программа написана на С++, будем считать что аргументы для выполнения передаются из внешней оболочки. Код выглядит следующим образом:
#include "mpi.h"
#include <iostream>
#include <windows.h>
using namespace std;
double Fact(int n)
{
if (n==0)
return 1;
else
return n*Fact(n-1);
}
int main(int argc, char *argv[])
{
SetConsoleOutputCP(1251);
int n;
int myid;
int numprocs;
int i;
int rc;
long double drob,drobSum=0,Result, sum;
double startwtime = 0.0;
double endwtime;
n = atoi(argv[1]);
if (rc= MPI_Init(&argc, &argv))
{
cout << "Ошибка запуска, выполнение остановлено " << endl;
MPI_Abort(MPI_COMM_WORLD, rc);
}
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
if (myid == 0)
{
startwtime = MPI_Wtime();
}
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
for (i = myid; i <= n; i += numprocs)
{
drob = 1/Fact(i);
drobSum += drob;
}
MPI_Reduce(&drobSum, &Result, 1, MPI_LONG_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
cout.precision(20);
if (myid == 0)
{
cout << Result << endl;
endwtime = MPI_Wtime();
cout << (endwtime-startwtime)*1000 << endl;
}
MPI_Finalize();
return 0;
}
* This source code was highlighted with Source Code Highlighter.Вывод
Таким образом мы получили простенькую программу для подсчета экспоненты с использованием сразу нескольких процессоров. Наверное, узким местом является хранением самого результата, потому что с увеличением количества разрядов вмещать значение с использованием стандартных типов банально не выйдет и это место требует проработки. Пожалуй, достаточно рациональным решением является запись результата в файл, хотя, в виду чисто учебной функции этого примера, особо на этом внимание можно не акцентировать.
