Приложение 7

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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