Dlaczego rekurencja jest zabroniona w OpenCL?

19

Chciałbym użyć OpenCL do przyspieszenia renderowania obrazów ze śledzeniem promieni, ale zauważam, że strona Wikipedii twierdzi, że rekurencja jest zabroniona w Open CL. Czy to prawda? Ponieważ w dużym stopniu wykorzystuję rekurencję podczas raytracingu, będzie to wymagało znacznej przeprojektowania, aby skorzystać z przyspieszenia. Jakie jest podstawowe ograniczenie, które zapobiega rekurencji? Czy jest na to jakiś sposób?

trichopaks
źródło
2
Procesory graficzne działają w inny sposób. (Niektóre architektury) nie mają pojęcia globalnego „stosu programów”, więc rekurencyjne wywołania funkcji nie są w nich możliwe. OpenCL prawdopodobnie przyjmuje najniższy wspólny mianownik, tym samym całkowicie uniemożliwiając mu przenośność między procesorami graficznymi. Wydaje się, że
nowszy

Odpowiedzi:

27

Jest to zasadniczo spowodowane tym, że nie wszystkie procesory graficzne obsługują wywołania funkcji - a nawet jeśli tak, wywołania funkcji mogą być dość wolne lub mieć ograniczenia, takie jak bardzo mała głębokość stosu.

Kod modułu cieniującego i kod obliczeniowy GPU mogą wydawać się mieć wywołania funkcji w dowolnym miejscu, ale w normalnych okolicznościach wszystkie są w 100% zależne od kompilatora. Kod maszynowy wykonywany przez GPU zawiera rozgałęzienia i pętle, ale nie ma wywołań funkcji. Jednak wywołania funkcji rekurencyjnych nie mogą być wprowadzane z oczywistych powodów. (O ile niektóre argumenty nie są stałymi czasami kompilacji, w taki sposób, że kompilator może je złożyć i wstawić całe drzewo wywołań).

Aby zaimplementować prawdziwe wywołania funkcji, potrzebujesz stosu. Przez większość czasu kod modułu cieniującego w ogóle nie używa stosu - procesory graficzne mają duże pliki rejestrów, a moduły cieniujące mogą przechowywać wszystkie swoje dane w rejestrach przez cały czas. Ułożenie stosu jest trudne, ponieważ (a) potrzebujesz dużo miejsca na stosie, aby zapewnić wszystkie osnowy, które mogą być w locie w danym momencie, oraz (b) system pamięci GPU jest zoptymalizowany pod kątem łączenia wielu partii transakcji pamięciowych w celu osiągnięcia wysokiej przepustowości, ale odbywa się to kosztem opóźnienia, więc przypuszczam, że operacje na stosie, takie jak zapisywanie / przywracanie zmiennych lokalnych, byłyby strasznie wolne.

Historycznie wywołania funkcji na poziomie sprzętowym nie były zbyt przydatne na GPU, ponieważ bardziej sensowne jest wstawianie wszystkiego w kompilatorze. Dlatego architekci GPU nie skupili się na szybkim ich tworzeniu. Prawdopodobnie można by dokonać różnych kompromisów, jeśli w przyszłości pojawi się zapotrzebowanie na wydajne połączenia na poziomie sprzętowym, ale (jak w przypadku wszystkiego w inżynierii) poniesie to koszty gdzie indziej.

Jeśli chodzi o raytracing, ludzie zwykle radzą sobie z tego rodzaju rzeczami, tworząc kolejki promieni, które są w trakcie śledzenia. Zamiast rekurencji dodajesz promień do kolejki, a gdzieś na wysokim poziomie masz pętlę, która przetwarza przetwarzanie, dopóki wszystkie kolejki nie będą puste. Wymaga to jednak znacznej reorganizacji kodu renderującego, jeśli zaczynasz od klasycznego rekurencyjnego raytracera. Aby uzyskać więcej informacji, dobrym artykułem do przeczytania na ten temat jest Wavefront Path Tracing .

Nathan Reed
źródło
6
Niechętnie dzielę się tym tajnym sosem, ale miałem dość szczęścia, mając ustaloną maksymalną liczbę odrzuceń i posiadając stos o ustalonym rozmiarze (i pętlę ze stałą liczbą iteracji), aby sobie z tym poradzić. Również (i to jest prawdziwy tajny sos imo!) Mam materiały odbijające lub załamujące światło, ale nigdy oba, co sprawia, że ​​promienie nie rozszczepiają się, gdy się odbijają. Końcowym rezultatem tego wszystkiego jest renderowanie raytraced typu rekurencyjnego, ale poprzez iterację o stałym rozmiarze, a nie rekurencję.
Alan Wolfe
Jak rekursja ogona?
Tanmay Patil,
Nie potrzebujesz stosu do wykonania rekurencji ogona, ponieważ funkcje rekurencyjne ogona można przekształcić w funkcje iteracyjne. Czy kompilator OpenCL nie robi tego automatycznie?
Anderson Green,