Nouvel algorithme de suivi du GPU: suivi du chemin du front d'onde

Dans cet article, nous explorons l'important concept utilisé dans la plate-forme Lighthouse 2 récemment publiée. Le traçage de front d'onde , comme il s'appelle Lane, Karras et Aila de NVIDIA, ou le traçage de chemin en streaming, comme il était initialement appelé dans la thèse de maîtrise de Van Antwerp, joue un rôle crucial dans le développement de traceurs de chemin efficaces sur le GPU, et potentiellement de traceurs de chemin sur le CPU. Cependant, il est assez contre-intuitif, donc, pour le comprendre, il est nécessaire de repenser les algorithmes de traçage de rayons.

Occupation

L'algorithme de suivi de chemin est étonnamment simple et peut être décrit en quelques lignes de pseudocode:

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 

L'entrée est le rayon principal passant de la caméra au pixel de l'écran. Pour ce faisceau, nous déterminons l'intersection la plus proche avec la primitive de scène. S'il n'y a pas d'intersections, le faisceau disparaît dans le vide. Sinon, si le faisceau atteint la source de lumière, alors nous avons trouvé le chemin lumineux entre la source et la caméra. Si nous trouvons autre chose, nous effectuons alors une réflexion et une récursivité, en espérant que le faisceau réfléchi trouvera toujours la source d'éclairage. Notez que ce processus ressemble au chemin (de retour) d'un photon se reflétant sur la surface d'une scène.

Les GPU sont conçus pour effectuer cette tâche en mode multithread. Au début, il pourrait sembler que le lancer de rayons est idéal pour cela. Donc, nous utilisons OpenCL ou CUDA pour créer un flux pour un pixel, chaque flux exécute un algorithme qui fonctionne réellement comme prévu, et est assez rapide: il suffit de regarder quelques exemples avec ShaderToy pour comprendre à quelle vitesse le lancer de rayons peut être sur le GPU. Quoi qu'il en soit, la question est différente: ces traceurs de rayons sont-ils vraiment aussi rapides que possible ?


Cet algorithme a un problème. Le rayon primaire peut trouver la source lumineuse immédiatement, ou après une réflexion aléatoire, ou après cinquante réflexions. Le programmeur du CPU remarquera un débordement de pile potentiel ici; le programmeur GPU devrait voir le problème d'occupation . Le problème est causé par une récursion de queue conditionnelle: le chemin peut se terminer à la source de lumière ou continuer. Transférons cela à de nombreux threads: certains threads s'arrêteront et l'autre partie continuera à fonctionner. Après quelques réflexions, nous aurons plusieurs threads qui doivent continuer à calculer, et la plupart des threads attendront que ces derniers threads finissent de fonctionner. L'emploi est une mesure de la partie des threads GPU qui font un travail utile.

Le problème de l'emploi s'applique au modèle d'exécution des périphériques GPU SIMT. Les flux sont organisés en groupes, par exemple, dans le GPU Pascal (classe d'équipement NVidia 10xx) 32 threads sont combinés en une chaîne . Les threads dans warp ont un compteur de programme commun: ils sont exécutés avec une étape fixe, donc chaque instruction de programme est exécutée simultanément par 32 threads. SIMT signifie single instruction multiple thread , qui décrit bien le concept. Pour un processeur SIMT, un code avec conditions est complexe. Ceci est clairement indiqué dans la documentation officielle de Volta:


Exécution de code avec conditions dans SIMT.

Lorsqu'une certaine condition est vraie pour certains threads dans warp, les branches de l' instruction if sont sérialisées. Une alternative à l'approche «tous les threads font la même chose» est «certains threads sont désactivés». Dans le bloc if-then-else, l'occupation moyenne de la chaîne sera de 50%, sauf si tous les threads ont une cohérence concernant la condition.

Malheureusement, le code avec des conditions dans le ray tracer n'est pas si rare. Des rayons d'ombres ne sont émis que si la source de lumière n'est pas derrière le point d'ombrage, différents chemins peuvent entrer en collision avec différents matériaux, l'intégration avec la méthode de la roulette russe peut détruire ou laisser le chemin en vie, etc. Il s'avère que l'occupation devient la principale source d'inefficacité, et il n'est pas si facile de la prévenir sans mesures d'urgence.

Suivi du chemin de streaming

L'algorithme de suivi du chemin de diffusion en continu est conçu pour traiter la cause première du problème occupé. Le traçage de chemin de streaming divise l'algorithme de traçage de chemin en quatre étapes:

1. Générer
2. Étendre
3. Ombre
4. Connecter

Chaque étape est mise en œuvre comme un programme distinct. Par conséquent, au lieu d'exécuter un traceur de chemin complet en tant que programme GPU unique («noyau», noyau), nous devrons travailler avec quatre cœurs. De plus, comme nous le verrons bientôt, ils sont exécutés en boucle.

