Последовательно-параллельный метод суммирования

Последовательно-параллельный метод суммирования
Последовательный алгоритм
Последовательная сложность	$n-1$
Объём входных данных	$n$
Объём выходных данных	$1$
Параллельный алгоритм
Высота ярусно-параллельной формы	$O(\sqrt{n})$
Ширина ярусно-параллельной формы	$O(\sqrt{n})$

Основные авторы описания: А.В.Фролов.

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Последовательно-параллельный метод используется в качестве эрзаца блочной реализации вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря следующим особенностям: а) реализует приём получения двойных циклов из одинарных; б) в последовательной архитектуре компьютеров позволял для ряда операций уменьшать влияние округления на результат. Здесь будем описывать его версию для суммирования чисел.

1.2 Математическое описание алгоритма

Исходные данные: одномерный массив $N$ чисел.

Вычисляемые данные: сумма элементов массива.

Формулы метода: число $N$ разлагается в выражение типа $N = (p - 1) k + q$, где $p$ — количество процессоров, $k = \lceil \frac{N}{p} \rceil$, $q = N - k (p - 1)$.

После этого на $i$-м процессоре ($i \lt p$) последовательно вычисляется сумма элементов массива, начиная с $(i - 1) k + 1$-го, до $i k$-го.

$S_i = \sum_{j = 1}^k x_{k (i - 1) + j}$

На $p$-м процессоре последовательно вычисляется сумма элементов массива, начиная с $(p - 1) k + 1$-го до $(p - 1) k + q$-го.

$S_p = \sum_{j = 1}^q x_{k (p - 1) + j}$

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

$\sum_{i = 1}^p S_i$

1.3 Вычислительное ядро алгоритма

Вычислительное ядро последовательно-параллельного метода суммирования можно составить из множественных (всего $p$) вычислений сумм элементов массива:

$S_i = \sum_{j = 1}^k x_{k (i - 1) + j}$

и ещё одного вычисления суммы элементов частичных сумм

$\sum_{i = 1}^p S_i$

1.4 Макроструктура алгоритма

Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего $p + 1$) вычисления сумм

$S_i = \sum_{j = 1}^k x_{k (i - 1) + j}$

$\sum_{i = 1}^p S_i$

1.5 Схема реализации последовательного алгоритма

Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).

1.6 Последовательная сложность алгоритма

Для вычисления суммы массива, состоящего из $N$ элементов, при любых разложениях $N$ суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно $N - 1$. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.

1.7 Информационный граф

На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 24 элементов массива.

Рисунок 1. Последовательно-параллельный метод суммирования массива

Интерактивное изображение графа алгоритма без входных и выходных данных для случая суммирования 20 элементов массива

1.8 Описание ресурса параллелизма алгоритма

Для суммирования массива порядка $n$ последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:

• $k - 1$ ярусов суммирования по частям массива ($p$ ветвей),
• $p - 1$ ярусов суммирования (одна последовательная ветвь).

Таким образом, в параллельном варианте критический путь алгоритма (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае ($p = \sqrt{n}$) высота ЯПФ будет равна $2 \sqrt{n} - 2$.

При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью корень квадратный. При классификации по ширине ЯПФ его сложность будет такой же — корень квадратный.

1.9 Входные и выходные данные алгоритма

Входные данные: массив $\vec{x}$ (элементы $x_i$).

Дополнительные ограничения: отсутствуют.

Объём входных данных: $N$.

Выходные данные: сумма элементов массива.

Объём выходных данных: один скаляр.

1.10 Свойства алгоритма

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является корнем квадратным (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 1 (входных и выходных данных столько же, сколько операций). При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа локальны.

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

В простейшем (без перестановок суммирования) варианте на Фортране можно записать так:

	DO  I = 1, P
		S (I) = X(K*(I-1)+1)
		IF (I.LQ.P) THEN
			DO J = 2,K
				S(I)=S(I)+X(K*(I-1)+J)
		             END DO
		ELSE
			DO J = 2,Q
				S(I)=S(I)+X(K*(I-1)+J)
		             END DO
		END IF
	END DO
	SUM = S(1)
	DO I = 2, P
		SUM = SUM + S(I)
	END DO

Можно записать и аналогичные схемы, где суммирование будет проводиться в обратном порядке. Подчеркнём, что граф алгоритма обеих схем — один и тот же!

2.2 Возможные способы и особенности параллельной реализации алгоритма

В чистом виде алгоритм последовательно-параллельного метода для суммирования массива встречается редко, в основном встречаются его модификации, например для случаев вычисления скалярного произведения (вместо элементов массива будут фигурировать произведения элементов двух массивов), равномерной нормы (вместо элементов массива — их модули) и т. п. В случае вычисления скалярного произведения в одном из частных случаев подобный приём применён в библиотеке BLAS (там одна из размерностей равна 5), но, видимо, не для распараллеливания, а для оптимизации работы с регистрами процессора. Между тем, разбиения массивов на группы для вычислений частных сумм могут быть полезны и для лучшего использования кэша на отдельных узлах.