Dlaczego porównania są tak drogie na GPU?

Próbując poprawić wydajność mojej klasy wykrywania kolizji, odkryłem, że ~ 80% czasu spędzonego na GPU spędza na warunkach, jeśli tylko próbuję ustalić granice wiader, przez które powinna się zapętlać.

Dokładniej:

1. każdy wątek otrzymuje identyfikator, przez ten identyfikator pobiera swój trójkąt z pamięci (3 liczby całkowite), a przez te 3 pobiera swoje wierzchołki (3 liczby zmiennoprzecinkowe każdy).

2. Następnie przekształca wierzchołki w całkowite punkty siatki (obecnie 8 x 8 x 8) i przekształca je w granice trójkąta na tej siatce

3. Aby przekształcić 3 punkty w granice, znajduje min / max każdego wymiaru wśród każdego z punktów

Ponieważ w używanym przeze mnie języku programowania brakuje minmax, sam go stworzyłem, wygląda to tak:

procedure MinMax(a, b, c):
   local min, max

   if a > b:
      max = a
      min = b
   else:
      max = b
      min = a
   if c > max:
      max = c
   else:
      if c < min:
         min = c

   return (min, max)

Przeciętnie powinno to być 2,5 * 3 * 3 = 22,5 porównań, co ostatecznie pochłania znacznie więcej czasu niż rzeczywiste testy przecięcia krawędzi trójkąta (około 100 * 11-50 instrukcji).

W rzeczywistości stwierdziłem, że wstępne obliczenie wymaganych segmentów na jednostce centralnej (jednowątkowa, bez wektoryzacji), układanie ich w widoku GPU wraz z definicją segmentu i zmuszanie GPU do wykonania ~ 4 dodatkowych odczytów na wątek było 6 razy szybsze niż próba na miejscu ustalić granice. (zauważ, że są one ponownie obliczane przed każdym wykonaniem, ponieważ mam do czynienia z dynamicznymi siatkami)

Dlaczego więc porównanie jest tak strasznie wolne na GPU?

GPU to architektury SIMD. W architekturach SIMD każda instrukcja musi być wykonana dla każdego przetwarzanego elementu. (Jest wyjątek od tej reguły, ale rzadko pomaga).

Zatem w twojej MinMaxprocedurze nie tylko każde wywołanie musi pobrać wszystkie trzy instrukcje rozgałęzienia (nawet jeśli średnio oceniane są tylko 2,5), ale każda instrukcja przypisania również zajmuje cykl (nawet jeśli tak naprawdę nie zostanie „wykonana” ).

Ten problem jest czasem nazywany rozbieżnością wątków . Jeśli twoje urządzenie ma coś w rodzaju 32 linii wykonawczych SIMD, nadal będzie miało tylko jedną jednostkę pobierania. (Tutaj termin „wątek” zasadniczo oznacza „ścieżkę wykonania SIMD”.) Zatem wewnętrznie każda ścieżka wykonania SIMD ma bit „Jestem włączony / wyłączony”, a gałęzie w rzeczywistości po prostu manipulują tym bitem. (Wyjątkiem jest to, że w momencie, w którym każda linia SIMD zostaje wyłączona, jednostka pobierania ogólnie przeskoczy bezpośrednio do klauzuli „else”).

W twoim kodzie każda linia wykonania SIMD wykonuje:

compare (a > b)
assign (max = a if a>b)
assign (min = b if a>b)
assign (max = b if not(a>b))
assign (min = a if not(a>b))
compare (c > max)
assign (max = c if c>max)
compare (c < min if not(c>max))
assign (min = c if not(c>max) and c<min)

Może się zdarzyć, że na niektórych GPU konwersja warunkowa na predykację jest wolniejsza, jeśli GPU robi to sama. Jak zauważył @ PaulA.Clayton, jeśli twój język programowania i architektura ma predykcyjną operację warunkowego przenoszenia (szczególnie jedną z postaci if (c) x = y else x = z), możesz być w stanie zrobić to lepiej. (Ale prawdopodobnie nie wiele lepiej).

Również umieszczanie c < minwarunku wewnątrz elsenie c > maxjest konieczne. Na pewno nic ci nie oszczędza, a (biorąc pod uwagę, że GPU musi automatycznie przekonwertować go na predykcję) może być bolesne, że może być zagnieżdżone w dwóch różnych warunkowych.