Приложение 7
Последовательно-параллельный метод суммирования
Свойства и структура алгоритма
Общее описание алгоритма
Последовательно-параллельный метод используется в качестве эрзаца блочной реализации вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря следующим особенностям: а) реализует приём получения двойных циклов из одинарных; б) в последовательной архитектуре компьютеров позволял для ряда операций уменьшать влияние округления на результат. Здесь будем описывать его версию для суммирования чисел.
Математическое описание алгоритма
Исходные данные: одномерный массив [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]. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.
Информационный граф
На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 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 (входных и выходных данных столько же, сколько операций). При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа локальны.