Neuer GPU-Tracking-Algorithmus: Wavefront Path Tracing

In diesem Artikel untersuchen wir das wichtige Konzept der kürzlich veröffentlichten Lighthouse 2-Plattform: Die Wellenfront-Pfadverfolgung , wie sie von NVIDIA als Lane, Karras und Aila bezeichnet wird, oder die Streaming-Pfadverfolgung, wie sie ursprünglich in Van Antwerps Masterarbeit genannt wurde , spielt eine entscheidende Rolle die Entwicklung effizienter Pfad-Tracer auf der GPU und potenzieller Pfad-Tracer auf der CPU. Es ist jedoch ziemlich eingängig, daher ist es zum Verständnis notwendig, Raytracing-Algorithmen zu überdenken.

Belegung

Der Pfadverfolgungsalgorithmus ist überraschend einfach und kann in nur wenigen Pseudocodezeilen beschrieben werden:

vec3 Trace( vec3 O, vec3 D ) IntersectionData i = Scene::Intersect( O, D ) if (i == NoHit) return vec3( 0 ) // ray left the scene if (i == Light) return i.material.color // lights do not reflect vec3 R, pdf = RandomDirectionOnHemisphere( i.normal ), 1 / 2PI return Trace( i.position, R ) * i.BRDF * dot( i.normal, R ) / pdf 

Die Eingabe ist der Primärstrahl , der von der Kamera durch das Bildschirmpixel geleitet wird. Für diesen Strahl bestimmen wir den nächsten Schnittpunkt mit dem Szenenprimitiv. Wenn es keine Schnittpunkte gibt, verschwindet der Strahl in der Leere. Andernfalls, wenn der Strahl die Lichtquelle erreicht, haben wir den Lichtweg zwischen der Quelle und der Kamera gefunden. Wenn wir etwas anderes finden, führen wir Reflexion und Rekursion durch, in der Hoffnung, dass der reflektierte Strahl immer noch die Beleuchtungsquelle findet. Beachten Sie, dass dieser Prozess dem (Rück-) Pfad eines Photons ähnelt, das von der Oberfläche einer Szene reflektiert wird.

GPUs sind so konzipiert, dass sie diese Aufgabe im Multithread-Modus ausführen. Auf den ersten Blick scheint Ray Tracing dafür ideal zu sein. Wir verwenden OpenCL oder CUDA, um einen Stream für ein Pixel zu erstellen. Jeder Stream führt einen Algorithmus aus, der tatsächlich wie beabsichtigt funktioniert und ziemlich schnell ist. Schauen Sie sich nur einige Beispiele mit ShaderToy an, um zu verstehen, wie schnell Raytracing sein kann auf der GPU. Aber wie auch immer, die Frage ist anders: Sind diese Raytracer wirklich so schnell wie möglich ?


Dieser Algorithmus hat ein Problem. Der Primärstrahl kann die Lichtquelle sofort oder nach einer zufälligen Reflexion oder nach fünfzig Reflexionen finden. Der Programmierer für die CPU wird hier einen möglichen Stapelüberlauf bemerken. Der GPU-Programmierer sollte das Belegungsproblem sehen . Das Problem wird durch eine bedingte Schwanzrekursion verursacht: Der Pfad kann an der Lichtquelle enden oder fortgesetzt werden. Lassen Sie uns dies auf viele Threads übertragen: Einige der Threads werden angehalten und der andere Teil funktioniert weiterhin. Nach einigen Überlegungen werden wir mehrere Threads haben, die weiter rechnen müssen, und die meisten Threads warten darauf, dass diese letzten Threads ihre Arbeit beenden. Die Beschäftigung ist ein Maß für den Anteil der GPU-Threads, die nützliche Arbeit leisten.

Das Beschäftigungsproblem betrifft das Ausführungsmodell von SIMT-GPU-Geräten. Streams sind in Gruppen organisiert, z. B. in der Pascal-GPU (NVidia-Geräteklasse 10xx). 32 Threads werden zu einem Warp kombiniert. Threads in Warp haben einen gemeinsamen Programmzähler: Sie werden mit einem festen Schritt ausgeführt, sodass jeder Programmbefehl von 32 Threads gleichzeitig ausgeführt wird. SIMT steht für Single Instruction Multiple Thread , was das Konzept gut beschreibt. Für einen SIMT-Prozessor ist ein Code mit Bedingungen komplex. Dies wird in der offiziellen Volta-Dokumentation deutlich gezeigt:


Codeausführung mit Bedingungen in SIMT.