L'étape 1 («Générer») est responsable de la génération des rayons primaires. Il s'agit d'un noyau simple qui crée les points de départ et les directions des rayons en une quantité égale au nombre de pixels. La sortie de cette étape est un grand tampon de rayons et un compteur informant la prochaine étape du nombre de rayons à traiter. Pour les rayons primaires, cette valeur est égale à la largeur de l'écran multipliée par la hauteur de l'écran .

L'étape 2 («Renouveler») est le deuxième noyau. Il n'est exécuté qu'après la fin de l'étape 1 pour tous les pixels. Le noyau lit le tampon généré à l'étape 1 et traverse chaque rayon avec la scène. La sortie de cette étape est le résultat de l'intersection pour chaque rayon stocké dans le tampon.

L'étape 3 ("Shadow") est effectuée après l'achèvement de l'étape 2. Elle reçoit le résultat de l'intersection de l'étape 2 et calcule le modèle d'ombrage pour chaque chemin. Cette opération peut ou non générer de nouveaux rayons, selon que le chemin est terminé ou non. Les chemins qui génèrent le nouveau rayon (le chemin «s'étend») écrit le nouveau rayon (le «segment de chemin») dans le tampon. Les chemins qui échantillonnent directement les sources de lumière («échantillonnent explicitement l'éclairage» ou «calculent l'événement suivant») écrivent un faisceau d'ombre dans un deuxième tampon.

L'étape 4 («Connect») trace les rayons d'ombre générés à l'étape 3. Ceci est similaire à l'étape 2, mais avec une différence importante: les rayons de l'ombre doivent trouver n'importe quelle intersection, tandis que les rayons qui s'étendent doivent trouver l'intersection la plus proche. Par conséquent, un noyau distinct a été créé pour cela.

Après avoir terminé l'étape 4, nous obtenons un tampon contenant des rayons qui étendent le chemin. Après avoir pris ces rayons, nous passons à l'étape 2. Nous continuons à le faire jusqu'à ce qu'il n'y ait pas de rayons d'extension ou jusqu'à ce que nous atteignions le nombre maximal d'itérations.

Sources d'inefficacité

Un programmeur soucieux des performances verra beaucoup de moments dangereux dans un tel schéma d'algorithmes de traçage de chemin de streaming:

• Au lieu d'un seul appel de noyau, nous avons maintenant trois appels par itération , plus un noyau de génération. Défier les cœurs signifie une certaine augmentation de la charge, donc c'est mauvais.
• Chaque cœur lit un énorme tampon et écrit un énorme tampon.
• Le CPU a besoin de savoir combien de threads générer pour chaque cœur, donc le GPU doit dire au CPU combien de rayons ont été générés à l'étape 3. Le déplacement des informations du GPU vers le CPU est une mauvaise idée, et cela doit être fait au moins une fois par itération.
• Comment l'étape 3 écrit-elle les rayons dans le tampon sans créer d'espace partout? Il n'utilise pas de compteur atomique pour ça?
• Le nombre de chemins actifs diminue toujours, alors comment ce schéma peut-il aider du tout?

Commençons par la dernière question: si nous transférons un million de tâches vers le GPU, il ne générera pas un million de threads. Le nombre réel de threads exécutés simultanément dépend de l'équipement, mais dans le cas général, des dizaines de milliers de threads sont exécutés. Ce n'est que lorsque la charge tombe en dessous de ce nombre que nous remarquerons des problèmes d'emploi causés par un petit nombre de tâches.

Une autre préoccupation concerne les E / S à grande échelle des tampons. C'est en effet une difficulté, mais pas aussi grave que vous ne le pensez: l'accès aux données est hautement prévisible, en particulier lors de l'écriture dans des tampons, donc le retard ne pose pas de problème. En fait, les GPU ont été principalement développés pour ce type de traitement de données.

Les compteurs atomiques sont un autre aspect que les GPU gèrent très bien, ce qui est assez inattendu pour les programmeurs travaillant dans le monde du CPU. Le z-buffer nécessite un accès rapide et, par conséquent, la mise en œuvre de compteurs atomiques dans les GPU modernes est extrêmement efficace. En pratique, une opération d'écriture atomique est tout aussi coûteuse qu'une écriture non mise en cache dans la mémoire globale. Dans de nombreux cas, le retard sera masqué par une exécution parallèle à grande échelle dans le GPU.

Deux questions demeurent: les appels du noyau et le transfert de données bidirectionnel pour les compteurs. Ce dernier est en fait un problème, nous avons donc besoin d'un autre changement architectural: les threads persistants .

Les conséquences

Avant de plonger dans les détails, nous examinerons les implications de l'utilisation de l'algorithme de traçage de chemin de front d'onde. Tout d'abord, disons à propos des tampons. Nous avons besoin d'un tampon pour sortir les données de l'étape 1, c'est-à-dire rayons primaires. Pour chaque poutre, nous avons besoin de:

• Origine du rayon: trois valeurs flottantes, soit 12 octets
• Direction du rayon: trois valeurs flottantes, soit 12 octets

En pratique, il est préférable d'augmenter la taille du tampon. Si vous stockez 16 octets pour le début et la direction du faisceau, le GPU pourra les lire en une seule opération de lecture de 128 bits. Une alternative est une opération de lecture 64 bits suivie d'une opération 32 bits pour obtenir float3, ce qui est presque deux fois plus lent. Autrement dit, pour un écran de 1920 × 1080, nous obtenons: 1920x1080x32 = ~ 64 Mo. Nous avons également besoin d'un tampon pour les résultats d'intersection créés par le noyau Extend. Il s'agit d'un autre 128 bits par élément, soit 32 Mo. De plus, le noyau «Shadow» peut créer jusqu'à 1920 × 1080 extensions de chemin (limite supérieure), et nous ne pouvons pas les écrire dans le tampon à partir duquel nous lisons. C'est encore 64 Mo. Et enfin, si notre traceur de chemin émet des rayons d'ombre, alors c'est un autre tampon de 64 Mo. Après avoir tout résumé, nous obtenons 224 Mo de données, et ce uniquement pour l'algorithme de front d'onde. Ou environ 1 Go en résolution 4K.

Ici, nous devons nous habituer à une autre fonctionnalité: nous avons beaucoup de mémoire. Cela peut sembler. que 1 Go, c'est beaucoup, et il existe des moyens de réduire ce nombre, mais si vous approchez cela de manière réaliste, alors au moment où nous avons vraiment besoin de tracer les chemins en 4K, l'utilisation de 1 Go sur un GPU avec 8 Go sera le moindre de nos problèmes.

Plus grave que les besoins en mémoire, les conséquences seront pour l'algorithme de rendu. Jusqu'à présent, j'ai suggéré que nous devons générer un rayon d'extension et, éventuellement, un rayon d'ombre pour chaque thread dans le noyau Shadow. Mais que se passe-t-il si nous voulons effectuer une occlusion ambiante en utilisant 16 rayons par pixel? 16 rayons AO doivent être stockés dans le tampon, mais, pire encore, ils n'apparaîtront qu'à la prochaine itération. Un problème similaire se pose lors du traçage des rayons dans le style Whited: émettre un faisceau d'ombre pour plusieurs sources de lumière ou diviser un faisceau lors d'une collision avec du verre est presque impossible à réaliser.

D'un autre côté, le suivi du chemin du front d'onde résout les problèmes que nous avons répertoriés dans la section Occupation:

• À l'étape 1, tous les flux sans conditions créent des rayons primaires et les écrivent dans le tampon.
• Au stade 2, tous les flux sans conditions coupent les rayons avec la scène et écrivent les résultats de l'intersection dans le tampon.
• À l'étape 3, nous commençons à calculer les résultats d'intersection avec 100% d'occupation.
• À l'étape 4, nous traitons une liste continue de rayons d'ombre sans espaces.

Au moment où nous revenons à l'étape 2 avec les rayons survivants d'une longueur de 2 segments, nous avons à nouveau obtenu un tampon de rayons compact, qui garantit le plein emploi au démarrage du noyau.

De plus, il existe un avantage supplémentaire qui ne doit pas être sous-estimé. Le code est isolé en quatre étapes distinctes. Chaque cœur peut utiliser toutes les ressources GPU disponibles (cache, mémoire partagée, registres) sans tenir compte des autres cœurs. Cela peut permettre au GPU d'exécuter le code d'intersection avec la scène dans plus de threads, car ce code ne nécessite pas autant de registres que le code de shader. Plus il y a de threads, mieux vous pouvez masquer les retards.

Masquage des retards à temps plein amélioré, enregistrement en streaming: tous ces avantages sont directement liés à l'émergence et à la nature de la plate-forme GPU. Pour le GPU, l'algorithme de suivi de chemin de front d'onde est très naturel.

Est-ce que ça vaut le coup?

Bien sûr, nous avons une question: un emploi optimisé justifie-t-il les E / S des tampons et le coût de l'appel de cœurs supplémentaires?

La réponse est oui, mais prouver que ce n'est pas si facile.

Si nous revenons aux traceurs de piste avec ShaderToy pendant une seconde, nous verrons que la plupart d'entre eux utilisent une scène simple et codée en dur. Le remplacer par une scène à part entière n'est pas une tâche triviale: pour des millions de primitives, l'intersection du faisceau et la scène devient un problème complexe, dont la solution est souvent laissée à NVidia ( Optix ), AMD ( Radeon-Rays ) ou Intel ( Embree ). Aucune de ces options ne peut facilement remplacer la scène codée en dur dans le traceur de rayons artificiels CUDA. Dans CUDA, l'analogue le plus proche (Optix) nécessite un contrôle sur l'exécution du programme. Embree dans le CPU vous permet de tracer des faisceaux individuels à partir de votre propre code, mais le coût de ceci est un surdébit de performance significatif: il préfère tracer de grands groupes de faisceaux plutôt que des faisceaux individuels.


Écran de It's About Time rendu avec Brigade 1.

Le traçage du chemin du front d'onde sera-t-il plus rapide que son alternative (le mégacœur, comme Lane et ses collègues l'appellent) dépend du temps passé dans les cœurs (les grandes scènes et les shaders coûteux réduisent le dépassement de coût relatif par l'algorithme du front d'onde), sur la longueur maximale du chemin , l'emploi méga-core et les différences de charge sur les registres en quatre étapes. Dans une première version du Brigade Path Tracer original, nous avons constaté que même une scène simple avec un mélange de surfaces réfléchissantes et Lambert fonctionnant sur la GTX480 avait avantage à utiliser le front d'onde.

