Klaas van Gend is field application engineer voor Vector Fabrics. De 25 mensen sterke Eindhovense start-up heeft Pareon gemaakt om bestaande C- of C++-software te analyseren en te parallelliseren. In zijn vrije tijd schrijft Van Gend artikelen voor tijdschriften en werkt hij aan enkele opensourceprojecten. 

10 November 2012

Multicore kent vele vormen: homogeen, heterogeen, AMP, SMP, cachecoherent of niet, en ga zo maar door. Het raakt aan zowel oude informaticaprincipes als nieuwe innovaties. Klaas van Gend wijst de weg in multicoreland en legt uit waar de pijn zit voor de programmeur.

Met hedendaagse processoren is multicore bijna een vaststaand gegeven geworden. Er zijn nu zelfs al kleine microcontrollers met een dubbele Cortex-M3 te krijgen. Velen zien multicore als middel om nog prestaties uit een processor te persen nu de klokfrequentie nauwelijks meer toeneemt. Helaas schaalt bestaande software niet lekker mee.

Software is meestal geschreven voor single-threaded uitvoer. Zulke toepassingen draaien op een systeem met twee cores lukt nog wel: de oude applicatie werkt op de eerste kern en alle andere taken verhuizen naar de tweede. Die wordt weliswaar niet optimaal gebruikt, maar voor de applicatie is er nog wel winst. Maar om meer snelheid te behalen, of voor meer dan twee cores, zal de software moeten worden aangepast zodat er delen parallel gaan draaien. Helaas geldt dat programmeurs kennis zullen moeten hebben van de onderliggende hardware voor correcte parallellisatie.

De multicorewereld kan worden opgedeeld in twee typen processoren: de homogene processoren hebben meerdere exemplaren van dezelfde core aan boord, terwijl de heterogene processoren verschillende typen rekenkernen hebben. Bij de meeste gangbare homogene processorarchitecturen wordt al het geheugen tussen de verschillende cores gedeeld. Dan ontstaat meteen het volgende probleem: hoe worden schrijfacties naar het geheugen gesynchroniseerd zodat een core niet een half-geüpdatete versie leest uit zijn lokale cache? Bij sommige architecturen zoals TI‘s Keystone (8-core DSP) en de meeste GPU‘s wordt er niets gesynchroniseerd; het is daar de taak van de programmeur om ervoor te zorgen dat er niets mis kan gaan. Voor de bekendste architecturen (Intels en AMD‘s pc- en serverprocessoren, Freescales QorIQ, de Arm Cortex-A9-Socs) is er een cache-infrastructuur voor synchronisatie aanwezig. Deze cachecoherentie zorgt ervoor dat een schrijfactie naar het geheugen meteen bekend wordt bij geïnteresseerde andere caches/cores.

NVidia Tesla 1
Eens waren ze puur bedoeld voor grafische bewerkingen, maar tegenwoordig brengt NVidia al GPU-kaarten uit speciaal voor het zware rekenwerk.

Sommige architecturen zijn van nature geheel symmetrisch (symmetrische multiprocessoren ofwel SMP): alle cores werken altijd samen. Bij andere architecturen zoals Freescales QorIQ en Caviums Octeon kunnen kernen bij het opstarten afzijdig worden gehouden zodat ze zelfstandig eigen besturingssystemen kunnen draaien, het zogenaamde bare metal. Deze aanpak wordt wel AMP genoemd, omdat de cores ’asymmetrisch‘ worden gebruikt.

Ook asymmetrisch, maar dan op processorniveau, zijn de heterogene architecturen. Bekende voorbeelden zijn de oude tv-chips van NXP (Mips plus Trimedia), TI‘s Omap (Arm plus DSP), maar ook een gewone laptop met GPU heeft gedeeld geheugen en kan gezien worden als een heterogeen systeem. Vaak is er geen cachecoherentie tussen heterogene componenten. Bij bijvoorbeeld de Tegra3 van NVidia is er wel cachesynchronisatie tussen de Arm-cores onderling maar niet tussen de Arm-cores en de grafische processor.

Creativiteit

