Схема параллельного суммирования

Реализация суммирования на некоторых параллельных вычислительных системах 

 Помимо общих  слов о том, что ряд библиотек  пакетов, предназначенных для  параллельной реализации, содержит  специальные подпрограммы суммирования, остановимся на двух примерах  реализаций: под средой MPI, предназначенной для кластерной архитектуры, и на языке Colamo (для ПЛИСов). Упомянем только, что суммирование не очень хорошо ложится на конвейерную архитектуру, на которой, пожалуй, самой быстрой будет векторная реализация иерархически-последовательных схем.

Реализация под  средой MPI

 Программирующие  в среде обмена сообщениями  MPI, конечно, могут использовать  вышеприведённые схемы суммирования  массива, распределённого по секциям  памяти разных узлов кластера, самостоятельно, с помощью подпрограмм пересылки сообщений. Однако сами такие сообщения окажутся (для любой из выбранных схем) очень короткими, что при недостаточном опыте программиста отрицательно скажется на производительности системы. Поэтому разработчики среды предусмотрели выполнение массовых операций с помощью специальных подпрограмм, в которых уже заложены пересылки, не самым худшим образом оптимизированные под среду. Это - две подпрограммы: MPI_Allreduce и MPI_Reduce. Различаются они только тем, что во второй подпрограмме результат получает только один из узлов MPI, а не все (как в первой). Что показательно, подпрограммы эти могут выполнять не только суммирование массива, но и три других массовых операции по всему массиву: вычисление минимума, максимума и произведения. Для тех читателей, что заинтересовались данной страницей о суммировании в связи с универсальностью его вычислительных схем, данная новость обладает двойственным характером. С одной стороны, для описанных простых операций это хорошо, и неопытные в MPI программисты могут пользоваться ими. Однако то, что в списке базовых операций для этих подпрограмм отсутствуют более сложные (скалярное произведение, матричное умножение и т.п.), означает, что для этих операций надо будет писать реализации описанных выше схем с помощью ручного программирования и программ пересылки сообщений. Что, однако, будет в отношении замедления производительности (как, впрочем, и для описанных четырёх операций) уже не таким критичным, поскольку при выполнении более сложных операций матричного типа длина сообщений существенно увеличится, а главное - увеличится ещё больше доля "арифметики" между межузловыми обменами данных.  
 

 Но главное  - то, что даже в отношении указанных  4 операций (*, +, max, min) опытные программисты  под MPI с помощью умелого группирования выполняют масовые суммирования (умножения и др.) без использования этих двух подпрограмм не медленнее, а даже несколько быстрее, чем с их использованием.

Реализация на ПЛИСах 

 При реализации  на языке Коламо для ПЛИСов  важен такой вопрос, как планирование ресурсов, которые будут отведены на реализацию задачи. В качестве примера приведём программу, реализующую пирамидально-конвейерную схему с использованием 16 сумматоров:

 Program Piramida_Summatorov;

include MyLibNewElement; 

VAR a : array real [16:vector, 100:stream] mem;

VAR res : real mem;

VAR i, j, k, l, m, n, s, kk, vect, vectd2 : number;

VAR cm1, cm2, cm3, cm4, cm5, cm6 : real com;

VAR c : array real [8:vector, 8:vector] com;

VAR rg : real reg; 

Define vect=16;

Define vectd2=7;//vect/2-1

Define n=100;

Define m=3;

Define k=0;

Define kk=0;

Define l=8;//vect/2 

Cadr ev;

for s:=0 to n-1 do

begin

     for i:=0 to vectd2 do

     begin

         c[0,i]:=a[k,s]+a[k+1,s];

         k:=k+2;

     end;

     for j:=1 to m do

     begin

         kk:=0;

         l:=l/2;

         for i:=0 to l-1 do

         begin

             c[j,i]:=c[j-1,kk]+c[j-1,kk+1];

             kk:=kk+2;

         end;

     end;

     rg:=rg+c[m,vectd2];

end;

res:=rg;

EndCadr;

End_Program.  

 Эта программа реализует каскадно-пирамидальную схему с использованием конвейеризации.