DIKU Bits: Effektiv beregning af histogrammer på GPU

Troels Henriksen

*This DIKU Bits lecture will be in Danish*

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.

Tre spørgsmål til Troels Henriksen

Hvilket kursus underviser du i?
(BSc og MSc) CompSys på datalogi-BSc, HPPS på DatØk/DS BSc, og Parallel Functional Programming på datalogi MSc (som næste år skifter navn til Data Parallel Programming).

Hvilken teknologi/forskning/projekt/start up er du spændt på at se en udvikling af?
Jeg er især interesseret i at se hvordan processordesignere kommer til at håndtere afslutningen på Moore's lov.  Hvis vi stadigvæk vil have hurtigere maskiner, så skal vi til at lave dem mere specialiserede, og typisk også mere vanskelige at programmere.  Disse svagheder skal der så kompenseres for i software, f.eks. ved at lave nye programmeringssprog.

En anden udvikling jeg finder ret fascinerende er heuristiske løsninger af NP-komplete-problemer.  Det er fascinerende hvordan SAT-problemet (som kort fortalt handler om at finde løsninger på boolske ligninger) er gået fra at være uløseligt for alt andet end trivielle problemstørrelser, til at være en teknik der rutimemæssigt bruges til trods for at problemet på et teoretisk plan stadigvæk er ekstremt svært at løse.

Hvad er din favorit sketch fra DIKUrevy?
L'Amour fra 2014.