Параллельный алгоритм для вычисления суммы префикса

Question

У меня проблема с реализацией алгоритма для вычисления суммы префикса параллельно. Хотя этот алгоритм состоит из 3 шагов, я не могу написать код, поскольку псевдокод не указан.

Я просмотрел различные материалы в Интернете, а также о переполнении стека, но не получил точную реализацию алгоритма, описанную в вики. В вики упоминается следующее:

Сумма префикса может быть рассчитана параллельно с помощью следующих шагов:

1. Вычислить суммы последовательных пар элементов, в которых первый элемент пары имеет четный индекс: z0 = x0 + x1, z1 = x2 + x3 и т. Д.
2. Рекурсивно вычислить префиксную сумму w0, w1, w2, ... последовательности z0, z1, z2, ...
3. Разложите каждый член последовательности w0, w1, w2, ... на два члена общей суммы префикса: y0 = x0, y1 = w0, y2 = w0 + x2, y3 = w1 и т. Д. После первого значения каждое последовательное число yi либо копируется из позиции на половину так далеко через последовательность w, либо к предыдущему значению добавляется одно значение в последовательности x

Может кто-нибудь предложить мне реализацию псевдокода для проверки и реализации?

Answer 1

Я полагаю, что предоставленного ответа недостаточно для понимания алгоритма, поэтому я предоставил реальный ответ с более полным псевдокодом здесь: /questions/8960158/parallelnaya-summa-prefiksa-samaya-byistraya-realizatsiya/8960164#8960164 на основе http://http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html - полная статья, описывающая оптимальный параллельный алгоритм в соответствии с:

Blelloch, Guy E. 1990. "Префиксные суммы и их приложения". Технический отчет CMU-CS-90-190, Школа компьютерных наук, Университет Карнеги-Меллона.

Answer 2

То, что вы написали, в значительной степени само по себе является псевдокодом, но я надеюсь, что это поможет.

prefix_sum(List x):List
begin
   //This step is split in multiple tasks that are running in paralell
   //build z, be careful around the end
   w = prefix_sum(z)

   //This step should also be split in multiple tasks
   //build y, using w and x
   return y
end

РЕДАКТИРОВАТЬ: y_i желаемая сумма, которую мы хотим получить, y_i = w_{i / 2}, если i%2 == 1, и w_{i / 2-1}+_x, в противном случае. Здесь мы предполагаем, что w_-1= 0