Wat betreft parallellisatie zijn er verschillende vormen, die bij de verschillende architecturen anders tot hun recht komen. Bij taakparallellisatie nemen verschillende cores afwijkende taken op zich. Bij dataparallellisme voeren meerdere cores dezelfde taak uit, maar op verschillende data. Hier zijn met name GPU‘s sterk in. Een iets andere vorm van dataparallellisme werd al in de jaren zestig opgeschreven: het idee om met één instructie tegelijkertijd meerdere datavelden te bewerken. Dit is de basisgedachte achter Intels MMX en SSE, PowerPC‘s Altivec en Arms Neon. Compilerspecialisten dachten ooit dat compilers de geschikte loops zelf zouden herkennen en zouden vectoriseren. Helaas is er van die hoop weinig terechtgekomen. Dit komt deels doordat het moeilijk is gebleken om via statische analyse het gedrag van code te voorspellen. Voor triviale loops is dat nog wel mogelijk, maar zodra het wat moeilijker wordt, is er nog steeds niets dat de menselijke creativiteit verbetert.

Vector Fabrics Pareon links
Vector Fabrics Pareon rechts
Met de Pareon-tool zijn de codeafhankelijkheden inzichtelijk te maken, in dit geval (boven) tussen de loop die bovenin donkerblauw wordt weergegeven (Loop_8) en de rest van de code. Pareon kan ook een andere loop parallelliseren (onder). Aan het einde van de code is een afhankelijkheid tussen iteraties gevonden. Hier is dus synchronisatie nodig. Vandaar dat de iteraties niet netjes recht onder elkaar staan.

Er is nog een ander probleem met vectorisatie: het is platformafhankelijk. Eigenlijk zijn het allemaal assembly-instructies, en die hangen nou eenmaal aan een processorarchitectuur. In sommige gevallen (SSE2, Neon) bestaat er ook een C-achtige functieaanroep die hetzelfde doet. Deze intrinsics worden rechtstreeks door de compiler in de assembly-opcode vertaald. Hoewel met vectorisatie op interessante loops snel veel kan worden gewonnen – een lokale viervoudige verbetering is redelijk normaal – is het nadeel dus dat je jezelf ophangt aan een processor.

Pseudo-random

Zowel bij vectorisatie als bij parallellisatie heeft de programmeur een probleem: hij moet de geschikte code hiervoor wel eerst vinden in de applicatie. Er wordt ook code toegevoegd, bijvoorbeeld overhead voor semaforen en het starten of wakker maken van threads. Dat stelt nog zwaardere eisen aan de daadwerkelijke winst. Profilen is een must – het magische oog van de programmeur schiet vaker naast dan raak.

Anders dan vectorisatie heeft parallellisatie een extra probleem, dat nog groter is dan het lokaliseren van de geschikte code: schijnbaar ongerelateerde softwaredelen kunnen invloed hebben. Stel dat een loop de functie rand() toepast – een standaard pseudo-randomgenerator. Deze functie wordt veel gebruikt en testscripts vertrouwen er vaak op dat rand() altijd dezelfde reeks ’willekeurige‘ waardes oplevert. Als delen uit de loop met rand() ineens parallel worden uitgevoerd, kan de volgorde van functieaanroepen veranderen en daarmee de uitkomst – en gaan de testscripts ineens fouten vertonen. Natuurlijk is dit een vrij onschuldig voorbeeld, maar het maakt duidelijk dat een programmeur eerst van alle code moet bewijzen dat er geen aanroepen naar functies met een interne toestand zijn voordat hij kan parallelliseren.

Om deze volgorde correct te houden, kan locking worden ingezet, doorgaans via semaforen. Deze Api‘s, die in de meeste besturingssytemen zijn ingebouwd, kunnen ervoor zorgen dat een stukje code maar door één thread tegelijkertijd kan worden uitgevoerd of dat een gegevensveld maar door één thread tegelijkertijd kan worden beschreven. Het nadeel van semaforen is dat ze tijd kosten, en als een semafoor daadwerkelijk gelockt is en dus de executie van de tweede thread onderbreekt, gaat de efficiëntie (en dus de snelheidswinst) van het parallelle algoritme weer omlaag.

Om code te kunnen onderzoeken op parallellisatiemogelijkheden moet dus eerst worden geprofiled en vervolgens moet de onderliggende code worden geanalyseerd voor de afhankelijkheden tussen de hotspots en gegevenstoestand in andere delen van de code. Bekende tools als Oprofile of Intels VTune kunnen het eerste deel van deze analyse uitvoeren, maar daarna blijft een nauwgezette analyse van de flessenhalzen en de ervaring en inventiviteit van de programmeur belangrijk. Daarom moet performanceoptimalisatie meestal worden overgelaten aan zeer ervaren programmeurs.

