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

Описание свойств и структуры алгоритма

Словесное описание алгоритма

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

Математическое описание

Исходные данные: одномерный массив [math]\displaystyle{ N }[/math] чисел.

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

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

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

[math]\displaystyle{ S_i = \sum_{j = 1}^k x_{k (i - 1) + j} }[/math]

На [math]\displaystyle{ p }[/math]-м процессоре последовательно вычисляется сумма элементов массива, начиная с [math]\displaystyle{ (p - 1) k + 1 }[/math]-го до [math]\displaystyle{ (p - 1) k + q }[/math]-го.

[math]\displaystyle{ S_p = \sum_{j = 1}^q x_{k (p - 1) + j} }[/math]

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

[math]\displaystyle{ \sum_{i = 1}^p S_i }[/math]

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

Вычислительное ядро последовательно-параллельного метода суммирования можно составить из множественных (всего [math]\displaystyle{ p }[/math]) вычислений сумм элементов массива:

[math]\displaystyle{ S_i = \sum_{j = 1}^k x_{k (i - 1) + j} }[/math]

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

[math]\displaystyle{ \sum_{i = 1}^p S_i }[/math]

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

Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего [math]\displaystyle{ p + 1 }[/math]) вычисления сумм

[math]\displaystyle{ S_i = \sum_{j = 1}^k x_{k (i - 1) + j} }[/math]

[math]\displaystyle{ \sum_{i = 1}^p S_i }[/math]

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

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

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

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

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

Опишем граф алгоритма в виде рисунка. В данном случае выполнено суммирование 30 элементов массива.

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

Для суммирования массива порядка [math]\displaystyle{ n }[/math] последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:

• [math]\displaystyle{ k - 1 }[/math] ярусов суммирования по частям массива ([math]\displaystyle{ p }[/math] ветвей),
• [math]\displaystyle{ p - 1 }[/math] ярусов суммирования (одна последовательная ветвь).

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

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

Описание входных и выходных данных

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

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

Объём входных данных: [math]\displaystyle{ N }[/math].

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

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

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является корнем квадратным (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 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

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

Описание локальности данных и вычислений

Описание локальности реализации алгоритма

Описание структуры обращений в память и качественная оценка локальности

Рисунок 12.1. Суммирование элементов массива. Общий профиль обращений в память

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

Фрагмент 2 устроен очень просто и представляет собой последовательный перебор всех элементов массива. Фрагмент 1 состоит из двух одинаковых переборов элементов массива, что хорошо видно из рис. 12.2, где данный фрагмент рассмотрен отдельно.

Рисунок 12.2. Фрагмент 1 (профиль обращений к первому массиву)

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

Количественная оценка локальности

Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

На рисунке 12.3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что значение данной оценки достаточно высоко и близко к последовательно-параллельному скалярному произведению двух векторов, что является закономерным вследствие однотипности структуры выполняемых операций.

Рисунок 12.3. Сравнение значений оценки daps

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

На рисунке 12.4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, локальность профиля достаточно высока, что коррелирует со значением оценки daps.

Рисунок 12.4. Сравнение значений оценки cvg

Существующие реализации алгоритма

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