Участник:Bannikov Nikolay/Каскадная схема суммирования - История изменений

Bannikov Nikolay в 01:35, 19 ноября 2025

2025-11-19T01:35:30Z

← Предыдущая версия		Версия от 01:35, 19 ноября 2025
Строка 18:		Строка 18:

	На каждом уровне происходит одинаковая базовая операция: $$y=a+b$$		На каждом уровне происходит одинаковая базовая операция: $$y=a+b$$
	где a и b — либо исходные элементы, либо частичные суммы предыдущего уровня.<br>		где <math>a</math> и <math>b</math> — либо исходные элементы, либо частичные суммы предыдущего уровня.<br>
	Вычислительное ядро включает:		'''Вычислительное ядро включает:'''
	* Формирование пар чисел		* Формирование пар чисел
	* Выполнение операции их сложения		* Выполнение операции их сложения
	* Передачу полученных частичных сумм на следующий уровень		* Передачу полученных частичных сумм на следующий уровень

	Объем вычислительного ядра:		'''Объем вычислительного ядра:'''
	* Общее количество операций сложения: $n-1$		* Общее количество операций сложения: <math>n-1</math>
	* Количество уровней каскада: $\log_{2} n$		* Количество уровней каскада: <math>\log_{2} n</math>
	* Максимальное количество операций на уровне: $\frac{n}{2}$		* Максимальное количество операций на уровне: <math>\frac{n}{2}</math>
	Ключевые характеристики ядра:
			'''Ключевые характеристики ядра:'''
	* Регулярная структура - все операции однотипны (бинарное сложение)		* Регулярная структура - все операции однотипны (бинарное сложение)
	* Локальность данных - на каждом уровне вычисления используют только результаты с предыдущего уровня		* Локальность данных - на каждом уровне вычисления используют только результаты с предыдущего уровня

Bannikov Nikolay в 01:29, 19 ноября 2025

2025-11-19T01:29:57Z

@@ Строка 12: / Строка 12: @@
 На втором уровне — суммы результатов первого уровня $$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 с. (Серия "Суперкомпьютерное образование")

Bannikov Nikolay: Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === '''Каскадная схема сумми...»

2025-11-04T00:17:06Z

Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === '''Каскадная схема сумми...»

Новая страница

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Каскадная схема суммирования''' представляет собой алгоритм поэтапного (многоуровневого) сложения нескольких числовых величин, организованных в каскадную структуру. Основная идея заключается в том, что входные данные (слагаемые) группируются и суммируются последовательно на каждом уровне каскада, а полученные промежуточные результаты передаются на следующий уровень для дальнейшего суммирования.

Такая организация позволяет повысить быстродействие за счёт параллельного выполнения частичных сумм и уменьшения задержек при обработке больших массивов данных. Каскадная схема часто используется в цифровых вычислительных устройствах и системах обработки сигналов, где требуется эффективное выполнение операций сложения большого числа аргументов.
=== Математическое описание алгоритма ===
Пусть имеется набор входных данных: $$X = \{x_1,x_2,...,x_n\} $$
Необходимо найти их сумму: $$S = \sum_{i=1}^n x_i$$
В каскадной схеме процесс выполняется в несколько уровней. На каждом уровне производится суммирование попарных элементов предыдущего уровня.
<br>
На первом уровне формируются частичные суммы $$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 с. (Серия "Суперкомпьютерное образование")