GPU-basierte inklusive Scan auf einem unausgeglichenen Baum

Question

Ich habe folgendes Problem: Ich muss die inklusiven Scans (z.B. Präfixsummen) von Werten basierend auf einer Baumstruktur auf der GPU berechnen. Diese Scans können entweder vom Wurzelknoten (top-down) oder von den Blattknoten (bottom-up) ausgehen. Der Fall einer einfachen Kette ist einfach zu handhaben, aber die Baumstruktur macht die Parallelisierung recht schwierig, effizient zu implementieren.

Nach einem top-down inklusiven Scan würde beispielsweise (12) (0)[op](6)[op](7)[op](8)[op](11)[op](12) enthalten, und für einen bottom-up inklusiven Scan würde (8) (8)[op](9)[op](10)[op](11)[op](12) enthalten, wobei [op] ein bestimmter binärer Operator (Matrixaddition, Multiplikation usw.) ist.

Man muss auch die folgenden Punkte berücksichtigen:

• Für ein typisches Szenario sollte die Länge der verschiedenen Äste nicht zu lang sein (~10), mit etwa 5 bis 10 Ästen, sodass dies innerhalb eines Blocks ausgeführt wird und die Arbeit zwischen den Threads aufgeteilt wird. Unterschiedliche Blöcke werden einfach unterschiedliche Werte von Knoten verarbeiten. Dies ist offensichtlich nicht optimal in Bezug auf die Auslastung, aber dies ist eine Einschränkung des Problems, die zu einem späteren Zeitpunkt angegangen wird. Im Moment werde ich mich auf Instruktionslevel-Parallelismus verlassen.
• Die Struktur des Graphen kann nicht geändert werden (sie beschreibt ein tatsächliches System) und kann daher nicht ausgeglichen werden (oder nur durch Änderung der Wurzel des Baumes, z.B. Verwendung von (6) als neue Wurzel). Dennoch sollte ein typischer Baum nicht zu unausgeglichen sein.
• Ich verwende derzeit CUDA für GPGPU, daher bin ich offen für jede CUDA-fähige Template-Bibliothek, die dieses Problem lösen kann.
• Knotendaten befinden sich bereits im globalen Speicher und das Ergebnis wird von anderen CUDA-Kernels verwendet, daher ist das Ziel nur, dies zu erreichen, ohne dass es zu einem großen Engpass wird.
• Es gibt keinen "Zyklus", d.h. Äste können nicht im Baum fusionieren.
• Die Struktur des Baumes ist festgelegt und in einer Initialisierungsphase festgelegt.
• Eine einzige binäre Operation kann ziemlich teuer sein (z.B. Multiplikation von Polynommatrizen, d.h. jedes Element ist ein Polynom eines bestimmten Grades).

In diesem Fall, welche wäre die "beste" Datenstruktur (für die Baumstruktur) und die besten Algorithmen (für die inklusiven Scans/Präfixsummen), um dieses Problem zu lösen?

Answer 1

Vielleicht eine hirnrissige Idee, aber stellen Sie sich vor, dass Sie Knoten mit einem Wert von 0 in den Baum einfügen, auf eine Weise, dass Sie eine 2D-Matrix erhalten. Zum Beispiel gäbe es 3 Nullwertknoten unter dem 5 Knoten in Ihrem Beispiel. Verwenden Sie dann einen Thread, um jede Ebene der Matrix horizontal zu durchlaufen. Für die top-down-Präfixsumme verschieben Sie die Threads so, dass jeder untere Thread verzögert wird durch die maximale Anzahl an Zweigen, die der Baum an dieser Stelle haben kann. So erhalten Sie eine "Welle" mit einer schrägen Kante, die über die Matrix läuft. Die oberen Threads, die weiter fortgeschritten sind, berechnen diese Knoten rechtzeitig, damit sie weiter von den Threads, die weiter unten laufen, bearbeitet werden können. Sie bräuchten die gleiche Anzahl an Threads wie der Baum tief ist.

Answer 2

Ich denke, dass der parallele Präfix-Scan möglicherweise nicht für Ihren Fall geeignet ist, weil:

Der parallele Präfix-Scan Algorithmus wird die Gesamtanzahl von [op] erhöhen. In Ihrem Link zu Präfixsumme erfordert ein paralleler Präfix-Scan mit 16 Eingängen 26 [op], während eine sequenzielle Version nur 15 benötigt. Die Leistung des parallelen Algorithmus beruht auf der Annahme, dass ausreichend Hardware-Ressourcen vorhanden sind, um mehrere [op] parallel auszuführen.

Sie könnten die Kosten Ihrer [op] evaluieren, bevor Sie den parallelen Präfix-Scan ausprobieren.

Andererseits, da die Größe des Baums klein ist, denke ich, dass Sie Ihren Baum einfach als 4 (Anzahl der Blattknoten) unabhängige einfache Ketten betrachten könnten und die gleichzeitige Kernausführung verwenden könnten, um die Leistung dieser 4 Präfix-Scan-Kerne zu verbessern.

0-1-2-3
0-4-5
0-6-7-8-9-10
0-6-7-8-11-12

Answer 3

Ich denke, in der Kepler GK110-Architektur können Sie Kernel rekursiv aufrufen, was sie dynamischen Parallelismus nennen. Wenn Sie also die Summe der Werte an jedem Knoten des Baums berechnen müssen, würde dynamischer Parallelismus helfen. Die Tiefe der Rekursion könnte jedoch eine Einschränkung darstellen.

Answer 4

Mein erster Eindruck ist, dass du die Baumknoten in einem eindimensionalen Array organisieren könntest, ähnlich wie Eric vorgeschlagen hat. Und dann könntest du einen Segmentierten Präfixsummen-Scan (http://en.wikipedia.org/wiki/Segmented_scan) über dieses Array durchführen.

Wenn man deine Baumknoten als Beispiel nimmt, würde das eindimensionale Array wie folgt aussehen:

0-1-2-3-0-4-5-0-6-7-8-9-10-0-6-7-8-11-12

Dann hättest du ein paralleles Array von Flags, die anzeigen, wo eine neue Liste beginnt (mit Liste meine ich eine Sequenz, die am Wurzelknoten beginnt und an einem Blattknoten endet):

1-0-0-0-1-0-0-1-0-0-0-0- 0-1-0-0-0- 0- 0

Für den Bottom-Up-Fall könntest du ein separates Segment-Flag-Array erstellen, wie folgt:

0-0-0-1-0-0-1-0-0-0-0-0- 1-0-0-0-0- 0- 1

und es in umgekehrter Reihenfolge durchlaufen, indem du denselben Algorithmus verwendest.

Was die Implementierung eines Segmentierten Präfix-Scans betrifft, habe ich selbst noch keinen implementiert, aber ich habe ein paar Referenzen gefunden, die informativ sein könnten, wie man es macht: http://www.cs.cmu.edu/afs/cs/academic/class/15418-s12/www/lectures/24_algorithms.pdf und http://www.cs.ucdavis.edu/research/tech-reports/2011/CSE-2011-4.pdf (siehe Seite 23)