Traçage de chemin de streaming dans le phare 2

La plate-forme Lighthouse 2 possède deux traceurs de traçage de chemin de front d'onde. Le premier utilise Optix Prime pour la mise en œuvre des étapes 2 et 4 (étapes de l'intersection des rayons et des scènes); dans le second, Optix est utilisé directement pour implémenter cette fonctionnalité.

Optix Prime est une version simplifiée d'Optix qui ne traite que de l'intersection d'un ensemble de faisceaux avec une scène composée de triangles. Contrairement à la bibliothèque Optix complète, elle ne prend pas en charge le code d'intersection personnalisé et ne recoupe que les triangles. Cependant, c'est exactement ce qui est requis pour le traceur de chemin de front d'onde.

Le traceur de chemin de front d'onde basé sur Optix Prime est implémenté dans rendercore.cpp projet rendercore.cpp . L'initialisation d'Optix Prime commence dans la fonction Init et utilise rtpContextCreate . La scène est créée à l'aide de rtpModelCreate . Divers tampons de rayons sont créés dans la fonction SetTarget l'aide de rtpBufferDescCreate . Notez que pour ces tampons, nous fournissons les pointeurs de périphérique habituels: cela signifie qu'ils peuvent être utilisés à la fois dans Optix et dans des cœurs CUDA standard.