Wenn eine bestimmte Bedingung für einige Threads in Warp erfüllt ist, werden die Zweige der if-Anweisung serialisiert. Eine Alternative zum Ansatz "Alle Threads machen dasselbe" ist "Einige Threads sind deaktiviert". Im Wenn-Dann-Sonst-Block beträgt die durchschnittliche Besetzung von Warp 50%, es sei denn, alle Threads weisen eine Konsistenz hinsichtlich der Bedingung auf.

Leider ist Code mit Bedingungen im Ray Tracer nicht so selten. Schattenstrahlen werden nur emittiert, wenn sich die Lichtquelle nicht hinter dem Schattierungspunkt befindet, unterschiedliche Pfade mit unterschiedlichen Materialien kollidieren können, die Integration in die russische Roulette-Methode den Pfad zerstören oder am Leben lassen kann und so weiter. Es stellt sich heraus, dass die Belegung zur Hauptursache für Ineffizienz wird und es nicht so einfach ist, sie ohne Sofortmaßnahmen zu verhindern.

Streaming Path Tracing

Der Streaming Path Tracing-Algorithmus wurde entwickelt, um die Hauptursache des ausgelasteten Problems zu beheben. Die Streaming-Pfadverfolgung unterteilt den Pfadverfolgungsalgorithmus in vier Schritte:

1. Generieren
2. Verlängern
3. Schatten
4. Verbinden

Jede Stufe wird als separates Programm implementiert. Anstatt einen vollständigen Pfad-Tracer als einzelnes GPU-Programm („Kernel“, Kernel) auszuführen, müssen wir daher mit vier Kernen arbeiten. Wie wir gleich sehen werden, werden sie außerdem in einer Schleife ausgeführt.

Stufe 1 („Generieren“) ist für die Erzeugung von Primärstrahlen verantwortlich. Dies ist ein einfacher Kern, der die Startpunkte und Richtungen der Strahlen in einer Menge erzeugt, die der Anzahl der Pixel entspricht. Die Ausgabe dieser Stufe ist ein großer Strahlpuffer und ein Zähler, der die nächste Stufe über die Anzahl der zu verarbeitenden Strahlen informiert. Bei Primärstrahlen entspricht dieser Wert der Breite des Bildschirms multipliziert mit der Höhe des Bildschirms .

Stufe 2 („Erneuern“) ist der zweite Kern. Es wird erst ausgeführt, nachdem Stufe 1 für alle Pixel abgeschlossen ist. Der Kernel liest den in Schritt 1 erzeugten Puffer und kreuzt jeden Strahl mit der Szene. Die Ausgabe dieser Stufe ist das Schnittergebnis für jeden im Puffer gespeicherten Strahl.

Stufe 3 („Schatten“) wird nach Abschluss von Stufe 2 ausgeführt. Sie empfängt das Ergebnis der Schnittmenge aus Stufe 2 und berechnet das Schattierungsmodell für jeden Pfad. Diese Operation kann neue Strahlen erzeugen oder nicht, abhängig davon, ob der Pfad abgeschlossen ist. Die Pfade, die den neuen Strahl erzeugen (der Pfad "erweitert"), schreiben den neuen Strahl (das "Pfadsegment") in den Puffer. Pfade, die Lichtquellen direkt abtasten ("Beleuchtung explizit abtasten" oder "das nächste Ereignis berechnen"), schreiben einen Schattenstrahl in einen zweiten Puffer.

Stufe 4 („Verbinden“) zeichnet die in Stufe 3 erzeugten Schattenstrahlen nach. Dies ähnelt Stufe 2, weist jedoch einen wichtigen Unterschied auf: Die Schattenstrahlen müssen einen beliebigen Schnittpunkt finden, während die sich ausdehnenden Strahlen den nächsten Schnittpunkt finden müssen. Daher wurde hierfür ein separater Kern erstellt.

Nach Abschluss von Schritt 4 erhalten wir einen Puffer mit Strahlen, die den Pfad erweitern. Nachdem wir diese Strahlen aufgenommen haben, fahren wir mit Stufe 2 fort. Wir machen so weiter, bis keine Verlängerungsstrahlen mehr vorhanden sind oder bis wir die maximale Anzahl von Iterationen erreicht haben.

Ineffizienzquellen

Ein Programmierer, der sich Sorgen um die Leistung macht, wird in einem solchen Schema von Algorithmen zur Verfolgung von Streaming-Pfaden viele gefährliche Momente erleben:

