Por que a recursão é proibida no OpenCL?

19

Eu gostaria de usar o OpenCL para acelerar a renderização de imagens rastreadas por raios, mas notei que a página da Wikipedia afirma que a recursão é proibida no Open CL. Isso é verdade? Como eu faço uso extensivo da recursão ao traçar raios, isso exigirá uma quantidade considerável de redesenho para se beneficiar da velocidade. Qual é a restrição subjacente que impede a recursão? Existe alguma maneira de contornar isso?

Trichoplax
fonte
2
As GPUs funcionam de maneira diferente. (Algumas arquiteturas) não têm o conceito de uma "pilha de programas" global; portanto, chamadas de função recursivas não são possíveis nessas. O OpenCL provavelmente adota o menor denominador comum, impedindo-o completamente de permanecer portátil nas GPUs. Mais recente hardware CUDA parece ter introduzido o suporte para recursão em algum momento: stackoverflow.com/q/3644809/1198654
glampert

Respostas:

27

É basicamente porque nem todas as GPUs podem suportar chamadas de função - e mesmo que possam, as chamadas de função podem ser bastante lentas ou ter limitações, como uma profundidade de pilha muito pequena.

O código de sombreador e o código de computação da GPU podem parecer ter chamadas de função em todo o lugar, mas, em circunstâncias normais, eles são 100% incorporados pelo compilador. O código da máquina executado pela GPU contém ramificações e loops, mas nenhuma chamada de função. No entanto, chamadas de função recursivas não podem ser incorporadas por razões óbvias. (A menos que alguns dos argumentos sejam constantes em tempo de compilação, de forma que o compilador possa dobrá-los e alinhar toda a árvore de chamadas).

Para implementar chamadas de função verdadeiras, você precisa de uma pilha. Na maioria das vezes, o código shader não usa uma pilha - as GPUs possuem grandes arquivos de registro e os shaders podem manter todos os seus dados em registros o tempo todo. É difícil fazer uma pilha funcionar porque (a) você precisaria de muito espaço na pilha para fornecer todos os warps que podem estar em vôo por vez e (b) o sistema de memória da GPU é otimizado para agrupar muito de transações de memória para obter alta taxa de transferência, mas isso ocorre às custas da latência, portanto, acho que operações de pilha, como salvar / restaurar variáveis ​​locais, seriam muito lentas.

Historicamente, as chamadas de função no nível do hardware não são muito úteis na GPU, pois faz mais sentido alinhar tudo no compilador. Portanto, os arquitetos de GPU não se concentraram em torná-los rápidos. Provavelmente, algumas compensações diferentes poderiam ser feitas, se houver uma demanda por chamadas eficientes no nível de hardware no futuro, mas (como acontece com tudo na engenharia), haverá um custo em outro lugar.

No que diz respeito ao traçado de raios, o modo como as pessoas geralmente lidam com esse tipo de coisa é criando filas de raios que estão sendo rastreados. Em vez de repetir, você adiciona um raio a uma fila e, em algum nível alto, possui um loop que continua processando até que todas as filas estejam vazias. Requer uma reorganização significativa do seu código de renderização, se você estiver iniciando com um raytracer recursivo clássico. Para obter mais informações, um bom artigo para ler sobre isso é o Wavefront Path Tracing .

Nathan Reed
fonte
6
Estou relutante em compartilhar esse molho secreto, mas tive muita sorte em ter uma contagem máxima fixa de rejeições e uma pilha de tamanho fixo (e um loop com um número fixo de iterações) para lidar com isso. Além disso (e esse é o verdadeiro molho secreto da imo!), Tenho meus materiais refletivos ou refrativos, mas nunca os dois, o que faz com que os raios não se dividam quando saltam. O resultado final de tudo isso é a renderização rastreada por raios do tipo recursivo, mas através da iteração de tamanho fixo, não da recursão.
Alan Wolfe
Como recursão da cauda?
Tanmay Patil
Você não precisaria de uma pilha para executar a recursão da cauda, ​​pois as funções recursivas da cauda podem ser convertidas em funções iterativas. O compilador OpenCL não faz isso automaticamente?
Anderson Green