L'idea dell'albero di riduzione
Dimezzi i thread attivi a ogni passaggio.
L'idea dell'albero di riduzione è una lezione CUDA Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento CUDA Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso CUDA Academy include 4 lezioni in totale.
Cosa significa riduzione
Una riduzione comprime un intero array in un solo valore, ad esempio sommando tutti gli elementi fino a ottenere un unico totale. È uno dei pattern più comuni sulle GPU. 🌳
Il metodo sequenziale è lento
Su una CPU si sommano gli elementi uno dopo l’altro. Sono n passaggi sequenziali O(n), quindi un milione di numeri richiede un milione di addizioni dipendenti eseguite in sequenza.
L’addizione è associativa
Il punto è che l’addizione è associativa: (a+b)+c equivale a a+(b+c). È quindi possibile sommare le coppie secondo qualsiasi raggruppamento.
Sommare coppie in parallelo
Poiché il raggruppamento è libero, è possibile sommare contemporaneamente molte coppie indipendenti. Ogni thread gestisce una coppia, tutto in un singolo passaggio parallelo.
Dimezzare a ogni passaggio
Dopo un passaggio, metà degli elementi è stata eliminata. Ripetendo l’operazione, il numero di elementi attivi continua a dimezzarsi: da 8 a 4, poi a 2 e infine a 1.
Profondità logaritmica
Dimezzare significa terminare in log2(n) passaggi anziché n. Un milione di elementi si riduce in circa 20 passaggi, non in un milione.
Visualizzare l’albero
Rappresentare graficamente gli abbinamenti forma un albero binario. Le foglie sono gli input, ogni livello dimezza i nodi e la radice contiene la somma finale.
Lo stride raddoppia a ogni passaggio
Un modo per implementarlo è il seguente: a ogni passaggio, un thread somma il vicino a distanza stride, e tale stride raddoppia a ogni attraversamento dei dati.
for (int s = 1; s < blockDim.x; s *= 2) {
if (tid % (2 * s) == 0)
data[tid] += data[tid + s];
__syncthreads();
}Sincronizzarsi tra i passaggi
Ogni livello dipende dal completamento di quello precedente, quindi i thread devono attendere a una barriera prima di leggere il risultato del proprio partner.
Lavoro e span
Il numero totale di addizioni rimane circa n: questo è il lavoro. Tuttavia, la catena di dipendenze più lunga, lo span, si riduce a log2(n). Stesso lavoro, molto meno tempo di attesa.
Non solo somme
Lo stesso albero funziona per qualsiasi operazione associativa: massimo, minimo, prodotto o AND logico. Si sostituisce l’operatore, mentre la struttura rimane invariata.
Verifica rapida
Rifletta su quanti passaggi paralleli richiede una riduzione ad albero.
Riepilogo
Ha appreso l’albero di riduzione: sommare coppie in parallelo, dimezzare a ogni passaggio e terminare in log2(n). Funziona con qualsiasi operatore associativo. Ora manterrà occupati i warp! 🎉
Domande Frequenti
La lezione «L'idea dell'albero di riduzione» è gratuita?
Sì — il testo completo di «L'idea dell'albero di riduzione» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso CUDA Academy, passa a CoddyKit PRO. Il corso CUDA Academy include 4 lezioni in totale.
Cosa imparerò in «L'idea dell'albero di riduzione»?
Dimezzi i thread attivi a ogni passaggio. Eserciti CUDA Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare CUDA Academy?
Non è richiesta alcuna esperienza precedente. CUDA Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «L'idea dell'albero di riduzione»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione CUDA Academy?
Sì. Ogni lezione CUDA Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- L'idea dell'albero di riduzione
- Eliminare la divergenza dei warp
- Indirizzamento sequenziale
- Riduzione finale su più blocchi