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

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

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 Макроструктура алгоритма

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

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

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

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

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

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

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

Граф алгоритма изображён на рисунке.

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

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

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

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

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

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

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

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

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

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

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

Сдваивание, из-за сильной избыточности вычислений, вряд ли может быть применено на компьютерах без параллельных устройств.

2.2 Возможные способы и особенности параллельной реализации алгоритма

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

Как видно по графу алгоритма, ряд дуг длинны как по времени (по различию номеров ярусов операций, являющихся началом и концом дуги), так и по пространству (исключением является только размещение в гиперкубе, физически невозможное). Эта неустранимая нелокальность должна тормозить исполнение всех аналогичных алгоритмов.

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

2.4 Выводы для классов архитектур

Из-за своеобразия графа сдваивания лучше всего он отображается на архитектуру типа "гиперкуб". Поэтому для архитектур с массовым параллелизмом представляется неизбежным рост накладных расходов и слабая масштабируемость алгоритма.