CUDA Academy · leksjon

Tanken bak et reduksjonstre

Halver antallet aktive tråder i hvert trinn

Leksjon 1 av 413 trinn

Tanken bak et reduksjonstre er en gratis leksjon i CUDA Academy på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i CUDA Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i CUDA Academy inneholder totalt 4 leksjoner.

Hva reduksjon betyr

En reduksjon samler en hel tabell til én verdi, for eksempel ved å summere alle elementene til én total. Dette er et av de vanligste GPU-mønstrene. 🌳

Den sekvensielle metoden er treg

På en CPU legger De sammen elementene ett etter ett. Det er O(n) sekvensielle trinn, så én million tall betyr én million avhengige addisjoner etter hverandre.

Addisjon er assosiativ

Trikset er at addisjon er assosiativ: (a+b)+c er lik a+(b+c). Derfor står De fritt til å legge sammen parene i den grupperingen De ønsker.

Legg sammen parallelle par

Siden grupperingen er valgfri, kan De legge sammen mange uavhengige par samtidig. Hver tråd håndterer ett par, alt i ett parallelt trinn.

Halvering for hvert trinn

Etter én gjennomgang er halvparten av elementene borte. Gjenta, og antallet aktive elementer fortsetter å halveres: 8 til 4 til 2 til 1.

Logaritmisk dybde

Halvering betyr at De blir ferdig på log2(n) trinn i stedet for n. Én million elementer reduseres på omtrent 20 trinn, ikke én million.

Se for Dem treet

Når De tegner paringene, får De et binært tre. Bladene er inndataene, hvert nivå halverer antallet noder, og roten er den endelige summen.

Spranget dobles for hver gjennomgang

Én måte å kode dette på er at en tråd i hvert trinn legger til naboen med avstanden stride, og at dette spranget dobles for hver gjennomgang av dataene.

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

Synkroniser mellom trinnene

Hvert nivå avhenger av at det forrige er ferdig, så trådene må vente ved en barriere før de leser resultatet fra partneren sin.

Arbeid mot spenn

Det totale antallet addisjoner er fortsatt omtrent n, altså arbeidet. Men den lengste avhengighetskjeden, spennet, krymper til log2(n). Samme arbeid, langt mindre venting.

Ikke bare summering

Det samme treet fungerer for enhver assosiativ operasjon: maks, min, produkt eller logisk AND. Bytt operator, så består strukturen.

Rask kontroll

Tenk over hvor mange parallelle trinn en trereduksjon trenger.

Besvar den i den interaktive leksjonen

Oppsummering

De lærte reduksjonstreet: legg sammen par parallelt, halver for hvert trinn, og bli ferdig på log2(n). Det fungerer for enhver assosiativ operator. Nå skal vi holde warps i arbeid! 🎉

Gratis å komme i gang

Lær deg C++ med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 30
Leksjoner: 120

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Tanken bak et reduksjonstre» gratis?

Ja – hele teksten i «Tanken bak et reduksjonstre» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av CUDA Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i CUDA Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Tanken bak et reduksjonstre»?

Halver antallet aktive tråder i hvert trinn Du øver på CUDA Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med CUDA Academy?

Ingen tidligere erfaring er nødvendig. CUDA Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.

Hvor lang tid tar leksjonen «Tanken bak et reduksjonstre»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne CUDA Academy-leksjonen?

Ja. Alle CUDA Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til CUDA Academy