Участник: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$$

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

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

На каждом уровне происходит одинаковая базовая операция: $$y=a+b$$ где [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] — либо исходные элементы, либо частичные суммы предыдущего уровня.
Вычислительное ядро включает:

• Формирование пар чисел
• Выполнение операции их сложения
• Передачу полученных частичных сумм на следующий уровень

Объем вычислительного ядра:

• Общее количество операций сложения: [math]\displaystyle{ n-1 }[/math]
• Количество уровней каскада: [math]\displaystyle{ \log_{2} n }[/math]
• Максимальное количество операций на уровне: [math]\displaystyle{ \frac{n}{2} }[/math]

Ключевые характеристики ядра:

• Регулярная структура - все операции однотипны (бинарное сложение)
• Локальность данных - на каждом уровне вычисления используют только результаты с предыдущего уровня
• Параллелизм - операции в пределах одного уровня независимы и могут выполняться параллельно

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

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

Описание изображения

Рис. 1 Диаграмма маршрутизации каскадной схемы суммирования

Литература

1. А.В.Старченко, В.Н.Берцун. Методы параллельных вычислений. Изд-во Том. ун-та, 2013. - 223 с. (Серия "Суперкомпьютерное образование")