Разработка сложных параллельных программ на языке MC#

Цель - изучить параллельный алгоритм вычисления частичных сумм массива чисел и реализовать его на языке MC#.

На данном занятии, требуется реализовать программу на языке MC#, решающую задачу вычисления частичных сумм массива f длины n.

А именно, по заданному массиву чисел f [ 0 : n-1 ] необходимо построить массив h [ 0 : n-1 ], такой что

Идея параллельного решения этой задачи состоит в разбиении массива f на p сегментов, где n кратно p, с дальнейшей одновременной обработкой этих сегментов данных длины m = n div p. Таким образом, обработка каждого сегмента будет производиться movable -методом.

(Отметим, что приведенное ниже решение пригодно и для случая, когда n не кратно p. Соответствующее обобщение может рассматриваться в качестве упражнения).

Разбиение исходного массива f на p сегментов производится таким образом, что в сегмент q, где ( 0 <= q < p ) попадают элементы f [ i ], такие что i mod p = q.

Так, например, если n = 16 и p = 4, то

0 -ой сегмент составят числа f [ 0 ], f [ 4 ], f [ 8 ], f [ 12 ] ;

1 -ый сегмент составят числа f [ 1 ], f [ 5 ], f [ 9 ], f [ 13 ]

и т.д.

Параллельный алгоритм вычисления частичных сумм будет устроен так, что q -му процессу ( movable -методу), обрабатывающему q -ый сегмент данных, достаточно будет общаться лишь с его соседями слева и справа (соответственно, 0 -му процессу - лишь с соседом справа, а последнему, (p-1) -му процессу - лишь с соседом слева) и главной программой для возврата результатов. Процесс с номером q будет вычислять все элементы h [j] результирующего массива, такие что j mod p = q, где 0 <= j < n.

Фрагмент главной программы, разбивающей исходный массив на сегменты и вызывающий movable -метод handleSegment, показан ниже. Здесь первым аргументом этого метода является номер сегмента, а последним - имя канала для возврата результатов.

Объекты класса BDChannel объявляются следующим образом :

Схема взаимодействия процессов ( movable -методов) между собой и главной программой показана ниже:

После разбиения, исходный массив f приобретает вид двумерной матрицы, распределенной по p процессам:

Другими словами, эта матрица получена из массива f разрезанием его на p сегментов и транспонированием каждого сегмента.

Ключевая идея алгоритма отдельного процесса q состоит в заполнении локальных для него массивов h0 и h1 (оба, имеющие размерность m ) в соответствии с формулами:

Неформально, это означает, что для процесса с номером q i -ый элемент массива h0 есть сумма всех элементов приведенной выше матрицы, которые расположены выше и слева элемента aq,i (включая и элементы столбца i ).

Аналогично, i -ый элемент массива h1 есть сумма всех элементов матрицы, которые расположены ниже и слева элемента aq,i (но, не включая элементов из столбца i ).

Ниже показана иллюстрация этого принципа для n = 16, p = 4 и q = 1, i = 2.

После того, как вычислены массивы h0 и h1 (посредством взаимодействия с соседними процессами), процесс с номером q может вычислить элемент h[i * p + q] результирующего массива как

Получаемые результирующие m значений процесс q сохраняет в локальном массиве h для передачи их главной программе. Тогда общая схема movable -метода handleSegment выглядит следующим образом:

Фрагмент программы, вычисляющий массив h0, приведен ниже.