Het idee van een reductieboom
Halveer bij elke stap het aantal actieve threads.
Het idee van een reductieboom is een gratis CUDA Academy-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject CUDA Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus CUDA Academy bevat in totaal 4 lessen.
Wat een reductie betekent
Een reductie brengt een volledige array terug tot één waarde, bijvoorbeeld door elk element op te tellen tot één totaal. Dit is een van de meest voorkomende patronen op een GPU. 🌳
De sequentiële manier is langzaam
Op een CPU tel je elementen één voor één op. Dat zijn O(n) sequentiële stappen, dus een miljoen getallen betekent een miljoen afhankelijke optellingen achter elkaar.
Optellen is associatief
De truc is dat optellen associatief is: (a+b)+c is gelijk aan a+(b+c). Je mag paren dus in elke gewenste groepering optellen.
Parallelle paren optellen
Omdat de groepering vrij is, kun je veel onafhankelijke paren tegelijk optellen. Elke thread verwerkt één paar, allemaal in één parallelle stap.
Bij elke stap halveren
Na één doorgang is de helft van de elementen verdwenen. Herhaal dit en het aantal actieve elementen blijft halveren: 8 naar 4 naar 2 naar 1.
Logaritmische diepte
Door het halveren ben je klaar in log2(n) stappen in plaats van n. Een miljoen elementen wordt in ongeveer 20 stappen samengevoegd, niet in een miljoen.
De boom visualiseren
Als je de paren tekent, ontstaat een binaire boom. De bladeren zijn de invoer, elk niveau halveert het aantal knooppunten en de wortel is je uiteindelijke som.
De stapgrootte verdubbelt bij elke doorgang
Een manier om dit te programmeren is: bij elke stap telt een thread zijn buur op die zich op afstand stride bevindt, waarna die stapgrootte bij elke doorgang door de gegevens verdubbelt.
for (int s = 1; s < blockDim.x; s *= 2) {
if (tid % (2 * s) == 0)
data[tid] += data[tid + s];
__syncthreads();
}Tussen stappen synchroniseren
Elk niveau hangt af van het voltooien van het vorige niveau, dus threads moeten bij een barrière wachten voordat ze het resultaat van hun partner lezen.
Werk tegenover span
Het totale aantal optellingen blijft ongeveer n, het werk. Maar de langste keten van afhankelijkheden, de span, krimpt tot log2(n). Evenveel werk, veel minder wachten.
Niet alleen optellen
Dezelfde boom werkt voor elke associatieve bewerking: maximum, minimum, product of logische AND. Vervang de operator en de structuur blijft hetzelfde.
Korte controle
Denk na over hoeveel parallelle stappen een boomreductie nodig heeft.
Samenvatting
Je hebt de reductieboom geleerd: tel paren parallel op, halveer bij elke stap en eindig in log2(n). Dit werkt voor elke associatieve operator. Houd nu warps bezig! 🎉
Leer C++ met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Het idee van een reductieboom” gratis?
Ja — de volledige tekst van “Het idee van een reductieboom” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus CUDA Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus CUDA Academy bevat in totaal 4 lessen.
Wat leer ik in “Het idee van een reductieboom”?
Halveer bij elke stap het aantal actieve threads. Je oefent met CUDA Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met CUDA Academy te beginnen?
Ervaring vooraf is niet nodig. CUDA Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Het idee van een reductieboom”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over CUDA Academy?
Ja. Elke les over CUDA Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Het idee van een reductieboom
- Warpdivergentie elimineren
- Sequentiële adressering
- Reductie over meerdere blocks