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

Нахождение суммы элементов массива сдваиванием
Последовательный алгоритм
Последовательная сложность	$n-1$
Объём входных данных	$n$
Объём выходных данных	$1$
Параллельный алгоритм
Высота ярусно-параллельной формы	$log2n$
Ширина ярусно-параллельной формы	$n/2$

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

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

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

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

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

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

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

Формулы метода: элементы на каждом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.

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

Вычислительное ядро метода сдваивания для суммирования можно составить как из элементарных бинарных (всего $n - 1$) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.

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

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

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

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

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

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

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

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

Рисунок 1. Суммирование массива методом сдваивания

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

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

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

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

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

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

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

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

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

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