DIKU Bits: Effektiv beregning af histogrammer på GPU

Taler

Troels Henriksen, Postdoc, Programming Languages and Theory of Computing ved Datalogisk Institut.

Abstract

Den evige jagt på ydelse betyder at vores datamater bliver gradvist mere vanskelige at programmere, typisk ved at de bliver mere parallelle.  For at gøre maskinerne nemmere tilgængelige designer vi så programmeringssprog og biblioteker, som indkapsler typiske programmeringsmønstre, og implementerer dem effektivt én gang for alle.  Et godt programmeringssprog til en parallel maskine bør således stille programmeringsmekanismer til rådighed som både er nemme at ræsonnere omkring for et menneske, men som også kan afvikles effektivt.

I praksis kan vi dog ikke bare designe et programmeringssprog med hundredevis af forskellige mekanismer til ethvert tænkeligt formål, da hver mekanisme gør sproget både sværere at forstå og at implementere, idet man skal tage højde for alle tænkelige kombinationer af de tilgængelige mekanismer.  Udfordringen er således at finde et passende “parallelt ordforråd” som vi tilbyder programmøren, som hverken er for stort eller for begrænset.  Heldigivs har det vist sig, at de højereordensfunktioner vi kender fra funktionsprogrammering, såsom ‘map’, ‘reduce’, og ‘scan’, faktisk er velegnede til parallel programmering, og at man ved at sætte dem sammen, kan udtrykke utroligt mange parallelle algoritmer, samtidigt med at de er forholdsvist nemme at implementere i programmeringssprog.

De velkendte højereordensfunktioner er dog ikke fuldt tilstrækkelige. I min præsentation vil jeg gennemgå typer af problemer der ikke kan udtrykkes effektivt ved disse gængse funktioner, og motivere en ny højereordensfunktion der beregner såkaldte “generaliserede histogrammer”.  Disse viser sig nyttige i ret forskellige problemer, lige fra k-means clustering til partikelsimulering.  Jeg kommer til at snakke både om semantikken for sådanne generaliserede histogrammer, samt snakke om hvordan man implementerer dem med meget høj ydelse på moderne GPUer, hvor det især er vigtigt at tage højde for cache-hierarkiet.

Læs mere på di.ku.dk
______
DIKU Bits er en åben og gratis foredragsrække målrettet bachelorstuderende på DIKU og relaterede fagområder, men det er åbent for alle interesserede.
*This DIKU Bits lecture will be in Danish*