De bottleneck van parallel programmeren

In de chip-wereld is een ontwikkeling gaande die zonder aarzeling een revolutie genoemd mag worden. Nieuwe processoren die over exponentieel veel meer rekenkracht beschikken dan de huidige generatie. Een van de grootste uitdagingen met die nieuwe chips is het parallel programmeren. Als we dat niet goed doen, behalen we hooguit tien procent van de maximaal haalbare performance en schieten we er nog niets mee op.

We spreken met prof. dr. ir. Henri E. Bal, hoogleraar aan de Amsterdamse VU. Onder de vlag van COMMIT/ werkt hij aan een project om de groeiende kloof tussen de steeds complexer wordende infrastructuren en hoe applicaties werken te verkleinen. “In dit kader werken we momenteel erg hard aan het vereenvoudigen van parallel programmeren.”

Multitasken

De Wet van Moore stelt dat het aantal transistoren op chips elke achttien maanden verdubbelt. “Dat computers iedere achttien maanden twee keer zo snel worden, kan een gevolg zijn van deze wet, maar dat is niet wat de wet zelf zegt”, aldus Bal. “Sinds een jaar of dertig willen de grote chipmakers, gesterkt door de Wet van Moore, computers sneller maken. Dit lukte hen lange tijd terwijl ze het programmeermodel sequentieel hielden. Daarbij voert een rekenunit zijn lijst van instructies één voor één achter elkaar uit. Voor iedere berekening moet echter eerst data uit het geheugen worden gehaald. In de tussentijd kan de CPU andere dingen doen. Eigenlijk is hij al aan het multitasken. Volgens Bal is dat multitasken geëscaleerd tijdens de afgelopen decennia waarin de chips zijn doorontwikkeld. “Deze chips doen mega-ingewikkelde dingen zoals ‘prefetching’, ‘pipelining’, ‘branche prediction’, et cetera. Hierdoor is slechts een kwart van de ruimte op een chip gereserveerd voor de echte rekeneenheden. Een kwart is bestemd voor het multitasken. Omdat de chip snel rekent, moet hij bij veel geheugenposities kunnen. Voor een lokale kopie (cache) van dit geheugen wordt de rest van de ruimte op de chip, de helft, gebruikt.”

Henri Bal Foto Ernst van Deursen

Henri Bal Foto Ernst van Deursen

De toename van multitasking maakte hogere kloksnelheden, slimmere architecturen en dus ook snellere computers mogelijk. Tot we een jaar of tien geleden tegen de beruchte powerwall aanliepen. Bal: “Ze konden de kloksnelheid niet meer opschroeven, omdat de CPU dan te heet werd. Toen is men mondjesmaat afgestapt van het sequentiële programmeermodel en werden de multicores bedacht. Daarmee werden chips dus expliciet parallel. Alleen moest je de cores parallel programmeren als je de beschikbare rekenkracht efficiënt wilde gebruiken.”

En daar zit nu precies de bottleneck. Het parallel programmeren staat nog in de kinderschoenen en is bijzonder moeilijk. Daarop komen we verderop in dit artikel terug.

Naast de CPU’s werden de zogeheten GPU’s (Graphical Processing Unit) verder ontwikkeld. Deze werden gebruikt in de gaming wereld voor grafische kaarten, die continue miljoenen pixels moeten berekenen. “Een GPU bestaat – afhankelijk van het model – uit meerdere zogeheten streaming multiprocessors”, licht Bal toe. “Iedere multiprocessor bestaat uit honderden cores, waardoor er op één chip wel 2000 of nog meer cores kunnen. Ze zijn dus gemaakt om alles parallel te doen: high throughput. Er is één nadeel: één enkele taak voeren ze heel langzaam uit, omdat de geheugenposities en de ruimte om te multitasken hiervoor nagenoeg ontbreken.”

Er komen nu allerlei nieuwe architecturen beschikbaar. In 2012 bracht Intel de Xeon Phi uit, die teruggaat naar het punt waarop besloten werd het programmeermodel sequentieel te houden. “Praktisch alle transistoren op deze chips worden gebruikt voor rekentaken”, legt Bal uit, “en dat is natuurlijk wat je wilt. Alleen is elk van deze rekenkernen veel trager dan de laatste generaties sequentiële CPU’s, omdat caching en multitasking nu tot een minimum zijn gereduceerd. Maar het goede nieuws is dat je ontstellend veel cores tegelijkertijd diverse taken kunt laten uitvoeren. De Phi van Intel heeft weliswaar zestig cores op één chip, maar die hebben min of meer de Pentium-architectuur van tien jaar geleden, al is de kloksnelheid wel beter. Dus eigenlijk draaien we de beslissing om het programmeermodel sequentieel te houden en de chips zelf te laten multitasken, weer terug.”

Moeilijkheden

Een van de grootste uitdagingen met die nieuwe chips is het parallel programmeren. Bal luidt de noodklok. “Als mensen hiervoor niet goed worden opgeleid, wordt het ontstellend moeilijk om de efficiëntie die deze parallelle rekenunits beloven, er ook daadwerkelijk uit te halen. Zolang je die indrukwekkende rekencapaciteit niet effectief aanstuurt, gebruik je maar een percentage van de beschikbare rekenkracht. Onze ervaring is dat als je applicaties gewoon naïef implementeert op zo’n Intel Phi of GPU, je hooguit tien procent van de maximaal haalbare performance behaalt. Soms kom je niet eens verder dan één procent.”