Met Vector Fabrics proberen we deze afhankelijkheid te doorbreken. Onze Pareon-tool speurt de afhankelijkheden op door elke geheugentoegang te observeren tijdens het draaien van de software. Door geheugentoegang te koppelen aan de locatie in de code kunnen patronen van toegang worden herkend en de afhankelijkheden worden gecategoriseerd. Deze informatie geeft de programmeur inzicht in mogelijke toekomstige racecondities en het performanceverlies dat ontstaat omdat locking de code stiekem toch weer serieel maakt. Met de verworven kennis kan Pareon ook een voorstel doen over hoe de code met zo weinig mogelijk locking te parallelliseren én een schatting afgeven over de te verwachten snelheidswinst.

Overhead

Het implementeren van multicore is in een homogene SMP-situatie nog redelijk simpel: maak een tweede executiethread in je programma en laat deze het rekenwerk uitvoeren. Het besturingssysteem zorgt er wel voor dat het dan parallel gebeurt. Op heterogene systemen kan dit niet zomaar. Code gecompileerd op een Intel-processor werkt niet op een AMD-GPU. Natuurlijk is dit op te lossen door als programmeur specifieke delen opnieuw te compileren en wat glue code te schrijven, maar dat levert al snel een behoorlijke hoeveelheid werk op en is helaas specifiek voor dat platform.

Computerbedrijf Apple zag dit in 2007 ook al in en begon aan een project dat naar buiten kwam als OpenCL. Er werd een standaardisatiegroep voor opgericht onder auspiciën van de Khronos-groep, ook bekend van onder meer OpenGL. Met OpenCL is het makkelijker om C-achtige code te laten draaien op andere processoren in het systeem. Dit kunnen andere kernen van dezelfde processor zijn, maar ook GPU‘s, DSP‘s of FPGA‘s. OpenCL-code wordt vlak voor het moment van uitvoeren gekruiscompileerd voor het platform waarop hij gaat draaien – de compiler wordt dus meegeleverd met het apparaat. Daarna wordt de binaire code met de data naar het betreffende device gestuurd om zijn taken uit te voeren. Hier zit dus ook overhead in.

Helaas worden er nog wel eisen gesteld aan de C-code die voor een dergelijke versneller is toegestaan: er mag geen recursie in zitten, functiepointers zijn niet toegestaan en alle data moeten van tevoren begrensd zijn. Verder zijn de meeste standaard C-headerfiles taboe. Gelukkig definieert OpenCL zelf een heleboel mathematische en logische functies.

Belangrijk is ook dat OpenCL-jobs niet te groot zijn. Met honderden kleinere jobs is het makkelijker om alle GPU-cores parallel aan het werk te houden. OpenCL heeft ook mogelijkheden voor vectorisatie. Arrays van twee, drie, vier, acht of zestien waardes zijn in één keer te bewerken: er iets bij optellen, met iets vermenigvuldigen of van allemaal tegelijkertijd de wortel berekenen. Deze manier van vectoriseren heeft niet het probleem van hardwareafhankelijkheid, maar voegt wel de OpenCL-overhead toe.

Hoewel OpenCL in het begin best veel publiciteit heeft ontvangen, lijkt de ontwikkeling niet al te vlotjes te gaan – daadwerkelijk echt gebruik lijkt nog minimaal. De inzet van OpenCL in Apple-tablets en -telefoons lijkt logisch, want daar zijn diverse heterogene componenten voorhanden, maar helaas wordt dat door Apple dan weer niet aangeboden.

Sinds juni 2012 is er de HSA Foundation, waarin AMD, Arm, Imagination, Mediatek en Texas Instruments proberen wat meer voortgang in de OpenCL-ontwikkeling te krijgen. Grote ontbrekende in dit lijstje is NVidia, dat samen met Apple wel de oorspronkelijke spec heeft opgeschreven en bij alle videokaarten OpenCL-drivers meelevert maar verder vooral lijkt in te zetten op Cuda – een vergelijkbaar maar wat volwassener strategie specifiek voor zijn eigen GPU‘s.

