Dlaczego w programowaniu GPU pożądana jest wydajność pracy?

Czytałem następujący artykuł na temat wykonywania równoległego skanowania w CUDA:

https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch39.html

W artykule położono nacisk na uczynienie skanowania „wydajnym”. Innymi słowy, algorytm GPU nie powinien wykonywać więcej dodatków niż algorytm CPU, O (n). Autorzy przedstawiają dwa algorytmy, jeden „naiwny”, który dodaje dodatki O (nlogn), i jeden, który uważają za „wydajny”. Jednak efektywny algorytm pracy wykonuje dwa razy więcej iteracji pętli.

Z mojego zrozumienia, procesory graficzne są po prostu gigantycznymi procesorami SIMD i powinny działać w trybie blokowania. Wydaje się, że wykonanie dwukrotnie większej liczby pętli w algorytmie „wydajnej pracy” sugeruje, że wiele wątków będzie bezczynnych i na dłuższą metę obniży wydajność. czego mi brakuje?

Po pierwsze, re: „Procesory graficzne to po prostu gigantyczne procesory SIMD i powinny działać krok po kroku”, jest to nieco bardziej skomplikowane. Cały GPU nie działa ramię w ramię. Wątki shaderów są zorganizowane w grupy 32 zwane „warps” (w NVIDIA; w AMD są to grupy 64 zwane „frontami”, ale ta sama koncepcja). W warp wszystkie wątki działają w trybie blokowania jako tablica SIMD. Jednak różne osnowy nie są ze sobą w kontakcie. Ponadto niektóre osnowy mogą być aktywnie uruchomione, a inne mogą być zawieszone, podobnie jak wątki procesora. Warps można zawiesić, ponieważ czekają na coś (na przykład na zwrócenie transakcji pamięci lub bariery do usunięcia), lub ponieważ nie ma „

Wróćmy do twojego pytania. Widzę dwa sposoby, w których algorytm „wydajnej pracy” z tego artykułu wygląda na bardziej wydajny niż algorytm „naiwny”.

1. Wydajna wersja wymaga na początek połowy liczby wątków. W naiwnym algorytmie mają jeden wątek na element tablicy; ale w wersji efektywnej pracy każdy wątek działa na dwóch sąsiadujących elementach tablicy, dlatego potrzebują tylko połowy tyle wątków, co elementy tablicy. Mniej wątków oznacza mniej wypaczeń, więc większa część wypaczeń może aktywnie działać.

2. Chociaż wydajna wersja wymaga więcej kroków, jest to równoważone przez fakt, że liczba aktywnych wątków zmniejsza się szybciej, a całkowita liczba aktywnych wątków we wszystkich iteracjach jest znacznie mniejsza. Jeśli osnowa nie ma aktywnych wątków podczas iteracji, przeskoczy tylko do następnej bariery i zostanie zawieszona, umożliwiając uruchomienie innych osnowy. Mając mniej aktywnych wypaczeń, często można się spłacić w czasie wykonania. (Implikuje to, że kod GPU musi być zaprojektowany w taki sposób, aby aktywne wątki były spakowane razem w jak najmniejszej liczbie wypaczeń - nie chcesz, aby były one rozproszone, ponieważ nawet jeden aktywny wątek zmusi całe wypaczenie pozostać aktywnym).

   Rozważ liczbę aktywnych wątków w naiwnym algorytmie. Patrząc na rycinę 2 w tym artykule, widać, że wszystkie wątki są aktywne, z wyjątkiem pierwszych 2 ^k na k- tej iteracji. Tak więc w przypadku N wątków liczba aktywnych wątków jest równa N - 2 ^k . Na przykład przy N = 1024 liczba aktywnych wątków na iterację wynosi:

   1023, 1022, 1020, 1016, 1008, 992, 960, 896, 768, 512
   

   Jeśli przekonwertuję to na liczbę aktywnych wypaczeń (dzieląc przez 32 i zaokrąglając w górę), otrzymuję:

   32, 32, 32, 32, 32, 31, 30, 28, 24, 16
   

   za sumę 289. Z drugiej strony efektywny algorytm zaczyna się od połowy większej liczby wątków, a następnie zmniejsza o połowę liczbę aktywnych w każdej iteracji, aż spadnie do 1, a następnie zaczyna się podwajać, aż wróci do znów połowa wielkości tablicy:

    512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
   

   Konwertowanie tego na aktywne wypaczenia:

   16, 8, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 8, 16
   

   Suma wynosi 71, czyli tylko o jedną czwartą tyle. Widać więc, że w trakcie całej operacji liczba aktywnych wypaczeń jest znacznie mniejsza dzięki wydajnemu algorytmowi. (W rzeczywistości, w przypadku długiego przebiegu w środku jest tylko garść aktywnych wypaczeń, co oznacza, że ​​większość układu nie jest zajęta. Jeśli uruchomione są dodatkowe zadania obliczeniowe, np. Z innych strumieni CUDA, mogą się rozwinąć, aby wypełnić to niezajęte miejsce).

Biorąc to wszystko pod uwagę, niefortunnie jest, że artykuł o GPU Gems nie wyjaśnia tego wszystkiego, skupiając się na analizie dużej liczby „dodatków”, która, choć nie całkowicie nieistotna, pomija wiele szczegółów na temat tego, dlaczego ten algorytm jest szybciej.