Pixelshader Skalierung Parallelität

[dronus]

Ich wunder mich grad:

Ich will ein großes Bild herunterskalieren und dabei alle Pixel berücksichtigen. Z.b. 2048 x 2048 -> 64 x 64.

Jetzt habe ich zwei Verfahren probiert:
1) Der Pixelshader mittelt je 2x2 Pixel zu einem. Das wird 5x widerholt bis man ein 64x64 Bild hat.
2) Der Pixelshader mittelt 32x32 Pixel zu einem.

Interessanterweise scheint 1) ein vielfaches schneller zu sein (Nvidia GeForce 8600GTS). Warum? Wäre das Zielbild sehr klein, würde 2) vermutlich nicht alle GPU-Shaderkerne ausnutzen. Aber hier können ja immerhin 4096 Pixel bearbeitet werden. Das wird doch wohl reichen?

[Krishty]

Cache-Misses? Mal eine Hilbert-Kurve probiert, statt die 32 × 32 Pixel von links oben nach rechts unten runterzurendern?

Oder – noch besser – probiert, immer nur 2×2 Pixel runterzuskalieren und das rekursiv zu wiederholen, bis alle Pixel abgedeckt sind? Du musst bedenken, dass a + b + c + d nicht so schnell ist wie (a + b) + (c + d), du musst die Pixel also hierarchisch zusammenfassen, wenn es performant sein soll.

Gruß, Ky

[dronus]

Oder – noch besser – probiert, immer nur 2×2 Pixel runterzuskalieren und das rekursiv zu wiederholen, bis alle Pixel abgedeckt sind? Du musst bedenken, dass a + b + c + d nicht so schnell ist wie (a + b) + (c + d), du musst die Pixel also hierarchisch zusammenfassen, wenn es performant sein soll.

Genau das mache ich mit 1). Da ist jetzt die Weisheit da, nur meine Frage bleibt: Warum?

Mit dem Cache ist eine interessante Idee, immerhin werden beim 2x2 Scaler pro Pixel nur zwei Speicherstellen (Rohbildzeilen) adressiert und die sind komplett von etlichen weiteren Pixeln widerverwendbar. Andererseits kann der 32x32-Scaler einen Speicherzugriff praktisch alleine verwenden und muss sich nichtmal auf die Zugriffe der Nachbarn verlassen. Warum sollte er also schlechter sein..

Die Reihenfolge scheint der Treiber übrigens zu optimieren! Es macht keinen Unterschied ob ich die 32x32 Pixel-Schleife nach x oder y zuerst durchgehe.

[Krishty]

Da ist jetzt die Weisheit da, nur meine Frage bleibt: Warum?

Weil es besser parallelisierbar ist als ein trivial implementiertes 2).

Mit dem Cache ist eine interessante Idee, immerhin werden beim 2x2 Scaler pro Pixel nur zwei Speicherstellen (Rohbildzeilen) adressiert und die sind komplett von etlichen weiteren Pixeln widerverwendbar. Andererseits kann der 32x32-Scaler einen Speicherzugriff praktisch alleine verwenden und muss sich nichtmal auf die Zugriffe der Nachbarn verlassen. Warum sollte er also schlechter sein..

GPUs speichern Texturen nicht in Zeilen.

Die Reihenfolge scheint der Treiber übrigens zu optimieren! Es macht keinen Unterschied ob ich die 32x32 Pixel-Schleife nach x oder y zuerst durchgehe.

… oder der Bottleneck liegt woanders. Ist ja auch beides gleich ineffizient.

[Jörg]

Groessere Bloecke koennen sich gegenseitig den Texture-Cache streitig machen. Bei 32x32 liegst Du bei 4KiB pro Thread. AFAIK ist der Texture-Cache gerade mal 16 KiB gross. D.h. schon ab 5 Threads pro Multiprozessor auf der NVidia-HW kommen die sich ins Gehege.
Du kannst das ja mal unter CUDA implementieren, dort kannst Du etwas flexibler mit den Mappings von Threads auf SMs umgehen.
Alternativ koennte ein cleverer Treiber den 2x2 Kernel erkennen und ihn durch bilineare Filterung in den Texture-Units ersetzen....

[Schrompf]