• Anstelle eines einzelnen Kernelaufrufs haben wir jetzt drei Aufrufe pro Iteration sowie einen Generierungskernel. Herausfordernde Kerne bedeuten eine gewisse Erhöhung der Last, was schlecht ist.
• Jeder Kern liest einen riesigen Puffer und schreibt einen riesigen Puffer.
• Die CPU muss wissen, wie viele Threads für jeden Kern generiert werden müssen. Daher muss die GPU der CPU mitteilen, wie viele Strahlen in Schritt 3 generiert wurden. Das Verschieben von Informationen von der GPU zur CPU ist eine schlechte Idee und muss mindestens einmal pro Iteration erfolgen.
• Wie schreibt Stufe 3 die Strahlen in den Puffer, ohne überall Räume zu schaffen? Er benutzt dafür keinen Atomzähler?
• Die Anzahl der aktiven Pfade nimmt immer noch ab. Wie kann dieses Schema überhaupt helfen?

Beginnen wir mit der letzten Frage: Wenn wir eine Million Aufgaben an die GPU übertragen, werden keine Millionen Threads generiert. Die tatsächliche Anzahl der gleichzeitig ausgeführten Threads hängt von der Ausrüstung ab. Im allgemeinen Fall werden jedoch Zehntausende von Threads ausgeführt. Erst wenn die Last unter diese Zahl fällt, werden wir Beschäftigungsprobleme bemerken, die durch eine kleine Anzahl von Aufgaben verursacht werden.

Ein weiteres Problem ist die große E / A von Puffern. Dies ist zwar eine Schwierigkeit, aber nicht so schwerwiegend, wie Sie es vielleicht erwarten: Der Zugriff auf Daten ist sehr vorhersehbar, insbesondere beim Schreiben in Puffer, sodass die Verzögerung keine Probleme verursacht. Tatsächlich wurden GPUs hauptsächlich für diese Art der Datenverarbeitung entwickelt.

Ein weiterer Aspekt, den GPUs sehr gut handhaben, sind Atomzähler, was für Programmierer, die in der CPU-Welt arbeiten, ziemlich unerwartet ist. Der Z-Puffer erfordert einen schnellen Zugriff, und daher ist die Implementierung von Atomzählern in modernen GPUs äußerst effektiv. In der Praxis ist eine atomare Schreiboperation genauso kostspielig wie ein nicht zwischengespeicherter Schreibvorgang in den globalen Speicher. In vielen Fällen wird die Verzögerung durch umfangreiche parallele Ausführung in der GPU maskiert.

Es bleiben zwei Fragen offen: Kernelaufrufe und bidirektionale Datenübertragung für Zähler. Letzteres ist eigentlich ein Problem, daher brauchen wir eine weitere Änderung der Architektur: dauerhafte Threads .

Die Folgen

Bevor wir uns mit den Details befassen, werden wir die Auswirkungen der Verwendung des Wellenfront-Pfadverfolgungsalgorithmus untersuchen. Lassen Sie uns zunächst über Puffer sprechen. Wir benötigen einen Puffer, um die Daten von Stufe 1 auszugeben, d.h. Primärstrahlen. Für jeden Strahl benötigen wir:

• Strahlursprung: drei Gleitkommawerte, d. H. 12 Bytes
• Strahlrichtung: drei Gleitkommawerte, d. H. 12 Bytes

In der Praxis ist es besser, den Puffer zu vergrößern. Wenn Sie 16 Bytes für den Anfang und die Richtung des Strahls speichern, kann die GPU diese in einem 128-Bit-Lesevorgang lesen. Eine Alternative ist eine 64-Bit-Leseoperation, gefolgt von einer 32-Bit-Operation, um float3 zu erhalten, was fast doppelt so langsam ist. Das heißt, für einen Bildschirm von 1920 × 1080 erhalten wir: 1920x1080x32 = ~ 64 MB. Wir benötigen auch einen Puffer für die vom Extend-Kernel erstellten Schnittpunktergebnisse. Dies sind weitere 128 Bit pro Element, dh 32 MB. Außerdem kann der "Shadow" -Kern bis zu 1920 × 1080 Pfaderweiterungen (Obergrenze) erstellen, und wir können sie nicht in den Puffer schreiben, aus dem wir lesen. Das sind weitere 64 MB. Und schließlich, wenn unser Pfad-Tracer Schattenstrahlen aussendet, ist dies ein weiterer 64-MB-Puffer. Nachdem wir alles zusammengefasst haben, erhalten wir 224 MB Daten, und dies gilt nur für den Wellenfrontalgorithmus. Oder ungefähr 1 GB in 4K-Auflösung.

