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

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

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

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

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

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

Исходные данные: одномерный массив $n$ чисел.

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

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

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

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

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

Как уже записано в описании ядра алгоритма, основную часть метода составляют элементарные бинарные (всего $\frac{n}{2} log_2 n$) вычисления сумм.

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

В описанном виде суммирование сдваиванием не используют при последовательной реализации, поскольку кроме усложнения общей схемы алгоритма и резкого роста потребности в памяти, нужной для хранения промежуточных данных, сам по себе алгоритм содержит подавляющее большинство избыточных вычислений: по сравнению с последовательным алгоритмом нахождения частных сумм количество операций больше в $\frac{1}{2} log_2 n$ раз.

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

Для вычисления суммы массива, состоящего из $n$ элементов, количество операций равно $\frac{n}{2} log_2 n$. Поэтому алгоритм должен быть отнесён к алгоритмам линейно-логарифмической сложности по количеству последовательных операций.

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

Рисунок 1. Граф алгоритма при n=16 c отображением входных данных. Чёрными обозначены операции, результаты которых нужны на выходе алгоритма. Все вершины соответствуют операции сложения

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

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

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

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

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

Объём входных данных: $n$.

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

Объём выходных данных: $n$.

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

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