Нахождение частных сумм элементов массива сдваиванием

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

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

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

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

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

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

Вычисляемые данные: частичные суммы первых [math]i[/math] элементов массива, где [math]i[/math] принимает все значения от [math]1[/math] до [math]n[/math].

Формулы метода: элементы на первом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её соседних элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д. По нахождению тех частных сумм, где [math]i[/math] является степенью двойки, формулы повторяют Нахождение суммы элементов массива сдваиванием. Однако, кроме этого, для каждой пары (например, для нахождения суммы [math]x_i+...+x_{i+k}[/math] и [math]x_{i+k+1} +...+ x_{i+2k}[/math])дополнительно вычисляются все частные суммы от [math]x_i+...+x_{i+k+1}[/math] до [math]x_i+...+x_{i+2k-1}[/math].

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

Вычислительное ядро последовательно-параллельного метода суммирования можно составить из элементарных бинарных (всего [math]\frac{n}{2} log_2 n[/math]) вычислений сумм.

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

Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.

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

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

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

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

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

Опишем граф алгоритма в виде рисунка. В данном случае выполнено суммирование 16 элементов массива. Вершины , соответствующие входным данным - даны синим цветом , выходным данным - красным цветом.

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

Для суммирования массива порядка [math]n[/math] методом сдваивания в параллельном варианте требуется последовательно выполнить [math]\lceil \log_2 n \rceil[/math] ярусов с убывающим (от [math]\frac{n}{2}[/math] до [math]1[/math]) количеством операций суммирования. При классификации по высоте ЯПФ, таким образом, метод сдваивания относится к алгоритмам с логарифмической сложностью. При классификации по ширине ЯПФ его сложность будет линейной.

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

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

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

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

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

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

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является [math]\frac{n}{\log_2 n}[/math] (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 1 (входных и выходных данных столько же, сколько операций). При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.