Исследование алгоритмов коллективных обменов информацией между ветвями параллельных программ в распределенных вычислительных системах

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Алгоритмы трансляционно-циклических обменов информацией в распределенных ВС

1.1 Трансляционно-циклический обмен информацией в распределенных ВС

1.2 Алгоритм Bruck

1.3 Выводы

2. Экспериментальное исследование эффективности алгоритма

2.1 Организация моделирования

2.2 Результаты моделирования

Заключение

Список использованных источников

Приложение 1. Исходный текст программы

Введение

Начиная с середины 1960-х годов распределенные вычислительные системы (ВС) активно используются как инструментальные средства решения сложных задач в различных отраслях науки и техники. В архитектурном плане распределенная ВС представляется композицией множества взаимодействующих элементарных машин (оснащенных средствами коммуникаций и внешними устройствами) и сети межмашинных связей [1, 2]. Элементарная машина (ЭМ) - это основной функциональный и структурный элемент ВС; конфигурация ЭМ допускает варьирование в широких пределах - от процессорного ядра до ЭВМ. Все основные ресурсы распределенных ВС (арифметико-логические устройства, память, средства управления и коммуникаций) являются логически и технически рассредоточенными. Число ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч.

Параллельные алгоритмы и программы для распределенных ВС преимущественно разрабатываются в модели передачи сообщений (Message Passing). В этой модели ветви параллельной программы взаимодействуют друг с другом путем обменов информационными сообщениями по каналам межмашинных связей ВС. Выделяют два типа обменов информацией между ветвями параллельных программ [1]: дифференцированный (point-to-point) и коллективные (collective) обмены. При дифференцированном обмене осуществляется передача информации из одной ветви в любую другую ветвь. Коллективные обмены подразделяются на несколько видов: трансляционный (ТО, One-to-all Broadcast), трансляционно-циклический (ТЦО, All-to-all Broadcast) и коллекторный обмены (КО, All-to-one broadcast). При трансляционном обмене данные из одной ветви передаются во все остальные; при трансляционно-циклическом обмене информация из ветвей передается каждой ветви и принимается из всех; коллекторный обмен подразумевает прием информации из всех ветвей в одну.

Анализ использования в параллельных алгоритмах и программах коллективных обменов показывает, что суммарное время их выполнения достигает 45% времени выполнения программ. Как правило, количество обращений в алгоритмах и программах к коллективным операциям обменов имеет функциональную зависимость от размера входных данных.

В настоящее время в коммуникационных библиотеках стандарта MPI и системах параллельного программирования для реализации коллективных обменов используются алгоритмы рассылки данных по кольцу, рекурсивного сдваивания, алгоритм Дж. Брука (J. Bruck) и алгоритмы, упорядочивающие ветви в деревья различных видов. Перечисленные алгоритмы характеризуются различным временем выполнения и опираются на предположение об однородности каналов связи между ЭМ распределенных ВС. вычислительный алгоритм кластер bruck

Цель работы - исследовать эффективность реализации заданного алгоритма коллективного обмена информацией между ветвями параллельных программ в распределенных ВС.

1. Алгоритмы трансляционно-циклических обменов информацией в распределенных ВС

1.1 Трансляционно-циклический обмен информацией в распределенных ВС

При реализации ТЦО каждая ветвь i ? {0, 1, …, n?1} параллельной программы располагает локальным сообщением ai размером m байт. Требуется отправить сообщение ai всем ветвям и получить сообщения от каждой. По окончанию ТЦО все ветви должны содержать в своей памяти n сообщений a0,a1,...,an-1, упорядоченных по номерам ветвей, которым они принадлежат (рис. 1).

Рис. 1. Пример реализации ТЦО (n = 4): а - начальное состояние ветвей, б - конечное состояние ветвей;

1.2 Алгоритм Bruck

Алгоритм Дж. Брука (J. Bruck) допускает реализацию ТЦО для произвольного количества n параллельных ветвей.

На шаге k = 0, 1, …, log2n ?1 ветвь i передает все принятые сообщения ветви (i-2k+n)mod n и принимает сообщения от ветви (i+2k)mod n. Сообщения размещаются в памяти со смещением, поэтому по окончании работы алгоритма каждая ветвь i циклически сдвигает сообщения на i позиций вниз (рис. 2).

