Warum sind Vergleiche auf einer GPU so teuer?

10

Bei dem Versuch, die Leistung meiner Kollisionserkennungsklasse zu verbessern, stellte ich fest, dass ~ 80% der Zeit, die an der GPU verbracht wurde, für if / else-Bedingungen aufgewendet wurde, nur um die Grenzen für die Eimer herauszufinden, die sie durchlaufen sollte.

Etwas präziser:

  1. Jeder Thread erhält eine ID, mit dieser ID holt er sein Dreieck aus dem Speicher (jeweils 3 Ganzzahlen) und mit diesen 3 seine Scheitelpunkte (jeweils 3 Floats).

  2. Anschließend werden die Scheitelpunkte in ganzzahlige Gitterpunkte (derzeit 8 x 8 x 8) umgewandelt und in die Dreiecksgrenzen dieses Gitters umgewandelt

  3. Um die 3 Punkte in Grenzen umzuwandeln, werden die Min / Max jeder Dimension unter jedem der Punkte ermittelt

Da in der von mir verwendeten Programmiersprache ein Minmax fehlt, habe ich selbst einen erstellt, der folgendermaßen aussieht:

procedure MinMax(a, b, c):
   local min, max

   if a > b:
      max = a
      min = b
   else:
      max = b
      min = a
   if c > max:
      max = c
   else:
      if c < min:
         min = c

   return (min, max)

Im Durchschnitt sollten es also 2,5 * 3 * 3 = 22,5 Vergleiche sein, was viel mehr Zeit in Anspruch nimmt als die tatsächlichen Dreieck-Kanten-Schnittpunkttests (etwa 100 * 11-50 Anweisungen).

Tatsächlich stellte ich fest, dass die Vorberechnung der erforderlichen Buckets auf der CPU (Single Threaded, keine Vektorisierung), das Stapeln in einer GPU-Ansicht zusammen mit der Bucket-Definition und das Ausführen von ~ 4 zusätzlichen Lesevorgängen pro Thread durch die GPU sechsmal schneller war als der Versuch die Grenzen vor Ort herauszufinden. (Beachten Sie, dass sie vor jeder Ausführung neu berechnet werden, da es sich um dynamische Netze handelt.)

Warum ist der Vergleich auf einer GPU so schrecklich langsam?

user29075
quelle
2
Ihre Frage bezieht sich auf die Leistung eines bestimmten Codeteils auf Befehlsebene auf einem bestimmten Hardwaretyp. Das klingt für mich viel mehr nach einer Programmierfrage als nach einer Informatikfrage.
David Richerby
7
Ich vermute, dass nicht die Vergleiche teuer sind, sondern die Filialen. Wenn der Compiler keine Prädikation verwendet (oder die GPU diese nicht bereitstellt), werden Verzweigungen verwendet, die ein "Thread" -Zwecken verursachen (da GPUs SIMD-orientiert sind). Das Konvertieren der Bedingung in eine Maske und das Verwenden der Maske zum Synthetisieren von bedingten Bewegungen / Swaps kann eine sinnvolle Alternative sein.
Paul A. Clayton
1
@ DavidRicherby Ich bin mir nicht sicher, ob es so spezifisch ist. Würde diese Frage nicht für eine SIMD-Architektur gelten?
Kasperd
1
@DavidRicherby: Der Grund, warum wir Comp Arch in CS-Abteilungen unterrichten, ist, dass der Comp Arch Auswirkungen auf die von Ihnen ausgewählten Algorithmen hat. SIMD-Architekturen können nur dann einen hohen Durchsatz erzielen, wenn Sie herausfinden, wie das Programm ohne verschachtelte Zweige geschrieben wird.
Wandering Logic
2
Wie die Antwort von Wandering Logic weniger offensichtlich besagt, gehen GPUs davon aus, dass sich viele "Threads" gleichzeitig in derselben Anweisung befinden. GPUs nehmen also grob gesagt jeden Zweig und nicht nur die wahren Zweige. Aus diesem Grund nutzen GPUs die Tatsache aus, dass Nachbarn normalerweise dieselben Zweige verwenden. und Leistung ist schrecklich, wenn dies nicht wahr ist.
Rob

