Pieter Hijma promoveerde in juni aan de Vrije Universiteit Amsterdam op de stepwise refinement for performance-methode. Zijn proefschrift, getiteld ‘Programming many-cores on multiple levels of abstraction’, is online beschikbaar. Henri Bal is hoogleraar informatica aan de VU en trad op als promotor van Hijma. Het proefschrift van Ben van Werkhoven is getiteld ‘Scientific supercomputing with graphics processing units’ en is eveneens online beschikbaar.

26 October 2015

Bij het programmeren van multicoresystemen moet de ontwikkelaar een lastige keuze maken: op hoog abstractieniveau blijven, met mogelijk gevolgen voor de performance, of afdalen naar de architectuurdetails, waardoor de code weer minder generiek en vaak lastiger te begrijpen wordt. De UvA ontwikkelde een aanpak om programmeur en compiler samen de gevolgen van deze uitruil te laten verkennen.

Supercomputers gebruiken steeds vaker manycores voor grootschalige berekeningen. De krachtigste supercomputer van dit moment (zie de top 500 van supercomputers), de Chinese Tianhe-2, gebruikt daarvoor de Intel Xeon Phi. Deze is gebaseerd op een Pentium-architectuur van zo’n tien jaar geleden, maar elke chip bevat rond de zestig processoren met elk ook nog zestien vectoreenheden, goed voor een totaal van rond de duizend rekenkernen per chip. De nummer twee in de top 500 (Titan, van Oak Ridge National Lab) gebruikt gpu’s van Nvidia, die oorspronkelijk voor computergraphics zijn ontworpen. Moderne gpu’s hebben vele duizenden rekenkernen.

Kenmerkend voor beide vormen van manycores is dat ze volledig inzetten op grootschalig parallellisme: elke rekenkern is vele malen langzamer dan een rekenkern van een gewone moderne cpu, maar door er duizenden tegelijk op één chip te hebben (en miljoenen in een supercomputer) kunnen spectaculaire prestaties worden bereikt.

Manycores hebben echter een groot probleem: voor de programmeur is het ontzettend moeilijk om met zulk grootschalig parallellisme om te gaan. Gewone cpu’s doen weliswaar intern talloze berekeningen tegelijk, ze gebruiken enorm veel transistoren om het programmeermodel er aan de buitenkant sequentieel uit te doen zien en het parallellisme voor programmeurs te verbergen – denk aan out-of-order-executie, superscalar-technieken en diepe pijplijnen. Programmeurs zijn daardoor gepokt en gemazeld in het sequentiële programmeermodel.

Bij verdere schaling is het echter onhoudbaar om het parallellisme nog te verbergen. De nieuwe manycore-architecturen stappen daarom radicaal af van het sequentiële programmeermodel en bieden juist expliciet grootschalig parallellisme aan. Maar programmeurs die bijvoorbeeld een naïeve omzetting van cpu-code naar een gpu doen, weten vaak niet meer dan een tiende te halen van wat de grafische processor echt kan.

 advertorial 

Machine Learning Conference: 30 March 2022

Machine learning is taking the industry by storm. On 30 March 2022, Bits&Chips organizes the fourth edition of the Machine Learning Conference as a live event in ’s-Hertogenbosch. Interested in giving a talk? We welcome your proposal!

Het optimaliseren van gpu-code blijkt ontstellend moeilijk te zijn. Om te beginnen, moeten er miljoenen berekeningen tegelijk worden gestart om de cores überhaupt bezig te houden, en de toepassing moet zich daarvoor lenen. Daarnaast zullen de cores moeten samenwerken, maar de manier om informatie onderling te delen, is uitermate complex; er zijn verschillende gedeelde geheugens, maar die zijn klein of traag. Bij sommige gpu-geheugens is de performance ook nog afhankelijk van het toegangspatroon van alle cores samen, waardoor gangbare aanpakken bij gewone cachegeheugens (bijvoorbeeld sequentiële toegang) bij gpu’s opeens funest kunnen zijn. Daarnaast is de synchronisatie van al die miljoenen taken op duizenden cores zeer ingewikkeld, terwijl dat de performance sterk kan beïnvloeden.