Bij parallel programmeren heb je te maken met een aantal moeilijkheden. Zo moet je bedenken hoe je al die taken gaat opsplitsen. Bal: “In mijn colleges gebruik ik altijd het voorbeeld van de krantenbezorgers en de huizenbouwers. Wil je 10.000 kranten bezorgen, dan verdeel je die simpelweg over een aantal bezorgers. Het bouwen van een huis vergt veel meer coördinatie. De stukadoor, elektricien en de schilder moeten elkaar niet in de weg zitten en de diverse bouwers moeten hun werk in de juiste volgorde doen en informatie met elkaar delen. Daarnaast moet je zorgen dat het efficiënt gaat. Hiertoe moet je de zogeheten load balancing goed regelen, zodat de ene bezorger niet alleen maar in flats bezorgt en de andere een wijk heeft met allemaal verspreide huizen. Alle rekenunits moeten dus evenveel werk hebben.”

Systematisch programmeren

Een andere hobbel bij het parallel programmeren is de correctheid. Bal typeert deze moeilijkheid als ‘een echte beerput’. “Sequentiële computers zijn min of meer deterministisch: als je ze duizend keer iets laat doen met dezelfde input, krijg je duizend keer hetzelfde resultaat. Dit ben je bij parallelle systemen helemaal kwijt. Stel dat we twee computers hebben met één geheugenlocatie. Voor een aanpassing op een bankrekening wil de ene computer een bedrag optellen, terwijl de ander het bedrag wil verdubbelen. Het hangt dan van de timing van je programma af welke van de twee machines als eerste gaat. Dus je moet het zo programmeren dat je geen last hebt van deze ‘race condities’. Je wilt het parallel, maar tegelijkertijd wil je dat het deterministisch blijft. Voor dit probleem proberen we dingen te abstraheren en met kleine algoritmes te werken.”

Bal pleit ervoor om te werken aan een betere manier om die many cores op een systematische wijze te programmeren. “Vooralsnog is er niet één vorm van parallel programmeren. Voor clusters of supercomputers wordt de standaard MPI gebruikt, maar voor GPU’s zijn er nu nog verschillende standaarden. Het wordt wel hoog tijd dat daaruit één standaard komt, want de groei van de many cores gaat heel snel.”

Toepassingen

Deze parallelle vorm van rekenen wordt al in honderden toepassingen gebruikt. “Daarmee worden ook al behoorlijke successen behaald”, weet Bal. “Het zijn er teveel om allemaal te noemen, maar zelf werken wij bijvoorbeeld samen met de astronomen van Astron, een laboratorium in Dwingeloo. Hun LOFAR-telescoop genereert massa’s aan data die allemaal geanalyseerd moeten worden. Daarnaast is er de zogeheten Square Kilometer Array (SKA) die vanaf 2018 in Australië en Zuid-Afrika wordt gebouwd. Deze Array bestaat uit één vierkante kilometer aan kleine antennes die signalen uit de ruimte oppikken. Speciale software combineert al die data tot één grote telescoop die onvoorstelbaar ver kan kijken. De hoeveelheid data die SKA gaat genereren zal volgens een inschatting10 tot 100 keer de huidige wereldwijde internettraffic gaan overschrijden. Dat is zo enorm veel, dat je echt parallelle rekenkracht nodig hebt om het te analyseren.”

Een ander praktijkvoorbeeld is een samenwerking met het NFI (Nederlands Forensisch Instituut). “Bij een inval neemt de politie alle media die ze kunnen gebruiken voor het onderzoek in beslag: pc’s, telefoons, usb-sticks”, vertelt Bal. “Vanwege de hoeveelheid data en de vele tools om al die data te analyseren, kan dat weken rekentijd kosten. Wij werken mee aan methodes die hen helpen om uit die berg data binnen 24 uur datgene te filteren waarnaar ze op zoek zijn. Ook werken we mee aan de versnelling van een algoritme voor camera-identificatie. De ruis die de camerasoftware wegfiltert, gebruiken zij juist als een soort vingerafdruk van de camera. Dus aan de ruis in de plaatjes kunnen ze zien met welk toestel de foto is gemaakt, zodat je relaties kunt aanbrengen tussen camera’s van verdachten. Persoon x heeft een illegaal plaatje wat is gemaakt door de camera van persoon y.”

Opleiding

Aan de VU worden al wel diverse colleges gegeven waar zaken als racecondities, het analyseren van algoritmes en het behalen van performance worden gedoceerd. “Ook hebben we aan de VU een Top Master, Parallel and Distributed Computer Systems. Dat is een mix van internettechnologie en parallel programmeren. Een opleiding parallel programmeren bestaat nog niet, maar die moet er wel degelijk komen. Misschien moet je er niet direct bij eerstejaars mee beginnen, want dat is gewoon te moeilijk, maar moet je het mondjesmaat laten meelopen in bestaande vakken over datastructuur en algoritmen.”

Wat is COMMIT/?

COMMIT/ brengt wetenschappelijk onderzoek en (non-)profitorganisaties samen in ict-projecten binnen de negen belangrijkste economische sectoren van Nederland voor het onderzoeken en ontwikkelen van grensverleggende producten en diensten. Binnen COMMIT/ werken meer dan 110 partijen, waaronder universiteiten, technologische instituten en meer dan tachtig grote en kleine bedrijven, samen aan publiek-private projecten die op internationaal niveau een belangrijke rol spelen.

De officiële naam van het project waarvan Henri Bal projectleider is, luidt: IV-e (e-Infrastructure Virtualization for e-Science Applications). De direct bij dit project betrokken partners zijn naast de VU, UvA, TU Delft, CGI, TNO, Bitbrains Nederland BV, KLM en het LIACS (het informatica-instituut van de Universiteit Leiden).

 

Gerelateerde berichten...