Le rendu commence dans la méthode Render . Pour remplir le tampon de rayon primaire, un noyau CUDA appelé generateEyeRays . Après avoir rempli le tampon, Optix Prime est appelé à l'aide de rtpQueryExecute . Avec lui, les résultats d'intersection sont écrits dans extensionHitBuffer . Notez que tous les tampons restent dans le GPU: à l'exception des appels du noyau, il n'y a pas de trafic entre le CPU et le GPU. L'étape «Shadow» est implémentée dans le noyau d' shade CUDA habituel. Son implémentation est dans pathtracer.cu .

Certains détails d'implémentation pour optixprime_b méritent d'être mentionnés. Premièrement, les rayons d'ombre sont tracés en dehors du cycle du front d'onde. C'est vrai: un rayon d'ombre n'affecte un pixel que s'il n'est pas bloqué, mais dans tous les autres cas, son résultat n'est nécessaire nulle part ailleurs. Autrement dit, le faisceau d'ombre est jetable , il peut être tracé à tout moment et dans n'importe quel ordre. Dans notre cas, nous utilisons cela en regroupant les rayons de l'ombre afin que le lot finalement tracé soit le plus grand possible. Cela a une conséquence désagréable: avec N itérations de l'algorithme du front d'onde et X rayons primaires, la limite supérieure du nombre de rayons d'ombre est égale à XN .

Un autre détail est le traitement des différents compteurs. Les étapes «Renouveler» et «Ombre» devraient savoir combien de chemins sont actifs. Les compteurs pour cela sont mis à jour dans le GPU (atomiquement), ce qui signifie qu'ils sont utilisés dans le GPU, même sans retourner au CPU. Malheureusement, dans l'un des cas, cela est impossible: la bibliothèque Optix Prime doit connaître le nombre de rayons tracés. Pour ce faire, nous devons renvoyer les informations des compteurs une fois par itération.

Conclusion

Cet article explique ce qu'est le traçage de chemin de front d'onde et pourquoi il est nécessaire d'effectuer efficacement le traçage de chemin sur le GPU. Son implémentation pratique est présentée dans la plateforme Lighthouse 2, qui est open source et disponible sur Github .