Рис. 2 - Реализация ТЦО алгоритмом Дж. Брука (n = 6): а - начальное состояние ветвей; б - шаг 0; в - шаг 1; г - шаг 2; д - сдвиг сообщений.

1.3 Выводы

Объёмы данных, передаваемых между ветвями параллельной программы при реализации ТЦО алгоритма Дж. Брука, различны. По этой причине время реализации ТЦО рассматриваемым алгоритмом в иерархических распределённых ВС зависит от того, как ветви параллельной программы распределены по элементарными машинам системы.

2. Экспериментальное исследование эффективности алгоритма

2.1 Организация моделирования

Моделирование проводилось на Кластере СибГУТИ - Jet укомплектованный 18 вычислительными узлами, с использованием MPICH2.

Узлы построены на базе серверной платформы Intel SR2520SAF. На каждом узле размещено два процессора Intel Quad Xeon E5420 с тактовой частотой 2.5 GHz. Пиковая производительность кластера - 1,44 TFLOPS.

Если количество вычислителей равно n, а размер сообщения равен m то алгоритм можно представить в виде псевдокода:

Procedure Bruck(buf)

dist = 1

while dist < n do

sendto = (rank - dist + n) % n;

recvfrom = (rank + dist) % n;

k = (dist <= (n / 2)) ? dist : n - dist;

SendRecv(buf,k * m, sendto, buf, k * m, recvfrom)

dist = dist * 2

end while

if rank > 0 then

/* Shift buf items */

end if

end procedure

2.2 Результаты моделирования

Результаты моделирования разработанного алгоритма приведены на Рисунке 3.1.



Рис. 3.1 Зависимость времени выполнения алгоритма от размера сообщения

На Рисунке 3.2 приведены графики для сравнения скорости выполнения разработанного алгоритма от стандартного алгоритма MPI_Allgather.

Рис. 3.2 Сравнение разработанного алгоритма и MPI_Allgather.

Заключение

В результате выполнения работы разработан и исследован алгоритм ТЦО - Allgather основанный на алгоритме Дж. Брука.

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

Список использованных источников

1. Хорошевский В.Г. Архитектура вычислительных систем. - М.: МГТУ им. Н.Э. Баумана,

2. 2008. - 520 с.

3. Евреинов Э.В., Хорошевский В.Г. Однородные вычислительные системы. - Новосибирск: Наука, 1978. - 320 с.

4. MPICH3 Source Code.

5. OpenMPI Source Code.

6. Khoroshevsky V., Kurnosov M. Mapping Parallel Programs into Hierarchical Distributed Computer Systems // Proc. of "Software and Data Technologies". Sofia: INSTICC, 2009. Vol. 2. P. 123_128.

Приложение 1. Исходный текст программы

/*

* coll.c:

*

*/

#include <stdlib.h>

#include <mpi.h>

#include "mpiddtypes.h"

enum {

ALLGATHER_TAG = 128

};

/*

* allgather_bruck: Bruck's algorithm for Allgather [*].

*

* Communications: O(ceil(log2(N))), where N is a number of processes.

* Memory consumption: temporary buffer O(N) is used for local shift data.

*

* [*] J. Bruck et. al. Efficient Algorithms for All-to-All Communications in

* Multiport Message-Passing Systems // IEEE Trans. Parallel Distrib.

* Syst. - 1997. - Vol. 8, No.11. - P. 1143-1156.

*/

int allgather_bruck(void *sendbuf, int sendcount, MPI_Datatype sendtype,

void *recvbuf, int recvcount, MPI_Datatype recvtype,

MPI_Comm comm)