#pragma omp

Op symmetrische multiprocessoren zullen programmeurs dus nog wel even handmatig blijven parallelliseren via threads. Gewoonweg wat locking toevoegen aan code is zelden een goed idee. Het waarschijnlijk bekendste voorbeeld van slechte locking is de Linux-kernel: in de aloude 1.3-versie werd door Alan Cox code toegevoegd waarmee het OS ook op een SMP-systeem kon draaien. Vanaf ruwweg de 2.5-editie hebben programmeurs hard gewerkt om deze ’Big Kernel Lock‘ weer weg te poetsen. Zeven jaar later, met versie 2.6.37, was de BKL eindelijk vervangen door correcte, veel fijnmazigere locking, en waren veel algoritmes herschreven om helemaal geen locking meer nodig te hebben. Deze hele BKL removal heeft meerdere manjaren werk gekost.

De moeder van alle threading-bibliotheken voor C is PThreads. Deze Posix-library bevat abstracties van semaforen en threads, maar is in het dagelijks gebruik niet altijd even handig omdat de hoeveelheid code nogal toeneemt. Daarom zijn er diverse abstracties in omloop. Pareon gebruikt de VFTasks-bibliotheek, die we zelf hebben ontwikkeld maar onder een opensourcelicentie hebben vrijgegeven. Programmeurs die zelf gaan parallelliseren zullen echter sneller naar andere mechanismen grijpen.

Een bekende abstractie van PThreads is OpenMP, een set compilerextensies die met aanwijzingen voor de compiler (pragma‘s) aangeeft hoe code geparallelliseerd kan worden. Via deze #pragma omp-instructies kun je aangeven dat van de volgende loop iteraties parallel kunnen worden uitgevoerd, welke variabelen daarvoor per thread lokaal zijn en welke variabele na afloop het resultaat van bijvoorbeeld een optelling moet bevatten. OpenMP helpt dus om parallellisatie kort en netjes te formuleren. Diverse compilers ondersteunen het, waaronder Microsoft Visual C, de Intel-compiler, CLang/LLVM en GCC. OpenMP is erg elegant, maar geen officiële compilerextensie en daarom voor veel projecten niet toegestaan.

Sinds 2011 zijn er nieuwe Iso-standaarden voor zowel C als C++. Beide standaarden bevatten extensies voor multithreading en gebruiken interoperabele mogelijkheden. In C zijn er functies als thrd_create(), thrd_join() en mtx_unlock() bijgekomen. Voor C++ is er een std::thread-class, maar ook een heel mooie hoogniveau-implementatie std::future, die het parallelliseren van een functieaanroep echt versimpelt. Op dit moment is er helaas nog geen enkele compiler die alles uit de standaarden ondersteund, maar bijvoorbeeld atomics, mutexen en std::thread en std::future zijn al in GCC en CLang aanwezig.

Intels Threading Building Blocks (TBB) is een C++-templatebibliotheek met mogelijkheden als parallel_for() om de iteraties van een for()-loop te verspreiden over meerdere threads. Daarnaast heeft TBB implementaties van een aantal container-classes die geoptimaliseerd en beveiligd zijn voor parallelle uitvoering. Qua aanpak lijkt TBB deels op OpenMP, alhoewel het nieuwe calls toevoegt terwijl OpenMP alles met pragma‘s doet.

In de laatste revisies voor TBB wordt al gewag gemaakt van gebruik van C++11-primitieven. Het ligt voor de hand dat de bouwblokkendoos zichzelf zal vormen naar deze standaard. TBB wordt helemaal als broncode geleverd en is niet specifiek voor Intel-processoren, maar omdat de bibliotheek helemaal door de chipmaker wordt gespecificeerd is er van een volledig open oplossing geen sprake.

De wereld van multicore processoren en het programmeren daarvan is duidelijk in beweging, waardoor in ieder geval het programmeerwerk in de toekomst netter en overzichtelijker wordt. Het écht goed opzetten van een nieuwe, netjes parallelliseerbare architectuur is echter nog steeds werk voor goede softwarearchitecten. Het omvormen van bestaande code om beter gebruik te maken van multicoremogelijkheden vereist veel geduld en kennis omdat er een groot aantal problemen op de loer ligt. Met de goede tools is deze taak duidelijk lichter te maken.

Edited by Pieter Edelman