¿Por qué está prohibida la recursividad en OpenCL?

19

Me gustaría usar OpenCL para acelerar la representación de imágenes con trazado de rayos, pero noto que la página de Wikipedia afirma que la recursión está prohibida en Open CL. ¿Es esto cierto? Como hago un uso extensivo de la recursividad cuando trazo de rayos, esto requerirá una considerable cantidad de rediseño para beneficiarse de la velocidad. ¿Cuál es la restricción subyacente que previene la recurrencia? ¿Hay alguna manera de evitarlo?

trichoplax
fuente
2
Las GPU funcionan de manera diferente. (Algunas arquitecturas) no tienen el concepto de una "pila de programas" global, por lo que no es posible realizar llamadas a funciones recursivas. OpenCL probablemente adopta el mínimo común denominador, por lo que no lo permite por completo para permanecer portátil en las GPU. El hardware más nuevo de CUDA parece haber introducido soporte para la recursividad en algún momento: stackoverflow.com/q/3644809/1198654
glampert

Respuestas:

27

Esencialmente porque no todas las GPU pueden admitir llamadas a funciones, e incluso si pueden, las llamadas a funciones pueden ser bastante lentas o tener limitaciones, como una profundidad de pila muy pequeña.

Puede parecer que el código de sombreado y el código de cálculo de GPU tienen llamadas de función por todas partes, pero en circunstancias normales el compilador los alinea al 100%. El código de máquina ejecutado por la GPU contiene ramas y bucles, pero no llamadas a funciones. Sin embargo, las llamadas a funciones recursivas no pueden alinearse por razones obvias. (A menos que algunos de los argumentos sean constantes de tiempo de compilación, de tal manera que el compilador pueda plegarlos e alinear todo el árbol de llamadas).

Para implementar llamadas de función verdaderas, necesita una pila. La mayoría de las veces, el código de sombreador no utiliza una pila en absoluto: las GPU tienen grandes archivos de registro y los sombreadores pueden mantener todos sus datos en registros todo el tiempo. Es difícil hacer que una pila funcione porque (a) necesitaría mucho espacio de pila para proporcionar todas las deformaciones que pueden estar en vuelo a la vez, y (b) el sistema de memoria de la GPU está optimizado para agrupar mucho de las transacciones de memoria para lograr un alto rendimiento, pero esto se produce a expensas de la latencia, por lo que supongo que las operaciones de apilamiento como guardar / restaurar variables locales serían muy lentas.

Históricamente, las llamadas a funciones a nivel de hardware no han sido demasiado útiles en la GPU, ya que tiene más sentido incorporar todo en el compilador. Por lo tanto, los arquitectos de GPU no se han centrado en hacerlos rápidos. Probablemente se podrían hacer algunas compensaciones diferentes, si hay una demanda de llamadas eficientes a nivel de hardware en el futuro, pero (como con todo en ingeniería) incurrirá en un costo en otro lugar.

En lo que respecta al trazado de rayos, la forma en que las personas suelen manejar este tipo de cosas es mediante la creación de colas de rayos que están en proceso de ser rastreados. En lugar de recurrir, agrega un rayo a una cola, y en el nivel superior en algún lugar tiene un bucle que sigue procesando hasta que todas las colas estén vacías. Sin embargo, requiere una reorganización significativa de su código de representación si está comenzando desde un trazador de rayos recursivo clásico. Para obtener más información, un buen artículo para leer sobre esto es Wavefront Path Tracing .

Nathan Reed
fuente
66
Soy reacio a compartir esta salsa secreta, pero he tenido bastante buena suerte teniendo un conteo de rebote máximo fijo y teniendo una pila de un tamaño fijo (y un bucle con un número fijo de iteraciones) para manejar esto. Además (¡y esta es la verdadera salsa secreta imo!) Tengo mis materiales reflectantes o refractivos, pero nunca ambos, lo que hace que los rayos no se dividan cuando rebotan. El resultado final de todo esto es el renderizado de rayos de tipo recursivo, pero a través de la iteración de tamaño fijo, no la recursividad.
Alan Wolfe
¿Te gusta la recursión de la cola?
Tanmay Patil
No necesitaría una pila para realizar la recursión de cola, ya que las funciones recursivas de cola se pueden convertir en funciones iterativas. ¿El compilador de OpenCL no hace esto automáticamente?
Anderson Green