Hier müssen wir uns an eine andere Funktion gewöhnen: Wir haben viel Speicher. Es mag scheinen. Diese 1 GB sind eine Menge, und es gibt Möglichkeiten, diese Anzahl zu reduzieren. Wenn Sie dies jedoch realistisch angehen, ist die Verwendung von 1 GB auf einer GPU mit 8 GB das geringere unserer Probleme, wenn wir die Pfade wirklich in 4 KB verfolgen müssen.

Die Konsequenzen sind schwerwiegender als die Speicheranforderungen und wirken sich auf den Rendering-Algorithmus aus. Bisher habe ich vorgeschlagen, dass wir einen Erweiterungsstrahl und möglicherweise einen Schattenstrahl für jeden Thread im Schattenkern erzeugen müssen. Aber was ist, wenn wir Ambient Occlusion mit 16 Strahlen pro Pixel durchführen möchten? 16 AO-Strahlen müssen im Puffer gespeichert werden, aber noch schlimmer, sie erscheinen erst in der nächsten Iteration. Ein ähnliches Problem tritt auf, wenn Strahlen im Whited-Stil verfolgt werden: Es ist fast unmöglich, einen Schattenstrahl für mehrere Lichtquellen zu emittieren oder einen Strahl bei einer Kollision mit Glas zu spalten.

Auf der anderen Seite löst die Wellenfrontpfadverfolgung die Probleme, die wir im Abschnitt "Belegung" aufgeführt haben:

• In Stufe 1 erzeugen alle Flüsse ohne Bedingungen Primärstrahlen und schreiben sie in den Puffer.
• In Stufe 2 schneiden alle Flüsse ohne Bedingungen die Strahlen mit der Szene und schreiben die Ergebnisse der Schnittmenge in den Puffer.
• In Schritt 3 beginnen wir mit der Berechnung der Kreuzungsergebnisse bei 100% Belegung.
• In Schritt 4 verarbeiten wir eine fortlaufende Liste von Schattenstrahlen ohne Leerzeichen.

Wenn wir mit den überlebenden Strahlen mit einer Länge von 2 Segmenten zu Stufe 2 zurückkehren, haben wir wieder einen kompakten Strahlenpuffer, der die Vollbeschäftigung garantiert, wenn der Kernel startet.

Darüber hinaus gibt es einen zusätzlichen Vorteil, der nicht zu unterschätzen ist. Der Code wird in vier separaten Schritten isoliert. Jeder Kern kann alle verfügbaren GPU-Ressourcen (Cache, gemeinsam genutzter Speicher, Register) verwenden, ohne andere Kerne zu berücksichtigen. Dies kann es der GPU ermöglichen, den Schnittpunktcode mit der Szene in mehr Threads auszuführen, da für diesen Code nicht so viele Register erforderlich sind wie für den Shader-Code. Je mehr Threads, desto besser können Sie die Verzögerungen ausblenden.

Vollzeit, verbesserte Verzögerungsmaskierung, Streaming-Aufzeichnung: All diese Vorteile stehen in direktem Zusammenhang mit der Entstehung und der Art der GPU-Plattform. Für die GPU ist der Wellenfront-Pfadverfolgungsalgorithmus sehr natürlich.

Lohnt es sich?

Natürlich haben wir eine Frage: Rechtfertigt eine optimierte Beschäftigung die E / A von Puffern und die Kosten für das Aufrufen zusätzlicher Kerne?

Die Antwort lautet ja, aber dies zu beweisen ist nicht so einfach.

Wenn wir für eine Sekunde mit ShaderToy zu den Pfad-Tracern zurückkehren, werden wir feststellen, dass die meisten von ihnen eine einfache und fest codierte Szene verwenden. Das Ersetzen durch eine vollständige Szene ist keine triviale Aufgabe: Für Millionen von Grundelementen wird das Schneiden des Strahls und der Szene zu einem komplexen Problem, dessen Lösung häufig NVidia ( Optix ), AMD ( Radeon-Rays ) oder Intel ( Embree ) überlassen bleibt. Keine dieser Optionen kann die fest codierte Szene im CUDA-Tracer für künstliche Strahlen problemlos ersetzen. In CUDA erfordert das nächstgelegene Analogon (Optix) die Kontrolle über die Programmausführung. Mit Embree in der CPU können Sie einzelne Strahlen aus Ihrem eigenen Code verfolgen. Die Kosten hierfür sind jedoch ein erheblicher Leistungsaufwand: Er zieht es vor, große Gruppen von Strahlen anstelle einzelner Strahlen zu verfolgen.


Bildschirm von It's About Time mit Brigade 1 gerendert.

