CUDA Academy · Lekcja

Idea drzewa redukcji

Zmniejszać o połowę liczbę aktywnych wątków w każdym kroku.

Lekcja 1 z 413 kroki

Idea drzewa redukcji to bezpłatna lekcja CUDA Academy na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej CUDA Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs CUDA Academy zawiera 4 lekcji w sumie.

Znaczenie redukcji

Redukcja sprowadza całą tablicę do jednej wartości, na przykład sumując wszystkie elementy do jednej końcowej sumy. To jeden z najczęstszych wzorców obliczeń na GPU. 🌳

Sposób sekwencyjny jest wolny

Na CPU dodaje się elementy jeden po drugim. To sekwencyjne kroki O(n), więc milion liczb oznacza milion zależnych dodawań wykonywanych kolejno.

Dodawanie jest łączne

Kluczowe jest to, że dodawanie jest łączne: (a+b)+c równa się a+(b+c). Można więc dodawać pary w dowolnie wybranym grupowaniu.

Dodawanie równoległych par

Ponieważ grupowanie nie ma znaczenia, można jednocześnie dodawać wiele niezależnych par. Każdy wątek obsługuje jedną parę, wszystko w jednym kroku równoległym.

Połowa w każdym kroku

Po jednym przejściu połowa elementów znika. Powtarzaj ten proces, a liczba aktywnych elementów będzie się stale zmniejszać o połowę: 8 do 4, do 2, do 1.

Głębokość logarytmiczna

Zmniejszanie o połowę oznacza zakończenie w log2(n) krokach zamiast w n. Milion elementów zostaje zredukowanych w około 20 krokach, a nie w milionie.

Wyobraź sobie drzewo

Narysowanie parowań tworzy binarne drzewo. Liście są danymi wejściowymi, każdy poziom zmniejsza liczbę węzłów o połowę, a korzeń zawiera końcową sumę.

Krok zwiększa odległość dwukrotnie

Jednym ze sposobów implementacji jest dodawanie przez wątek w każdym kroku sąsiada oddalonego o stride, przy czym ta odległość podwaja się w każdym przejściu przez dane.

for (int s = 1; s < blockDim.x; s *= 2) {
  if (tid % (2 * s) == 0)
    data[tid] += data[tid + s];
  __syncthreads();
}

Synchronizacja między krokami

Każdy poziom zależy od zakończenia poprzedniego, dlatego wątki muszą zaczekać na barierze, zanim odczytają wynik partnera.

Praca a rozpiętość

Łączna liczba dodawań pozostaje w przybliżeniu równa n — to praca. Jednak najdłuższy łańcuch zależności, czyli rozpiętość, skraca się do log2(n). Ta sama praca, znacznie mniej oczekiwania.

Nie tylko sumowanie

To samo drzewo działa dla dowolnej łącznej operacji: maksimum, minimum, iloczynu lub logicznego AND. Wystarczy zmienić operator, a struktura pozostaje taka sama.

Szybkie sprawdzenie

Zastanów się, ilu kroków równoległych wymaga redukcja za pomocą drzewa.

Odpowiedz w interaktywnej lekcji

Podsumowanie

Poznali Państwo drzewo redukcji: równolegle dodawać pary, zmniejszać ich liczbę o połowę w każdym kroku i kończyć w log2(n). Działa ono dla dowolnego łącznego operatora. Następnie zajmiemy się utrzymaniem aktywności warpów! 🎉

Bezpłatny start

Ucz się C++ dzięki korepetycjom AI — za darmo

Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.

Kursy: 30
Lekcje: 120

Zacznij naukę bezpłatnie Wyświetl pełny kurs

Często zadawane pytania

Czy lekcja „Idea drzewa redukcji” jest bezpłatna?

Tak — pełny tekst „Idea drzewa redukcji” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu CUDA Academy, przejdź na CoddyKit PRO. Kurs CUDA Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Idea drzewa redukcji”?

Zmniejszać o połowę liczbę aktywnych wątków w każdym kroku. Ćwiczysz CUDA Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć CUDA Academy?

Nie wymagamy żadnego doświadczenia. CUDA Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.

Ile czasu zajmuje lekcja „Idea drzewa redukcji”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji CUDA Academy?

Tak. Każda lekcja CUDA Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do CUDA Academy