Участник:Bannikov Nikolay/Каскадная схема суммирования
Свойства и структура алгоритма
Общее описание алгоритма
Каскадная схема суммирования представляет собой алгоритм поэтапного (многоуровневого) сложения нескольких числовых величин, организованных в каскадную структуру. Основная идея заключается в том, что входные данные (слагаемые) группируются и суммируются последовательно на каждом уровне каскада, а полученные промежуточные результаты передаются на следующий уровень для дальнейшего суммирования.
Такая организация позволяет повысить быстродействие за счёт параллельного выполнения частичных сумм и уменьшения задержек при обработке больших массивов данных. Каскадная схема часто используется в цифровых вычислительных устройствах и системах обработки сигналов, где требуется эффективное выполнение операций сложения большого числа аргументов.
Математическое описание алгоритма
Пусть имеется набор входных данных: $$X = \{x_1,x_2,...,x_n\} $$
Необходимо найти их сумму: $$S = \sum_{i=1}^n x_i$$
В каскадной схеме процесс выполняется в несколько уровней. На каждом уровне производится суммирование попарных элементов предыдущего уровня.
На первом уровне формируются частичные суммы $$y_{j}^{(1)} = x_{2j-1} + x_{2j}, \quad j = 1,2,...\frac{n}{2}$$
На втором уровне — суммы результатов первого уровня $$y_{k}^{(2)} = y_{2k-1}^{(1)} + y_{2k}^{(1)}, \quad k = 1,2,...\frac{n}{4}$$
И так далее, пока не останется одно значение — итоговая сумма $$S = y_1^{(m)}, \quad где \ m = \log_{2} n$$
Программная реализация алгоритма
Литература
- А.В.Старченко, В.Н.Берцун. Методы параллельных вычислений. Изд-во Том. ун-та, 2013. - 223 с. (Серия "Суперкомпьютерное образование")