Wird die Wellenfrontpfadverfolgung schneller sein als ihre Alternative (der Megakernel, wie Lane und Kollegen ihn nennen), hängt von der Zeit ab, die in den Kernen verbracht wird (große Szenen und kostspielige Shader reduzieren den relativen Kostenüberlauf durch den Wellenfrontalgorithmus), von der maximalen Pfadlänge , Mega-Core-Beschäftigung und Unterschiede in der Belastung der Register in vier Stufen. In einer frühen Version des ursprünglichen Brigade Path Tracer haben wir festgestellt, dass selbst eine einfache Szene mit einer Mischung aus reflektierenden und Lambert-Oberflächen auf der GTX480 von der Verwendung der Wellenfront profitiert.

Streaming Path Tracing im Leuchtturm 2

Die Lighthouse 2-Plattform verfügt über zwei Tracer zur Verfolgung von Wellenfrontpfaden. Der erste verwendet Optix Prime für die Implementierung der Stufen 2 und 4 (Stufen der Schnittmenge von Strahlen und Szenen); Im zweiten Fall wird Optix direkt verwendet, um diese Funktionalität zu implementieren.

Optix Prime ist eine vereinfachte Version von Optix, die sich nur mit dem Schnittpunkt einer Reihe von Strahlen mit einer Szene aus Dreiecken befasst. Im Gegensatz zur vollständigen Optix-Bibliothek unterstützt sie keinen benutzerdefinierten Schnittcode und schneidet nur Dreiecke. Dies ist jedoch genau das, was für den Wellenfrontpfad-Tracer erforderlich ist.

Der auf Optix Prime basierende Wellenfrontpfad-Tracer ist in rendercore.cpp Projekts rendercore.cpp . Die Initialisierung von Optix Prime beginnt in der Init Funktion und verwendet rtpContextCreate . Die Szene wird mit rtpModelCreate . In der SetTarget Funktion werden mit rtpBufferDescCreate verschiedene Strahlenpuffer erstellt. Beachten Sie, dass wir für diese Puffer die üblichen Gerätezeiger bereitstellen: Dies bedeutet, dass sie sowohl in Optix- als auch in regulären CUDA-Kernen verwendet werden können.

Das Rendern beginnt mit der Render . Um den primären Strahlenpuffer zu füllen, wird ein CUDA-Kern namens generateEyeRays . Nach dem Füllen des Puffers wird Optix Prime mit rtpQueryExecute . Damit werden Schnittpunkteergebnisse in extensionHitBuffer . Beachten Sie, dass alle Puffer in der GPU verbleiben: Mit Ausnahme von Kernelaufrufen besteht kein Datenverkehr zwischen der CPU und der GPU. Die Stufe „Schatten“ ist im regulären CUDA- shade implementiert. Die Implementierung erfolgt in pathtracer.cu .

Einige Implementierungsdetails für optixprime_b sind erwähnenswert. Erstens werden Schattenstrahlen außerhalb des Wellenfrontzyklus verfolgt. Dies ist richtig: Ein Schattenstrahl wirkt sich nur dann auf ein Pixel aus, wenn es nicht blockiert ist. In allen anderen Fällen wird sein Ergebnis jedoch nirgendwo anders benötigt. Das heißt, der Schattenstrahl ist wegwerfbar und kann jederzeit und in beliebiger Reihenfolge verfolgt werden. In unserem Fall verwenden wir dies, indem wir die Strahlen des Schattens so gruppieren, dass die endgültig verfolgte Charge so groß wie möglich ist. Dies hat eine unangenehme Konsequenz: Bei N Iterationen des Wellenfrontalgorithmus und X Primärstrahlen ist die Obergrenze der Anzahl der Schattenstrahlen gleich XN .

Ein weiteres Detail ist die Verarbeitung verschiedener Zähler. Die Stufen „Erneuern“ und „Schatten“ sollten wissen, wie viele Pfade aktiv sind. Die Zähler hierfür werden in der GPU (atomar) aktualisiert, was bedeutet, dass sie in der GPU verwendet werden, auch ohne zur CPU zurückzukehren. Leider ist dies in einem Fall nicht möglich: Die Optix Prime-Bibliothek muss die Anzahl der verfolgten Strahlen kennen. Dazu müssen wir die Informationen der Zähler einmal pro Iteration zurückgeben.

Fazit

In diesem Artikel wird erläutert, was Wellenfrontpfadverfolgung ist und warum eine Pfadverfolgung auf der GPU effektiv durchgeführt werden muss. Die praktische Implementierung wird auf der Lighthouse 2-Plattform vorgestellt, die Open Source ist und auf Github verfügbar ist .