Oder Du machst den bilinearen Trick manuell (der Treiber kann sowas nicht erkennen, denke ich) und machst dafür weniger Stufen. Also sagen wir jeweils 4x4-Pixel mit 4 bilinearen Samples und davon dann nur halb so viele Durchläufe. Ob das einen Performance-Vorteil bringt, hängt wohl sehr am Texturcache und am CPU-Overhead... für kleinere Aufgaben (vielleicht so ab 64x64) ist der CPU-Overhead wahrscheinlich der bestimmende Faktor.

[Krishty]

Ich bleibe dabei, dass die Abhängigkeiten alles kaputt machen. Der GPU Shader Analyzer gibt für eine 32×32-Aufsummierung eine Laufzeit von 3228 Takten auf einer HD 4890 an. Addiert man nicht alles aufeinmal auf, sondern in vier Caches, sind es nurnoch 1614 Takte. Ich bin mir sicher, dass es nochmal bedeutend weniger sind, wenn man hierarchisch vorgeht.

Der Trick mit dem bilinearen Filter ist natürlich auch nützlich, trägt aber nichts zur Fragestellung bei, da die 2×2-Methode genauso davon profitiert :)

[Jörg]

Dem GSA traue ich nur bedingt.

Ohne 4er-Cache:
32x32, ps40: 3329 sind es bei mir mit Flow-Control, 655 ohne.
32x32, ps30: 807 mit FC, ohne FC streikt er.

Mit 4er-Cache:
32x32 ps30 mit FC: 807.
ps40 bekommt er nicht gebacken, keine Fehlermeldung, alle Werte N/A.

Mit diesen Zahlen zu operieren scheint also riskant.

Ansonsten gilt natuerlich, dass ein wiederholter 2x2-kernel viel mehr an Parallelitaet ausnutzen kann als ein 32x32. In Abhaengigkeit des Transfer-Overheads pro Pass gibt es dann irgendwo einen sweet-spot, den man wohl nur durch Messen mit dem konkreten Shader vernuenftig ermitteln kann.

Ich waere mal sehr dran interessiert, ein paar verlaessliche real-world-Zahlen aufzustellen, vllt. hat ja jemand Lust, so einen kleinen Benchmark (mit) zu schreiben...

[Krishty]

Okay, SM < 4.0 ist ein ganz anderes Paar Schuhe, da dort keine Single-Präzision vorgeschrieben ist. Dem Optimizer steht dort also frei, Abhängigkeiten aufzulösen, während er unter 4.0 unbedingt die Reihenfolge des Quelltexts beibehalten muss. Der OP hatte letztens noch was mit Geo-Shadern gemacht, darum gehe ich von SM >= 4 aus.

Ich waere mal sehr dran interessiert, ein paar verlaessliche real-world-Zahlen aufzustellen, vllt. hat ja jemand Lust, so einen kleinen Benchmark (mit) zu schreiben...

Bin genauso für Benching, aber heute morgen zwei Prototypen in den GSA zu hacken ist alles, wofür ich mich aufraffen konnte :D Atm genug Shader-Geraffel am Hals.

[Jörg]

Die drastischen Auswirkungen gab es ja gerade bei SM4 mit oder ohne FC. IEEE-conformance war natuerlich angehakelt bei mir.

[Krishty]

Ups, verlesen, sorry!

Okay, bei mir ist das mit FC auch merkwürdig. Ist FC preferred, wird trotzdem abgewickelt. Wird FC avoided, gibt es
ERROR 0:47: (47,14): warning X4000: Use of potentially uninitialized variable ((unknown))
ERROR 0:48: error X4000: variable 'Cache' used without having been completely initialized

Ich für meinen Teil degradiere mich zum stillen Beobachter :D

[dronus]

Hmm.. was mir immer noch nicht klar ist:
* Beide Methoden lesen jeden Pixel des Quellbildes nur einmal. Und es werden viele aufeinanderfolgende Pixel verwendet.
* Egal ob hierarchisch oder mit Schleife, jedesmal werden aufeinanderfolgende Pixel verarbeitet.
* Beim hierarchischen muss der Shader benachbarte Pixel gleichzeitig malen um vom Cache profitieren zu können, weil jeder Shader ja nur 4 Pixel zusammenfasst, und damit einen Speicherzugriff alleine bei weitem nicht ausnutzt.
* Die Schleife dagegen kann schon für einen Pixel mehrere Texturspeicherzugriffe benutzen ohne dabei einen gelesen Pixel zu verschwenden. Warum ist die dann schlechter?

