Paralleler Algorithmus zum Berechnen der Präfixsumme

Question

Ich habe ein Problem mit der Implementierung des Algorithmus zur Berechnung einer Präfix Summe parallel. Obwohl dieser Algorithmus 3 Schritte hat, kann ich den Code nicht schreiben, da kein Pseudocode angegeben ist.

Ich ging durch verschiedene Materialien im Web und auch auf Stack-Überlauf, aber ich habe nicht die genaue Implementierung des Algorithmus wie auf der wiki angegeben. Die Wiki erwähnt die folgenden:

A Präfixsumme kann durch die folgenden Schritte parallel berechnet werden ::

1. Berechne die Summen von aufeinander folgenden Paaren von Elementen in dem das erste Element des Paares ein HAS geradem Index: z0 = x0 + x1, z1 = x2 + x3 usw.
2. Recursively die Präfixsumme w0 berechnen, w1, w2, ... der Folge z0, z1, z2, ...
3. Expand jeder Term der Folge w0, w1, w2, ... in zwei Terme der Gesamtpräfixsumme: y0 = x0, y1 = w0, y2 = w0 + x2, y3 = w1 usw. Nach dem fi rst Wert, jeder aufeinanderfolgende Reihe yi entweder aus einer Position, halb so weit durch die w-Sequenz kopiert oder der vorherige Wert hinzugefügt, um einen Wert in der X-Sequenz

Kann jemand bitte einen Pseudocode vorschlagen Implementierung für mich zu überprüfen und zu implementieren?

Answer 1

ich die bereitgestellte Antwort glaube nicht genug ist, um den Algorithmus zu verstehen, so vorgesehen ich eine tatsächliche Antwort mit umfassendem Pseudo-Code hier: https://stackoverflow.com/a/12874227/697862 basierend auf http://http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html, die ein vollständigen Artikel ist Beschreibung des optimalen parallelen Algorithmus gemäß:

Blelloch, Guy E. 1990. "Präfix Summen und ihre Anwendungen." Technische Bericht CMU-CS-90-190, Schule für Informatik, Carnegie Mellon Universität.

Answer 2

Was Sie geschrieben haben ist ziemlich Pseudo-Code für sich allein, aber ich hoffe, dass dies helfen wird.

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 

EDIT: y _i wird Summe wollen wir wünschen bekommen, y _i = w _i/2, wenn i% 2 == 1 und w _i/2-1 + _x, sonst. Hier gehen wir davon aus, dass w _-1 = 0