Участник: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:
   • Вычисляем расстояние [math]\displaystyle{ d = 2^{(t-1)} }[/math]
   • Для каждого индекса [math]\displaystyle{ i \gt d }[/math] процессор [math]\displaystyle{ i }[/math] выполняет: [math]\displaystyle{ s_i = s_i + s_{i-d} }[/math]
   • Для каждого индекса [math]\displaystyle{ i ≤ 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]

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

Вычислительное ядро параллельного алгоритма вычисления всех частных сумм представляет собой операцию:

[math]\displaystyle{ s_i = s_i + s_{i-d} }[/math]

где:

• [math]\displaystyle{ s_i }[/math] - текущее значение в процессоре [math]\displaystyle{ i }[/math]
• [math]\displaystyle{ s_{i-d} }[/math] - значение из процессора, находящегося на расстоянии [math]\displaystyle{ d }[/math] слева
• [math]\displaystyle{ d }[/math] - расстояние между процессорами, которое удваивается на каждом шаге

Характеристики вычислительного ядра:

1. Простота: Каждая операция - одно сложение
2. Регулярность: На каждом шаге выполняется одинаковый тип операций, только меняется расстояние
3. Параллельность: Все операции на одном шаге могут выполняться одновременно разными процессорами
4. Коммуникационная интенсивность: Основная сложность - в организации быстрого обмена данными между процессорами, а не в самих вычислениях

На первом шаге выполняется [math]\displaystyle{ n - 1 }[/math] сложений, на втором [math]\displaystyle{ n - 2 }[/math] сложений и так далее. Несмотря на то, что общее количество операций [math]\displaystyle{ (n · log_{2} n) }[/math] больше чем в последовательном алгоритме [math]\displaystyle{ n }[/math] операций, время выполнения сокращается с [math]\displaystyle{ n }[/math] шагов до [math]\displaystyle{ log_{2} n }[/math] шагов благодаря параллелизму.

Макроструктура алгоритма

Алгоритм вычисления всех частных сумм не использует в качестве составных частей другие сложные алгоритмы, но может быть представлен как последовательность однотипных макрошагов (или итераций). Каждый макрошаг состоит из двух базовых операций: коммуникационной (передача данных) и вычислительной (суммирование).

Алгоритм представляет собой последовательность [math]\displaystyle{ log_{2} n }[/math] итераций.
Каждая итерация для всех активных процессоров представима следующими двумя этапами:

1. Передача данных на расстояние [math]\displaystyle{ d }[/math]
2. Сложение: [math]\displaystyle{ s[i] = s[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_k = \sum_{i=1}^n x_i, 1 ≤ k ≤ n }[/math]

В последовательном алгоритме частичные суммы можно вычислить весьма просто из рекуррентного соотношения:

[math]\displaystyle{ S_k = S_{k-1} + x_k, \quad k = 1,2,\ldots,n; \quad S_0 = 0 }[/math]

Фрагмент кода на С++:

   // Вычисление частичных сумм
   s[0] = a[0];
   for (int i = 1; i < n; i++) 
   {
       s[i] = s[i - 1] + a[i];
   }

• Последовательный алгоритм выполняет [math]\displaystyle{ O(n) }[/math] операций за [math]\displaystyle{ O(n) }[/math] времени на 1 процессоре
• Параллельный алгоритм выполняет [math]\displaystyle{ O(n · log n) }[/math] операций за [math]\displaystyle{ O(log n) }[/math] времени на [math]\displaystyle{ n }[/math] процессорах
• При [math]\displaystyle{ n = 1 }[/math] или при выполнении на одном ядре параллельный алгоритм вырождается в последоватьльный

Литература

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