{

int rc, rank, commsize;

MPI_Aint recvlb, recvextent;

int rbufsize, nblocks, dist, recvfrom, sendto;

char *sbuf, *rbuf, *rbuftmp;

PMPI_Comm_size(comm, &commsize);

PMPI_Comm_rank(comm, &rank);

if (comm == MPI_COMM_NULL)

return MPI_ERR_COMM;

rc = PMPI_Type_get_true_extent(recvtype, &recvlb, &recvextent);

RETURN_ON_MPIERR(rc);

/* Allocate memory for receive buffer */

rbufsize = commsize * recvcount * recvextent;

if ((rbuftmp = malloc(sizeof(*rbuftmp) * rbufsize)) == NULL)

return 1;

/* Copy initial data to send buffer */

if (sendbuf != MPI_IN_PLACE) {

/* Copy sendbuf to block 0 of recvbuf */

rc = mpiddtype_copylocal(sendbuf, sendcount, sendtype, rbuftmp,

recvcount, recvtype);

} else {

/*

* Sendbuf and sendtype are ignored.

* Copy data from rank-th block of recvbuf to block 0.

*/

if (rank != 0) {

rc = mpiddtype_copylocal((char *)recvbuf +

rank * recvcount * recvextent,

recvcount, recvtype, rbuftmp, recvcount,

recvtype);

}

}

RETURN_ON_MPIERR(rc);

/*

* On each step send data to process (i - 2^k + n) % n and receive data

* from process (i + 2^k) % n. Number of blocks on each step is doubled.

* Total number of steps is ceil(log2(N)), where N is a number of processes.

*/

nblocks = 1;

sbuf = (char *)rbuftmp;

for (dist = 1; dist < commsize; dist *= 2) {

sendto = (rank - dist + commsize) % commsize;

recvfrom = (rank + dist) % commsize;

nblocks = (dist <= (commsize / 2)) ? dist : commsize - dist;

rbuf = sbuf + dist * recvcount * recvextent;

rc = PMPI_Sendrecv(sbuf, nblocks * recvcount, recvtype, sendto,

ALLGATHER_TAG, rbuf, nblocks * recvcount,

recvtype, recvfrom, ALLGATHER_TAG, comm,

MPI_STATUS_IGNORE);

RETURN_ON_MPIERR(rc);

}

/*

* Shift data.

* Copy blocks: 0, 1, ... commsize - rank to original recv buffer

*/

rc = mpiddtype_copylocal(rbuftmp, (commsize - rank) * recvcount, recvtype,

(char *)recvbuf + rank * recvcount * recvextent,

(commsize - rank) * recvcount, recvtype);

RETURN_ON_MPIERR(rc);

if (rank > 0) {

rc = mpiddtype_copylocal(rbuftmp +

(commsize - rank) * recvcount * recvextent,

rank * recvcount, recvtype, recvbuf,

rank * recvcount, recvtype);

RETURN_ON_MPIERR(rc);

}

free(rbuftmp);

return MPI_SUCCESS;

}

Test.c

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <mpi.h>

#include "coll.h"

int main(int argc, char **argv)

{

int commsize, rank, i;

int *sendbuf, *recvbuf;

int sendcount = 1024, recvcount;

double t0, t1;

MPI_Init(&argc, &argv);

MPI_Comm_size(MPI_COMM_WORLD, &commsize);

MPI_Comm_rank(MPI_COMM_WORLD, &rank);

if ((sendbuf = malloc(sizeof(*sendbuf) * sendcount)) == NULL) {

fprintf(stderr, "No enough memory for sendbuf.\n");

exit(EXIT_FAILURE);

}

recvcount = sendcount * commsize;

if ((recvbuf = malloc(sizeof(*recvbuf) * recvcount)) == NULL) {

fprintf(stderr, "No enough memory for recvbuf.\n");

exit(EXIT_FAILURE);

}

for(i=0;i!=sendcount;i++) sendbuf[i]=rank;

allgather_bruck(sendbuf, sendcount, MPI_INT,

recvbuf, sendcount, MPI_INT, MPI_COMM_WORLD);

t0 = MPI_Wtime();

allgather_bruck(sendbuf, sendcount, MPI_INT,

recvbuf, sendcount, MPI_INT, MPI_COMM_WORLD);

t1 = MPI_Wtime();

if(rank==0) printf("elapsed time == % lf\n",t1-t0);

free(sendbuf);

free(recvbuf);

MPI_Finalize();

return EXIT_SUCCESS;

}

Размещено на Allbest.ru