РЕАЛИЗАЦИЯ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА СУММИРОВАНИЯ ПОСРЕДСТВОМ BOOST.MPI

Одной из актуальных задач является задача распараллеливания. Параллельные методы вычислений позволяют добиться оптимального времени выполнения поставленных задач. Особый интерес представляет малоизученная библиотека Boost.MPI для С++, как простой и гибкий инструмент распараллеливания.

Постановка задачи.

С помощью библиотеки Boost.MPI параллельно вычислить сумму телескопического ряда. И установить зависимость время работы от числа процессов.

Реализация.

Сначала следует поставить Boost и MPI, а также OpenMPI. Компиляция и запуск программы с названием mpi-boost.cpp, например на 2-х процессах, производится с помощью команд:

->mpic++ -o mpi-boost mpi-boost.cpp -lboost_mpi

->mpirun -np 2 ./mpi-boost

Первым шагом в написании программы является создание mpi::invironment объекта, с аргументами указанными в функции main(). Взаимодействие с MPI всегда осуществляется через коммуникатор, который должен быть создан как объект типа mpi::comunicator[1]. Этот коммуникатор может показать сколько процессов запущено ("size") и также присваивает уникальный номер каждому процессу от нуля до размера коммуникатора ("rank").

При этом в заголовке программы подключаются:

#include <boost/mpi/environment.hpp>

#include <boost/mpi/communicator.hpp>

Производится создание объектов в начале работы:

int main(intargc, char* argv[]){

mpi::environmentenv(argc, argv);

mpi::communicatorworld;

Получить ранг процесса и их количество можно таким образом:

rank=world.rank();

size=world.size();

Итак, нам нужно вычислить сумму телескопического ряда, которая имеет вид

                                           (1)

А именно проверить его сходимость к единице. Чтобы распараллелить вычисление суммы, каждый процесс будет вычислять только члены ряда начиная со своего номера, т.е. с rank+1 и через число процессов, т.е. через size и находить только их сумму.

for(i=rank+1; i<=n; i+=size)

sc+=1./(i*(i+1.));

Далее эти суммы с каждого процесса необходимо просуммировать.Для этого мы воспользуемся коллективной операцией Reduce [2]. Которая выполняет операцию со  значением переменной от каждого процесса и заносит в новую переменную полученный результат, который хранится на специальном корневом процессе. В нашем случае данным корневым процессом будет являться процесс с рангом 0. Для нахождения итоговой суммы ряда воспользуемся операцией суммирование сумм, полученных с каждого процесса. Данная операция обозначается std::plus.

Для использования reduce и std::plus следует подключить в заголовке программы:

#include <boost/mpi/collectives.hpp>

#include <boost/mpi/operations.hpp>

Если sc- сумма значений одного или нескольких членов члена, а s - сумма ряда, и world - коммуникатор, то вызов функции reduce выглядит следующим образом:

mpi::reduce(world,sc,s,std::plus<double>(),0);

Точность суммы ряда зависит от количества членов ряда. Продемонстрируем это на примере:

n = 10, summ = 0.909091

n = 100, summ = 0.990099

n = 1000, summ = 0.999001

n = 10000, summ = 0.9999

n = 100000, summ = 0.99999

n = 1000000, summ = 0.999999

n = 10000000, summ = 1

Итак, при большом числе членов ряда сумма стремится к точному значению равному 1.

Для того, чтобы вычислить время выполнения суммирования надо создать объект типа mpi::timer, для этого надо подключить в заголовке файла:

#include <boost/mpi/timer.hpp>

Запуск таймера производится командой:

timer.restart();

а получение времени в секундах с момента запуска:

time=timer.elapsed();

С помощью функции elapsed_min(), возвращающая минимальное ненулевое значение, которое функция elapsed() [2] может вернуть, можно получить погрешность вычисления времени:

pogr=timer.elapsed_min();

Итак, программа должна выдавать итоговую сумму ряда, время работы и погрешность измерений. Но это надо делать только для процесса с рангом 0, т.к. итоговая сумма храниться именно на нем:

if (rank==0) std::cout<< "summ = "<< s << ", time = " << time

<< ", pogr = " <<pogr<<std::endl;

Полный код приведен ниже:

1.  #include <boost/mpi/environment.hpp>

2.  #include <boost/mpi/communicator.hpp>

3.  #include <boost/mpi/timer.hpp>

4.  #include <boost/mpi/collectives.hpp>

5.  #include <boost/mpi/operations.hpp>

6.  #include <iostream>

7.   

8.  namespace mpi = boost::mpi;

9.   

10.   intmain(intargc, char* argv[]){

11.   mpi::environment env(argc, argv);

12.   mpi::communicator world;

13.   int rank, size, i,n=10000000;

14.   double s=0.0,sc=0.0, time=0.0, pogr=0.0;

15.   rank=world.rank();

16.  size=world.size();

17.  mpi::timer timer;

18.  pogr=timer.elapsed_min();

19. timer.restart();

20. for(i=rank+1; i<=n; i+=size)

21. sc+=1./(i*(i+1.));

22. mpi::reduce(world,sc,s,std::plus<double>(),0);

23.  time=timer.elapsed();

24.  if (rank==0) std::cout<< "summ = "<< s <<

     ", time = " << time << ", pogr = " <<pogr<<std::endl;

25.    return 0;

26.   }

Нам осталось установить зависимость времени выполнения от количества процессов. Протестируем программу на 1, 2 и 3 процессах:

maria@hp:~/Boost.MPI$ mpirun -np 1 ./mpi-boost

summ = 1, time = 0.922882, pogr = 1e-06

maria@hp:~/Boost.MPI$ mpirun -np 2 ./mpi-boost

summ = 1, time = 0.553266, pogr = 1e-06

maria@hp:~/Boost.MPI$ mpirun -np 3 ./mpi-boost

summ = 1,time = 0.539136, pogr = 1e-06

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

Таким образом, после проведенного исследования была выявлена обратная зависимость времени выполнения от числа процессов. При увеличении числа процессов время уменьшается.

Список литературы:

1. Boost.MPI— [Электронный ресурс] — Режим доступа. — URL: http: //www.boost.org/doc/libs/1_60_0/doc/html/mpi.html (дата обращения 05.01.2016)

2. Douglas Gregor, Matthias Troyer, Boost.MPIVersion 1.0. /Douglas Gregor, Matthias Troyer // Trustees of Indiana University. — 2005-2007. — A 133.