Pull to refresh

Основы MPI для «чайников»

System Programming *
Sandbox
Так вышло, что мне пришлось тесно столкнуться с изучением параллельных вычислений и в частности 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. В поток вывода отправляется также и отмеренное нашим таймером значение времени в милисекундах.

Листинг кода

Программа написана на С++, будем считать что аргументы для выполнения передаются из внешней оболочки. Код выглядит следующим образом:
#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.

Вывод

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

Tags:
Hubs:
Total votes 37: ↑32 and ↓5 +27
Views 82K
Comments Comments 29