Antworten:

10

GPUs sind SIMD-Architekturen. In SIMD-Architekturen muss jeder Befehl für jedes Element ausgeführt werden, das Sie verarbeiten. (Es gibt eine Ausnahme von dieser Regel, aber es hilft selten).

In Ihrer MinMaxRoutine muss also nicht nur jeder Aufruf alle drei Verzweigungsbefehle abrufen (auch wenn im Durchschnitt nur 2,5 ausgewertet werden), sondern jede Zuweisungsanweisung nimmt auch einen Zyklus in Anspruch (auch wenn sie nicht tatsächlich "ausgeführt" wird). ).

Dieses Problem wird manchmal als Thread-Divergenz bezeichnet . Wenn Ihr Computer über 32 SIMD-Ausführungsspuren verfügt, verfügt er nur über eine einzige Abrufeinheit. (Hier bedeutet der Begriff "Thread" im Grunde genommen "SIMD-Ausführungsspur".) Intern hat also jede SIMD-Ausführungsspur ein "Ich bin aktiviert / deaktiviert" -Bit, und die Zweige manipulieren dieses Bit tatsächlich nur. (Die Ausnahme ist, dass an dem Punkt, an dem jede SIMD-Spur deaktiviert wird, die Abrufeinheit im Allgemeinen direkt zur "else" -Klausel springt.)

In Ihrem Code führt also jede SIMD-Ausführungsspur Folgendes aus:

compare (a > b)
assign (max = a if a>b)
assign (min = b if a>b)
assign (max = b if not(a>b))
assign (min = a if not(a>b))
compare (c > max)
assign (max = c if c>max)
compare (c < min if not(c>max))
assign (min = c if not(c>max) and c<min)

Es kann vorkommen, dass bei einigen GPUs diese Konvertierung von Bedingungen in Prädikation langsamer ist, wenn die GPU dies selbst tut. Wie von @ PaulA.Clayton hervorgehoben, können if (c) x = y else x = zSie möglicherweise bessere Ergebnisse erzielen, wenn Ihre Programmiersprache und -architektur über eine vorgegebene bedingte Verschiebungsoperation verfügt (insbesondere eine der Formulare ). (Aber wahrscheinlich nicht viel besser).

Außerdem ist es nicht c < minerforderlich , die Bedingung innerhalb elsevon zu platzieren c > max. Es spart Ihnen sicherlich nichts und (da die GPU es automatisch in Prädikation konvertieren muss) kann es tatsächlich weh tun, wenn es in zwei verschiedenen Bedingungen verschachtelt ist.

Wanderlogik
quelle
2
(Entschuldigung, wenn ein Teil davon unklar ist, ich versuche eine Antwort zu bekommen, bevor die Theoretiker die Frage als nicht zum Thema gehörend schließen.)
Wandering Logic
Es ist in dem Sinne thematisch, dass einige Algorithmen nicht durch SIMD-Parallelität beschleunigt werden können. (dh: Arbeit, Spanne usw. für eine theoretischere Behandlung des Warum)
Rob
1
Hier ist ein weiterer Vortrag über die Grundlagen der Divergenz people.maths.ox.ac.uk/gilesm/cuda/lecs/lec3-2x2.pdf Beachten Sie daraus, dass das Problem (auf Nvidia sowieso) nur pro Warp besteht. Code, der auf verschiedenen Warps ausgeführt wird, kann leicht voneinander abweichen. Und ein anderes Papier, das eine Methode vorschlägt, um dies zu vermeiden: hal.inria.fr/file/index/docid/649650/filename/sbiswi.pdf
Fizz
Etwas anders, aber in Übereinstimmung mit den Kommentaren, die ich unter der Frage eprint.iacr.org/2012/137.pdf geschrieben habe, ist es lesenswert: Eine 10- fache Verlangsamung im Vergleich zur vorhergesagten Leistung kann für eine GPU "normal" sein, es sei denn, Sie fallen aus zu seiner Montage (normalerweise mit offiziell nicht unterstützten Werkzeugen). Es ist möglich, dass GPU-Targeting-Compiler besser wurden, aber ich würde meinen Atem nicht anhalten.
Fizz