Участник:Bannikov Nikolay/Параллельный алгоритм вычисления всех частных сумм

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

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

Данный алгоритм предназначен для вычисления всех частных сумм заданного массива данных. Для входного массива:

[math]\displaystyle{ X = \{x_1,x_2,...,x_n\} }[/math]

требуется найти массив:

[math]\displaystyle{ S = \sum_{i=1}^n x_i }[/math]

такой, что каждый его элемент [math]\displaystyle{ S[i] }[/math] равен сумме всех элементов [math]\displaystyle{ X }[/math] от первого до [math]\displaystyle{ i }[/math]-го включительно.
Алгоритм относится к классу алгоритмов сдваивания. Его ключевая идея заключается в том, что на каждом шаге расстояние, на которое передаются и суммируются уже накопленные частичные результаты, удваиваются. Входные данные представляют собой массив числовых элементов, для которых определена операция сложения, однако алгоритм может быть обобщен на любую ассоциативную бинарную операцию (умножение, нахождение минимума/максимума, логическое И/ИЛИ и.т.д.).

Литература

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