Kortom: een manycore is een machine die een heleboel architectuurdetails blootstelt aan de softwareontwikkelaar, wat het programmeren erg ingewikkeld maakt. Daar staat tegenover dat de programmeur de volledige controle heeft en uitgebreide mogelijkheden heeft om forse optimalisaties door te voeren. In de praktijk zal hij echter veel tijd kwijt zijn met – vaak stuurloos – uitproberen van aanpakken, zeker wanneer hij niet bekend is met manycore-architecturen.

Steeds meer details

Er zijn verschillende aanpakken geprobeerd om de pijn te verzachten. Als alternatief voor Cuda en Opencl, de standaard low-level gpu-programmeeromgevingen, zijn er talen zoals Openacc bedacht die met annotaties van sequentiële code werken. Door het hogere abstractieniveau zijn ze makkelijker te programmeren, maar dat gaat ten koste van de performance. Ook is gepoogd om cpu-code automatisch om te zetten naar gpu-code, maar dit lijkt alleen in specifieke domeinen te slagen. Een goede methode om manycores (zoals gpu’s) systematisch te programmeren en een goede performance te halen, ontbreekt.

Op de Vrije Universiteit in Amsterdam hebben we ons daarom over zo’n methode gebogen. Het resultaat is een aanpak die we stepwise refinement for performance hebben gedoopt. Het kernidee is om programmeurs te laten beginnen op een hoog niveau dat veel architectuurdetails abstraheert. Vervolgens geeft de compiler advies om het programma verder te optimaliseren. Wanneer dat onvoldoende lukt, kan steeds een niveau worden afgezakt, waar meer details van de architectuur worden vrijgegeven. Ook de compiler daalt mee af en kan steeds gedetailleerde aanwijzingen geven. Op deze manier werken de compiler en de programmeur systematisch samen.

Bal figuur 1
Door met een hiërarchie te werken waarin steeds meer architectuurdetails worden vrijgegeven, kunnen programmeurs gericht hun implementaties voor een manycore optimaliseren.

Een van de voordelen van deze aanpak is dat programmeurs goed de afweging kunnen maken tussen een hoog abstractieniveau met goede leesbaarheid en portabiliteit tussen verschillende multicores, en een laag abstractieniveau met mogelijk hogere performance. Het grootste voordeel is misschien wel dat de geschiedenis van het optimalisatieproces goed gedocumenteerd is. Doorgaans is geoptimaliseerde code moeilijk te begrijpen en is het niet duidelijk waarom bepaalde beslissingen zijn genomen. Onze methode maakt duidelijk welke stappen zijn gezet op elk niveau, op basis van welke compilerfeedback, en hoe de veranderingen zich verhouden tot de hardware.

Onze implementatie van deze methodologie wordt ondersteund door een groot compilersysteem (geschreven in de metaprogrammeertaal Rascal van het CWI) genaamd Many-Core Levels (MCL). Het systeem bevat een C-achtige programmeertaal en een taal om manycores te beschrijven en de verschillende abstractieniveaus te definiëren. Deze hardwarebeschrijvingen worden opgenomen in een hiërarchie met steeds meer details voor de programmeur en de compiler.

Naast feedback geven kan het systeem de uiteindelijke code vertalen naar Opencl voor executie op een specifiek manycore device, zoals een gpu of een Xeon Phi. Bovendien bevat het systeem een makkelijke manier om taken op een cluster van meerdere gpu’s te draaien, zelfs als de nodes verschillende soorten manycores hebben. Een goed voorbeeld is het Das-systeem (Distributed ASCI Supercomputer), dat honderden Nederlandse informatici al bijna twee decennia lang gebruiken: Das-5 bevat zes clusters met allerlei soorten manycores.

Vingerafdruk

Een mooie illustratie van de werking geeft het promotieproject van Ben van Werkhoven. Hij heeft zich gebogen over het automatisch analyseren van multimediamateriaal voor forensische doeleinden. Bij forensisch onderzoek moeten vaak talloze harddisks en mobiele apparaten worden onderzocht op verdachte zaken, waarbij alle mogelijke soorten media moeten worden geanalyseerd. Gegeven de enorm hoge resolutie van moderne beeldsensoren en de miljoenen foto’s die vaak moeten worden geanalyseerd, is dit een zeer tijdrovende rekenklus.

