Bygg et histogram

Et histogram teller hvor mange inndata som faller i hver bin. Mange tråder vil forsøke å øke den samme bin-en, så dette er et problem for atomics. 📊

Hver tråd leser ett element, finner bin-en og øker den. Uten beskyttelse mister populære bin-er tellinger på grunn av kappløp.

Den enkleste korrekte løsningen er én atomicAdd per element direkte i globalt minne. Det fungerer, men populære bin-er serialiserer trådene.

Når dataene samler seg i noen få bin-er, samler tusenvis av tråder seg rundt samme adresse. Denne konkurransen kan gjøre globale atomics svært trege.

Privatisering gir hver blokk sitt eget private histogram i raskt delt minne. Trådene kolliderer bare innenfor blokken sin, ikke på tvers av hele grid-et.

Hver blokk deklarerer en delt tabell med størrelse lik antallet bin-er. Den ligger på brikken, så atomics der er langt billigere enn globale atomics.

Trådene setter det delte histogrammet til null i fellesskap og kaller deretter __syncthreads, slik at ingen teller før tømmingen er ferdig.

Nå øker hver tråd atomisk sin bin i delt minne. Samme atomicAdd, men på den raske kopien på brikken i stedet for i globalt minne.

Etter en barrierekall legger trådene hver delt bin til det globale histogrammet med én atomicAdd per bin. Det blir langt færre globale atomics enn tidligere.

Atomics i delt minne er raske, og de kostbare globale atomics utføres nå én gang per bin per blokk i stedet for én gang per element.

Det private histogrammet må få plass i delt minne. Hvis det er for mange bin-er, kan du dele dem opp i flere gjennomganger eller gå tilbake til globale atomics.

De bygde et histogram med globale atomics og gjorde det deretter raskere ved hjelp av privatisering i delt minne: tøm, tell lokalt, slå sammen. ✅