Pourquoi la récursivité est-elle interdite dans OpenCL?

19

Je voudrais utiliser OpenCL pour accélérer le rendu des images raytracées, mais je remarque que la page Wikipedia affirme que la récursivité est interdite dans Open CL. Est-ce vrai? Comme j'utilise beaucoup la récursivité lors du lancer de rayons, cela nécessitera une refonte considérable afin de bénéficier de l'accélération. Quelle est la restriction sous-jacente qui empêche la récursivité? Y a-t-il un moyen de contourner cela?

trichoplax
la source
2
Les GPU fonctionnent d'une manière différente. (Certaines architectures) n'ont pas le concept d'une "pile de programmes" globale, donc les appels de fonctions récursives ne sont pas possibles dans celles-ci. OpenCL adopte probablement le plus petit dénominateur commun, le refusant ainsi complètement de rester portable sur les GPU. Le matériel CUDA plus récent semble avoir introduit la prise en charge de la récursivité à un moment donné: stackoverflow.com/q/3644809/1198654
glampert

Réponses:

27

C'est essentiellement parce que tous les GPU ne peuvent pas prendre en charge les appels de fonction - et même s'ils le peuvent, les appels de fonction peuvent être assez lents ou avoir des limitations telles qu'une très faible profondeur de pile.

Le code de shader et le code de calcul GPU peuvent sembler avoir des appels de fonction partout, mais dans des circonstances normales, ils sont tous 100% alignés par le compilateur. Le code machine exécuté par le GPU contient des branches et des boucles, mais aucun appel de fonction. Cependant, les appels de fonction récursifs ne peuvent pas être alignés pour des raisons évidentes. (À moins que certains des arguments ne soient des constantes au moment de la compilation, de telle sorte que le compilateur puisse les replier et aligner l'arborescence complète des appels.)

Pour implémenter de vrais appels de fonction, vous avez besoin d'une pile. La plupart du temps, le code de shader n'utilise pas du tout de pile: les GPU ont de gros fichiers de registre et les shaders peuvent conserver toutes leurs données dans des registres tout le temps. Il est difficile de faire fonctionner une pile car (a) vous auriez besoin de beaucoup d'espace de pile pour fournir toutes les nombreuses chaînes pouvant être en vol à la fois, et (b) le système de mémoire GPU est optimisé pour regrouper beaucoup de transactions de mémoire pour atteindre un débit élevé, mais cela se fait au détriment de la latence, donc je suppose que les opérations de pile comme la sauvegarde / restauration de variables locales seraient terriblement lentes.

Historiquement, les appels de fonction au niveau matériel n'ont pas été trop utiles sur le GPU, car il était plus logique de tout intégrer dans le compilateur. Les architectes GPU n'ont donc pas cherché à les rendre rapides. Des compromis différents pourraient probablement être faits, s'il existe une demande d'appels au niveau matériel efficaces à l'avenir, mais (comme pour tout ce qui concerne l'ingénierie), cela entraînera un coût ailleurs.

En ce qui concerne le lancer de rayons, la façon dont les gens gèrent généralement ce genre de chose consiste à créer des files d'attente de rayons qui sont en train d'être tracées. Au lieu de récursif, vous ajoutez un rayon à une file d'attente, et au niveau élevé quelque part, vous avez une boucle qui continue le traitement jusqu'à ce que toutes les files d'attente soient vides. Cependant, cela nécessite une réorganisation importante de votre code de rendu si vous commencez à partir d'un raytracer récursif classique. Pour plus d'informations, un bon article à lire à ce sujet est Wavefront Path Tracing .

Nathan Reed
la source
6
Je suis réticent à partager cette sauce secrète, mais j'ai eu de la chance d'avoir un nombre de rebonds maximum fixe et d'avoir une pile de taille fixe (et une boucle avec un nombre fixe d'itérations) pour gérer cela. Aussi (et c'est la vraie sauce secrète imo!) J'ai mes matériaux soit réfléchissants ou réfringents mais jamais les deux, ce qui fait que les rayons ne se séparent pas lorsqu'ils rebondissent. Le résultat final de tout cela est un rendu raytraced de type récursif, mais à travers une itération de taille fixe, pas une récursivité.
Alan Wolfe
Comme la récursivité de la queue?
Tanmay Patil
Vous n'auriez pas besoin d'une pile pour effectuer la récursivité de la queue, car les fonctions récursives de la queue peuvent être converties en fonctions itératives. Le compilateur OpenCL ne le fait-il pas automatiquement?
Anderson Green