Участник: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]-го включительно.
Алгоритм относится к классу алгоритмов сдваивания. Его ключевая идея заключается в том, что на каждом шаге расстояние, на которое передаются и суммируются уже накопленные частичные результаты, удваиваются.
Входные данные представляют собой массив числовых элементов, для которых определена операция сложения, однако алгоритм может быть обобщен на любую ассоциативную бинарную операцию (умножение, нахождение минимума/максимума, логическое И/ИЛИ и.т.д.).
Алгоритм широко используется в параллельных вычислениях.

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

Пусть дан массив чисел:

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

Необходимо найти массив

[math]\displaystyle{ S = \{s_1,s_2,...,s_n\} }[/math]

где [math]\displaystyle{ s_i = x_1 + x_2 + ... + x_i }[/math] для всех [math]\displaystyle{ i }[/math] от 1 до n.

Алгоритм выполняется за [math]\displaystyle{ k = log_{2} n }[/math] шагов:

1. Каждый процессор [math]\displaystyle{ i }[/math] хранит значение [math]\displaystyle{ s_i = x_i }[/math]
2. Для каждого шага [math]\displaystyle{ t }[/math] от 1 до k:
   1. Вычисляем расстояние [math]\displaystyle{ d = 2^{(t-1)} }[/math]
   2. Для каждого индекса [math]\displaystyle{ i \gt d }[/math] процессор [math]\displaystyle{ i }[/math] выполняет: [math]\displaystyle{ s_i = s_i + s_{i-d} }[/math]
   3. Для каждого индекса [math]\displaystyle{ i \lt =d }[/math] значение [math]\displaystyle{ s_i }[/math] остается неизменным
3. После [math]\displaystyle{ k }[/math] шагов массив [math]\displaystyle{ S }[/math] содержит все частные суммы

Простой пример для [math]\displaystyle{ n = 4: }[/math]

• Начало: [math]\displaystyle{ [x_1,x_2,x_3,x_4] }[/math]
• Шаг 1 (d=1): [math]\displaystyle{ [x_1, x_1 + x_2, x_2 + x_3, x_3 + x_4] }[/math]
• Шаг 2 (d-2): [math]\displaystyle{ [x_1, x_1 + x_2, x_1 + x_2 + x_3, x_1 + x_2 + x_3 + x_4] }[/math]

Литература

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