|
|
| (не показаны 2 промежуточные версии этого же участника) |
| Строка 1: |
Строка 1: |
| = Последовательно-параллельный метод суммирования =
| |
|
| |
|
| == Свойства и структура алгоритма ==
| |
|
| |
| === Общее описание алгоритма ===
| |
|
| |
| '''Последовательно-параллельный метод''' используется в качестве эрзаца блочной реализации вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря следующим особенностям: а) реализует приём получения двойных циклов из одинарных; б) в последовательной архитектуре компьютеров позволял для ряда операций уменьшать влияние округления на результат. Здесь будем описывать его версию для суммирования чисел.
| |
|
| |
| === Математическое описание алгоритма ===
| |
|
| |
| Исходные данные: одномерный массив <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 < 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>
| |
|
| |
| === Вычислительное ядро алгоритма ===
| |
|
| |
| Вычислительное ядро последовательно-параллельного метода суммирования можно составить из множественных (всего <math>p</math>) вычислений сумм элементов массива:
| |
| :<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>
| |
|
| |
| и ещё одного вычисления суммы элементов частичных сумм
| |
| :<math>\sum_{i = 1}^p S_i</math>
| |
|
| |
| === Макроструктура алгоритма ===
| |
|
| |
| Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего <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>
| |
|
| |
| === Схема реализации последовательного алгоритма ===
| |
|
| |
| Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).
| |
|
| |
| === Последовательная сложность алгоритма ===
| |
|
| |
| Для вычисления суммы массива, состоящего из <math>N</math> элементов, при любых разложениях <math>N</math> суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно <math>N - 1</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной'' сложности по количеству последовательных операций.
| |
|
| |
| === Информационный граф ===
| |
|
| |
| На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 30 элементов массива.
| |
|
| |
| [[file:series-parallel summation graph.png|center|thumb|600px|Рисунок 1. Последовательно-параллельный метод суммирования массива]]
| |
|
| |
| === Описание ресурса параллелизма алгоритма ===
| |
|
| |
| Для суммирования массива порядка <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>.
| |
|
| |
| При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью ''корень квадратный''. При классификации по ширине ЯПФ его сложность будет такой же — ''корень квадратный''.
| |
|
| |
| === Входные и выходные данные алгоритма ===
| |
|
| |
| Входные данные: массив <math>\vec{x}</math> (элементы <math>x_i</math>).
| |
|
| |
| Дополнительные ограничения: отсутствуют.
| |
|
| |
| Объём входных данных: <nowiki/><math>N</math>.
| |
|
| |
| Выходные данные: сумма элементов массива.
| |
|
| |
| Объём выходных данных: один скаляр.
| |
|
| |
| === Свойства алгоритма ===
| |
|
| |
| Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''корнем квадратным'' (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа локальны.
| |
|
| |
| == Литература ==
| |
| <references />
| |