Een klus die echter zeer geschikt is voor manycoreclusters: de foto’s kunnen worden verdeeld over verschillende nodes en de miljoenen pixels van elke foto kunnen worden doorgerekend door de duizenden cores. Van Werkhoven heeft in het Nederlandse Commit-project onderzocht hoe die analyses naar gpu’s konden worden gebracht, wat indertijd zeer tijdrovend maar uiteindelijk zeer succesvol was. Hij spitste zich onder meer toe op het uitvoeren van convoluties op gpu’s, een belangrijke beeldverwerkingsbouwsteen die simpel gezegd neerkomt op het toepassen van een filter op een plaatje.

In een project van het Netherlands Escience Centre (NLESC), de VU en het NFI werken we nu samen om zulke analyses te versnellen met behulp van manycores en onze nieuwe methode. Deze toepassing bleek een mooie testcase, omdat er belangrijke trade-offs zijn waarin alleen de programmeur – die weet welke data er worden geanalyseerd – de juiste afwegingen kan maken.

Bij een convolutie worden bijvoorbeeld dezelfde data voor meerdere berekeningen gebruikt. In een naïeve implementatie worden gegevens meerdere keren geladen, maar gpu’s kunnen ze tijdelijk opslaan in een klein, snel scratchpad-geheugen. Het parallellisme wordt echter weer beperkt wanneer dit geheugen te veel wordt gebruikt.

Een dergelijk programma schrijven met MCL gaat ongeveer als volgt: een programmeur begint op het hoogste abstractieniveau met Perfect, een geïdealiseerde manycoremachine die een aantal programmeerabstracties definieert. Figuur 2 toont een gedeelte van de Perfect-hardwarebeschrijving samen met het convolutieprogramma. Doordat de software de abstracties van de hardwarebeschrijving gebruikt, beschikt de compiler over kennis rond de context waarin de software opereert. De hardwarebeschrijving definieert bovendien hoe deze abstracties zich verhouden tot het fysieke device, waardoor een implementatie kan worden gegenereerd. Deze implementatie haalt een doorvoersnelheid van ongeveer 130 Gflops (floating point-operaties per seconde).

De Perfect-implementatie negeert echter hergebruik van de data omdat de geïdealiseerde machine geen scratchpad-geheugen aanbiedt. Een programmeur die meer performance wil halen, kan het programma daarom automatisch vertalen naar een lager abstractieniveau. Hij komt dan uit op de hardwarebeschrijving van de gpu. Na analyse op datahergebruik kan de compiler adviseren om het scratchpad-gebruiken te gebruiken. Wanneer de programmeur hiermee rekening houdt, springt de performance naar 215 Gflops.

De programmeur kan nu besluiten om nog verder af te zakken naar het abstractieniveau van Nvidia. De compiler heeft hier kennis over deze specifieke architectuur en meldt dat het parallellisme gelimiteerd is door de hoeveelheid scratchpad-geheugen. Daaruit volgt het advies om het gebruik hiervan te beperken. Op dit abstractieniveau wordt de trade-off tussen het geheugengebruik en parallellisme dus duidelijk. Door het programma nu zodanig aan te passen dat het rekening houdt met deze trade-off, klimt de performance naar 241 Gflops. Na alle feedback te hebben verwerkt, wordt een performance van 302 Gflops behaald.

Op deze wijze kunnen programmeurs besluiten hoe ver ze willen gaan met optimalisaties, leren ze belangrijke afwegingen te maken in hun programma’s om goed overweg te gaan met de beschikbare hardware en kunnen ze stapsgewijs tot op een laag niveau controle uitoefenen om performance te halen. We hebben de methode uitgeprobeerd op een programmeur met weinig gpu-ervaring. Deze wist veel algoritmes bijna optimaal over te zetten naar gpu’s, vaak slechts in enkele dagen. In de praktijk blijkt dat voor veel toepassingen uiteindelijk vergelijkbare prestaties worden gehaald als voor met de hand geoptimaliseerde code, hoewel in sommige gevallen de compileranalyse nog iets tekortschiet.

In het NFI-project wordt onze methode momenteel ook toegepast op het automatisch herkennen van de specifieke camera(sensor) waarmee een foto is genomen, omdat daarmee verbanden kunnen worden opgespoord. De ruis van een beeldsensor dient hier als een vingerafdruk, en om die ruis te extraheren, moet precies het omgekeerde worden toegepast van convolutiefiltering. We verwachten dat onze methode de programmeurs helpt om deze toepassing, en vele andere, efficiënt te implementeren.

Edited by Pieter Edelman