[Krishty]

* Beim hierarchischen muss der Shader benachbarte Pixel gleichzeitig malen um vom Cache profitieren zu können, weil jeder Shader ja nur 4 Pixel zusammenfasst, und damit einen Speicherzugriff alleine bei weitem nicht ausnutzt.

GPUs speichern Texturen nicht in Zeilen.

Beim Laden werden nicht n Pixel einer Zeile gecached, sondern m × m Pixel eines Quads, dessen Pixel gemäß einer Space-Filling-Curve im Speicher angeordnet sind. Darum ist es furchtbar ineffizient, die Textur zeilen- oder spaltenweise zu lesen. Liest du stattdessen quad-weise, hast du so gut wie keine Cache-Misses. Fasst du die einzelnen Quads hierarchisch zusammen, lässt es sich außerdem – im Gegensatz zu einer Schleife – parallelisieren.

[dronus]

Fasst du die einzelnen Quads hierarchisch zusammen, lässt es sich außerdem – im Gegensatz zu einer Schleife – parallelisieren.

Joa, ok, aber die Schleife wird ja auch für jeden Pixel im Zielbild, also einige Tausend Mal ausgeführt... und mehr als 1000 Kerne hat meine GPU wohl kaum, so dass welche nichts zu tun hätten?

[Krishty]

Wenn du in einer Schleife aufaddierst, kann die nächste Addition erst durchgeführt werden, wenn die vorherige fertig ist. Du hast dann keine anderen Shader-Cores leer laufen, aber dafür alle ALUs eines Shader-Cores, die nicht addieren. Und die kriegst du nicht einmal ausgenutzt, weil sie ständig auf die Ergebnisse der vorherigen Addition warten. (Jedenfalls im Groben – Jörg stellt das sicher noch richtiger ;) )

[Jörg]

"Noch richtiger" wohl kaum, aber vielleicht eine intuitievere Erklaerung. (Am Rande: Das Problem was man hier sieht findest Du in der Literatur unter "parallel reduction" beschrieben).

Aber um beim Beispiel zu bleiben.
Angenommen jede Addition benoetigt 1 Zeiteinheit, Speichertransfers sind so schnell, dass sie im gleichen Zeitabschnitt ausgefuehrt werden koennen.

Dann brauchst Du fuer eine sequentielle Addition von (N+1) Werten genau N Zeitschritte. Da aber die Additions-Operation assoziativ ist, koennte man sich ja denken, hey, moment, warum nehme ich nicht eine zweite CPU und teile alles auf (das hatten wir oben in einem Beispiel a+b+c+d => (a+b) + (c+d)?
Statt N Operationen auf einer CPU habe ich (grob) N/2 auf 2 verteilt. Das sind noch immer die gleiche Anzahl an Operationen, aber die Aufteilung hat einen Vorteil: Man kann beide CPUs zur gleichen Zeit starten und schwups sind sie nach der Haelfte der Zeit fertig. Aber nun muessen beide CPUs am Ende doch noch dazu gebracht werden, ihre Werte zusammenzurechnen, hier entsteht also durch die Aufteilung der Bedarf an einer Kommunikationsoperation, die zwingend erst dann starten kann, wenn beide Haelften berechnet wurden. Jede Halbierung des Bereiches resultiert also in einer Halbierung der Ausfuehrungszeit fuer die Basisoperationen, ruft aber einen Overhead durch die Kommunikation hervor. Fuer unser Beispiel waere das das Schreiben des Ergebnisses eines 2x2-kernels in den GPU-Speicher sowie das anschliessende Lesen im naechsten Pass.
Wenn man es sich visualisiert, erhaelt man fuer einen solchen Algorithmus eine Baumstruktur, deren Hoehe log_2(N) ist. Die Knoten enthalten das Ausfuehren eines Kernels, die Kanten stehen fuer die auftretende Kommunikationsoperation. Und nicht vergessen: Pro Ebene des Baumes kann jeder Knoten unabhaengig seiner Nachbarn berechnet werden.

Ueber die Groesse des Kernels kann man nun ein bisschen Steuern, wie tief der Baum wird. Ein groesserer Kernel bedeutet dass mehr Zeit in den Knoten verbraucht wird und weniger in der Kommunikation. Je nach Verhaeltnis dieser Werte gibt es irgendwo ein Optimum der Kernelgroesse fuer deinen Kartentyp.

Was hat es nun mit diesem "4er" - Cache noch aufsich: Wenn der Kernel wieder groesser wird, dann kann es sein, dass man durch andere Techniken die sequentielle Ausfuehrung in diesem Kernel beschleunigen kann. Wenn z.B. Operationen Latenzen aufweisen, dann kann man die so hintereinander legen, dass sie moeglichst unabhaengig von vorherigen Berechnungen sind. Soetwas ueberlaesst man am Besten dem Compiler (auch wenn man am GSA-Beispiel sieht, dass da wohl noch etwas Arbeit inverstiert werden koennte ;) ).

