Een histogram bouwen

Een histogram telt hoeveel invoerwaarden in elke bak vallen. Veel threads zullen dezelfde bak willen verhogen, dus dit is een probleem voor atomics. 📊

Elke thread leest één element, bepaalt de bijbehorende bak en verhoogt die bak. Zonder bescherming verliezen populaire bakken tellingen door races.

De eenvoudigste correcte oplossing is één atomicAdd per element, rechtstreeks naar het globale geheugen. Dit werkt, maar drukke bakken voeren threads na elkaar uit.

Wanneer gegevens zich ophopen in enkele bakken, richten duizenden threads zich op hetzelfde adres. Die concurrentie kan globale atomics pijnlijk traag maken.

Privatisering geeft elk blok een eigen privéhistogram in snel gedeeld geheugen. Threads botsen alleen binnen hun blok, niet in het hele grid.

Elk blok declareert een gedeelde array met een grootte die overeenkomt met het aantal bakken. Deze staat op de chip, waardoor atomics daar veel goedkoper zijn dan globale atomics.

Threads zetten gezamenlijk het gedeelde histogram op nul en roepen daarna __syncthreads aan, zodat niemand begint te tellen voordat het leegmaken klaar is.

Nu verhoogt elke thread atomisch zijn bak in het gedeelde geheugen. Hetzelfde atomicAdd, maar op de snelle kopie op de chip in plaats van in het globale geheugen.

Na een barrière tellen threads elke gedeelde bak met één atomicAdd op bij het globale histogram. Veel minder globale atomics dan voorheen.

Atomics in gedeeld geheugen zijn snel, en de dure globale atomics worden nu één keer per bak per blok uitgevoerd in plaats van één keer per element.

Het privéhistogram moet in het gedeelde geheugen passen. Als er te veel bakken zijn, verwerk je ze in meerdere doorgangen of val je terug op globale atomics.

Je hebt een histogram gebouwd met globale atomics en het daarna versneld met privatisering in gedeeld geheugen: leegmaken, lokaal tellen, samenvoegen. ✅