Die Texture-Caches helfen hier nur noch, an den Werten der Kommunikationszeit zu drehen. Und ich sehe eben, dass die noch kleiner sind als ich dachte: 6-8KB nur auf deiner Karte.

Zum letzen Punkt: Doch , deine GPU kann 1000ende von Threads ausfuehren (nur nicht 100%ig parallel). Was dort passiert ist folgendes: Die Threads werden quasi "auf Halde" produziert. Wenn es einem Thread nicht moeglich ist, im naechsten Takt sofort weiterzurechnen (weil er z.B. auf einen Memory-Transfer wartet, oder eine sync-Operation mit anderen Threads durchfuehrt, oder weil er einen Befehl ausfuehrt, der eine hohe Latenz hat und diese nicht durch andere Instruktionen versteckt werden kann oder weil er eine Hardware-Einheit benutzen will, die gerade blockiert ist, ...), dann wird aus dem grossen Pool ein anderer Thread verwendet. (Fuer Einzelheiten bei NVidia schau am besten in das CUDA-Handbuch, da erfaehrst Du alles ueber Streaming Multiprocessors, Thread, Warps, Blocks und Grids). Gerade hier, was die Handhabung von Threads angeht, unterscheiden sich GPUs doch ziemlich voneinander. Der kleine SGX535 kann z.B. 16 Threads in jeder seiner beiden Pipelines halten, eine NVidia GPU deiner Generation jedoch schon bis zu 768 (am besten ins Manual schauen, Appendix A.1, so langsam kann mein Kopf nicht mehr jede Zahl behalten) pro Streaming Multiprocessor (und davon hat sie so einige...2 bis 30 bei den nicht-Fermi Karten).

Vielleicht hilft das ja ein bisschen, die ganze Thematik zu verstehen, und wenn nicht, dann frag einfach weiter oder schnapp dir die Literatur.

Aber nun ist Schluss, meine Bahnfahrt ist ja schon halb vorbei ;)

[dronus]

Danke für die ausfühtliche Erläuterung :-)

ich hab noch eine einfache Idee warum die Schleife schlechter sein könnte:

Wenn die GPU die 32x32 Pixel des Zielbildes auf 32x32 Shaderkerne (angenommen es gäbe soviele) verteilt, wird auf jedem die Schleife den ersten passenden Pixel des Quellbildes lesen wollen, das sind 32x32 verstreute PIxel, vermutlich muss dazu das ganze Bild aus dem Speicher geholt werden, dass passt aber nicht in den Cache. So wird jedes Byte des Quellbildes vielfach gelesen, obwohl innerhalb einer Schleife schön zusammenhängende Speicherzellen gebraucht werden.

Wenn die GPU ihre z.b. 100 Kerne auf 2x2 Pixel Blöcke stürzt, sind das Vermutlich die ersten 100 2x2 Blöcke des Quellbildes "links oben", dann wird jede von einem Kern geladene Speichersstelle im Quellbild tatsächlich auch von vielen anderen Kernen benötigt, und vielleicht passen sogar die Zugriffe aller Kerne in den Cache. Dann wird jedes Byte im Quellbild nur einmal gelesen.