Cell-processor leert naar plaatjes kijken

Bij het overzetten van een sequentieel programma naar een heterogene multicorearchitectuur zijn de gevolgen voor de uitvoersnelheid van tevoren niet altijd te overzien. De Cell-processor biedt in totaal vijf lagen van parallellisme waar de programmeur rekening mee moet houden. Een verkeerde inzet hiervan betekent een verspilling van rekenkracht. Een applicatie kan zelfs langzamer draaien dan de originele code. Ana Lucia Varbanescu van de TU Delft zette voor IBM de Marvel-applicatie over, een toepassing om foto‘s te classificeren. Zij experimenteerde met de optimale inzet van de rekenkernen. Meer is niet altijd beter.

Bij de Cell-processor zullen de meeste mensen aan de Playstation 3 denken, de spelconsole waarmee Sony de harten en portemonnees van gamers probeert te veroveren. De Cell is echter interessant voor veel meer toepassingsgebieden. De processor werd gezamenlijk ontwikkeld door IBM, Sony en Toshiba. Sony had een duidelijke toepassing voor ogen om in het project te stappen. Voor de andere twee partners lag dat wat anders. Toshiba dacht het silicium te kunnen gebruiken voor zijn televisies. IBM had dezelfde opvattingen over zijn High Performance Computing-toepassingen, programmatuur die grote hoeveelheden rekenkracht vereist. Op dit moment evalueert Big Blue de Cell door zijn HPC-applicaties zo veel mogelijk over te zetten naar deze processor.

Bij de introductie van de PS3 roemde halfgeleidermarktonderzoeker Isuppli de Cell-processor door deze te omschrijven als ’supercomputer op een chip‘. De Cell heeft dan ook flink wat in huis: naast een min of meer standaard PowerPC-kern voor huishoudelijke taken beschikt de chip over acht vectoreenheden, die elk 128 bits aan data tegelijk kunnen verwerken in twee onafhankelijke pijplijnen. Deze Synergistic Processor Elements (SPE‘s) hebben geen cachegeheugen, omdat dat lastig te synchroniseren is over de in totaal negen rekenkernen. In plaats daarvan hebben ze elk 256 kilobyte aan Local Store-opslag (LS). Om het gebrek aan snelle toegang tot cachegeheugen gedeeltelijk te compenseren, gebruiken de SPE‘s asynchrone DMA-aanroepen om data tussen het werkgeheugen en de LS heen en weer te pompen. De processor kan dus al een ophaalcommando geven terwijl de voorgaande transactie nog bezig is. Per transactie kan er zestien kilobyte worden overgedragen.

In totaal krijgt de Cell daarmee vijf niveaus van parallellisme. Het hoogste niveau is dat van Multiple Program Multiple Data (MPMD), ofwel parallellisme op taakniveau. Hierbij houdt elke rekenkern zich bezig met verschillende aspecten van een computerprogramma. Een stapje lager komt Single Program Multiple Data (SPMD), ofwel parallellisme op dataniveau. Daarbij voert elke rekenkern dezelfde taak uit op een ander stuk van de data. Dan is er het zojuist beschreven parallellisme in de datastromen waar de programmeur rekening mee dient te houden. Op de laagste twee niveaus staan vector- en pijplijnparallellisme. De SPE‘s verwerken gelijktijdig vectoren van 128 bits. Dat kan variëren van twee double-precision floats tot zestien words die tegelijk worden verwerkt in een van de twee pijplijnen. Deze zijn allebei geoptimaliseerd voor andere bewerkingen, maar als de meest efficiënte pijplijn al vol zit, kan de instructie beter naar de andere worden gestuurd. Deze vijf lagen van parallellisme maken het er voor de programmeur niet makkelijker op om de software op de juiste manier op te delen.

Wolkenlucht

Als casestudy werkte TU Delft-promovenda Ana Lucia Varbanescu samen met haar collega‘s IBM‘s Marvel-software uit op de Cell. Marvel is een Windows-toepassing die foto‘s classificeert door ze te vergelijken met een verzameling referentieafbeeldingen. Het programma doet dit door een score op te stellen voor een aantal aspecten van het beeld en hieruit een algemene betrouwbaarheidsscore te destilleren. Deze kan dan worden vergeleken met scores in een referentiedatabase.

Marvel kijkt naar het histogram, het correlogram, de textuur en de objectranden in een afbeelding. Het histogram is de verdeling van de kleuren in een beeld. Een bos zal bijvoorbeeld 90 procent groen zijn en een foto van de lucht grotendeels blauw. Het correlogram kijkt naar de ruimtelijke verdeling van deze kleuren. Het histogram voor een foto van een wit laken tegen een blauwe hemel zal bijvoorbeeld sterk overeenkomen met een afbeelding van een lucht met wolken, maar de ruimtelijke verdeling is heel anders. De textuur neemt de structuur in beschouwing. Dit is een indicatie voor het materiaal van de objecten. De randen ten slotte vertellen iets over het aantal en de grootte van de objecten in de afbeelding. Deze vier processen leveren voor elke afbeelding een reeks getallen van 12 tot 256 bits. Deze worden uiteindelijk verwerkt tot een enkele score.

De referentieafbeeldingen hebben een reeks scores voor elke klasse die het programma onderscheidt. Marvel vergelijkt de score van de afbeeldingen met elke score van de referentieplaatjes en velt aan de hand daarvan zijn oordeel. Een grotere referentiedatabase levert daarom aan de ene kant betere resultaten op. Aan de andere kant groeit de uitvoeringstijd ook sterk. Dat maakt van Marvel een mooi demonstratieproject voor de Cell-processor.

Dankzij de PowerPC-kern is het overzetten van een applicatie naar Cell redelijk rechttoe rechtaan. In eerste instantie zet een programmeur de code over naar dit Power Processing Element (PPE). Bij standaard C/C++-code zal dit weinig inspanning vergen. Vanaf dat moment beschikt de ontwikkelaar over een draaiend programma op de Cell, dat echter vaak langzamer zal lopen dan de originele toepassing. Het PPE is niet zo krachtig uitgevoerd en geoptimaliseerd voor stroomverbruik. In het geval van Marvel nam het poorten naar het Cell-PPE een tot twee dagen in beslag. Dat had voornamelijk te maken met de huishouding rondom de C++-code, zoals makefiles. Marvel is een zeer grote applicatie, geschreven in Visual C++. Het doelsysteem draait op Linux en gebruikt IBM‘s aangepaste versie van de GCC-compiler voor Cell.Als de applicatie op het PPE draait is de volgende stap om de rekenintensieve delen van het programma onder te brengen op de SPE‘s. Deze zijn te identificeren met een standaard profiler, die rapporteert hoeveel tijd elke functieaanroep in beslag neemt. Als de relevante gedeeltes zijn gevonden, kan de programmeur hier zijn kernels op baseren voor de SPE‘s.

Als de applicatie op het PPE draait is de volgende stap om de rekenintensieve delen van het programma onder te brengen op de SPE‘s. Deze zijn te identificeren met een standaard profiler, die rapporteert hoeveel tijd elke functieaanroep in beslag neemt. Als de relevante gedeeltes zijn gevonden, kan de programmeur hier zijn kernels op baseren voor de SPE‘s.

Het is natuurlijk het beste om de originele code zo veel mogelijk in stand te houden. Dat kan door de functies die op de SPE‘s moeten draaien te vervangen door C++-stubs, lege functies die alleen een commando bevatten om de kernels op de SPE‘s aan te roepen. In het geval van Marcell, de aangepaste Marvel-versie, gebruikte Varbanescu compiler directives om naar wens sequentiële of Cell-code te genereren. Op die manier kon ze de prestaties van deze twee uitvoermanieren met elkaar vergelijken.

Als laatste stap moet een ontwikkelaar de SPE-software optimaliseren. Vaak werkt de code uit het originele programma minder efficiënt op de SPE‘s dan op de oorspronkelijke processor. Bij het optimaliseren van de SPE-code kan de programmeur zichzelf uitleven in het tweaken van het parallellisme op het laagste niveau. Bij IBM werkt een handvol programmeurs die hier zeer bedreven in zijn. Het is ook erg verleidelijk om hier tot in den treure mee door te gaan en steeds meer prestaties uit de software te wringen. Uiteindelijk moet de efficiëntie op dit niveau echter komen van de compiler en de geoptimaliseerde bibliotheken. Het is eenvoudigweg te duur om dit handmatig te blijven doen. Bovendien ontbreekt er een juiste weg; het probleem kan op vele manieren worden aangepakt. Dat maakt het erg lastig om de beste te kiezen.

Deze iteratieve manier van poorten heeft het grote voordeel dat de ontwikkelaar altijd een werkend programma heeft en stapsgewijs kan optimaliseren. Daaruit blijkt dus direct wat wel en niet werkt.

Helaas staan de objectgeoriënteerde ontwerpprincipes haaks op de benodigdheden om een programma goed op te delen over meerdere processoren. Bij het identificeren van de rekenintensieve onderdelen krijgt de programmeur informatie over functieaanroepen. Functies zitten bij objectgeoriënteerde code echter doorgaans netjes in klassen verpakt. Die functieaanroepen moeten dus handmatig door de klassenhiërarchie worden gevolgd om de relevante delen te identificeren. Dit was ook het geval bij Marvel, dat zich zeer strikt aan de objectgeoriënteerde principes van C++ houdt. Verder mixt een objectgeoriënteerde aanpak data en functies binnen afzonderlijke blokken en schermt deze af van buiten. Voor een multiprocessoraanpak moet de data juist voortdurend naar de andere rekenkernen worden gestuurd.

Varbanescu kon voor Marvel vijf voor de hand liggende rekenintensieve stappen identificeren. De eerste vier zijn het opstellen van de scores voor respectievelijk het histogram, het correlogram, de textuur en de randen. De laatste rekenintensieve stap is het vergelijken van de betrouwbaarheidscore met de referentiebeelden.

Na het schrijven en optimaliseren laten deze vijf kernels indrukwekkende resultaten zien. Randdetectie gaat bijvoorbeeld meer dan negentig keer zo snel als op het PPE. De PowerPC-kern van Cell is echter geen goede referentie, omdat die niet voor rekenkracht is gebouwd. Vergeleken met een standaard desktopprocessor bedraagt de versnelling nog geen twintig keer. Nog steeds een indrukwekkend getal, maar de originele code was niet geoptimaliseerd voor de specifieke processor. Een harde uitspraak over de uitvoersnelheid van de Cell-processor geven deze cijfers dus niet.

Ook is de versnelling afhankelijk van het aandeel van de kernel in het totale proces. Dit staat bekend als de wet van Amdhal. De randdetectie is goed voor 28 procent van de rekentijd in de originele Marvel-toepassing. Een versnelling van twintig keer voor dit onderdeel betekent dus geen versnelling van twintig keer voor de applicatie als geheel. In totaal was het delegeren naar de SPE‘s op de Playstation 3 goed voor een acceleratie van tien keer ten opzichte van een desktopprocessor (Figuur 1a).

Desktopprocessor

Varbanescu ging vervolgens op zoek naar de beste inzet van de beschikbare hardware. Op de Playstation 3 is een van de acht SPE‘s bestemd voor Sony en een andere is ook gereserveerd, alhoewel niemand precies weet waarvoor. De zes overige SPE‘s zijn beschikbaar voor programmeurs. IBM heeft ook een Cell-blade met twee Cell-processoren in een dual-coreconfiguratie. Aangezien de bussnelheid tussen de twee chips nagenoeg gelijk is aan de bussnelheid binnen elke Cell, kunnen ontwikkelaars deze blade inzetten als virtuele Cell-processor met zestien SPE‘s, waarbij ze slechts een van de twee PPE‘s inzetten. Big Blue heeft in Austin, Texas, een blade staan voor onderzoeksdoeleinden. Dankzij het tijdsverschil kon Varbanescu vanuit Delft naar hartenlust experimenteren terwijl de IBM-medewerkers op één oor lagen.

In eerste instantie testte ze eenvoudig taakparallellisme (MPMD). De eerste vier stappen draaien daarbij tegelijk, elk op een eigen SPE. Als deze allemaal klaar zijn, komt de vijfde stap in actie (Figuur 1b). Deze parallelle uitvoering versnelde de applicatie veertien keer ten opzichte van de desktopprocessor, slechts 1,4 keer zo veel als sequentiële uitvoer met de SPE‘s. Dat komt doordat het proces nog steeds gelimiteerd is door de langste stap. Een ander nadeel van deze benadering is dat de software slechts vier SPE‘s gebruikt.

De volgende stap was dus om te kijken naar dataparallellisme (SPMD). Alle SPE‘s voeren hier dezelfde taak uit op verschillende delen van de data. Marcell voert de vijf bewerkingen achtereenvolgens uit op alle SPE‘s (Figuur 1c). Zoals verwacht, versnelt dit de uitvoering van de kernels aanzienlijk, zij het niet altijd lineair. De precieze versnelling is onder meer afhankelijk van het databeheer. Zo gaat het opstellen van het histogram een stuk sneller met vijf dan met zes SPE‘s. De randdetectie schaalt meer dan lineair met het aantal SPE‘s. De kernel heeft hier met zes kernen elf keer minder tijd voor nodig dan met een enkele SPE. Ook dat is te wijten aan geheugeneffecten: met meerdere kernen kan de software grotere datablokken per keer opvragen. Dat vermindert het aantal geheugenaanroepen.

Een versnelling van de programmaonderdelen garandeert echter geen versnelling van de applicatie als geheel. In een pure SPMD-configuratie draait Marcell met zes SPE‘s even snel of zelfs langzamer dan met een enkele SPE. De oorzaak ligt in de 256 kilobyte aan Local Store-geheugen van de SPE‘s. Deze opslag moet niet alleen de data, maar ook de code herbergen. Daarom is er te weinig ruimte om de vijf kernels, die elk SPE achtereenvolgens draait, van tevoren in het geheugen te laden. Ook voor de code moeten de SPE‘s dus constant met het werkgeheugen communiceren en dat introduceert vertragingen. Als ervoor gekozen wordt om overlays te gebruiken, die afwisselend gedeeltes van het geheugen uitwisselen binnen dezelfde thread, blijft dit binnen de perken en is de executietijd min of meer gelijk voor elk aantal kernen. Wordt er echter gekozen voor het opstarten van een nieuwe thread voor elke berekening, dan gaan de prestaties dramatisch achteruit en groeit de uitvoertijd met het aantal gebruikte kernen. Het opstarten van threads is een zeer kostbare aangelegenheid.

Om toch alle kernen optimaal te gebruiken, richtte Varbanescu zich op een combinatie van data- en taakparallellisme. Elk SPE wordt hier slechts toegewezen aan een van de vier analysetaken, waarbij sommige van de taken op meerdere rekenkernen tegelijk draaien. De vijfde taak, het matchen met de referentiebeelden, gebeurt op vier SPE‘s tegelijk (Figuur 1d). De SPE‘s hoeven dus minder vaak van taak te wisselen. Binnen Marvel nemen het correlogram en de randdetectie respectievelijk 54 en 28 procent van de rekentijd in beslag. Het aandeel van de overige onderdelen komt niet boven de 8 procent. Deze twee bewerkingen liggen dus het meest voor de hand om over meerdere kernen uit te smeren. Aangezien het hier om een onderzoeksproject gaat, probeerde Varbanescu echter alle combinaties uit op de zes SPE‘s van een Playstation 3 en op de zestien SPE‘s van een Cell-blade.

Zoals te verwachten was, presteerde Marcell het beste als het correlogram op meerdere kernen draait (Figuur 2). Bij de PS3 maakt het nauwelijks uit of dit twee of drie kernen zijn. Ook bleek het opdelen van de randdetectie weinig invloed te hebben op de totale uitvoertijd. De beste verdeling was om drie kernen in te zetten voor het correlogram en één kern voor de andere bewerkingen. Bij de blade bleek Marcell optimaal te presteren met veertien kernen. Het correlogram en de randdetectie kregen hier elk vier kernen tot hun beschikking, en het histogram en de textuurdetectie drie. Het verschil met het gebruik van tien SPE‘s was echter dermate klein dat het de vraag is of de inzet van veertien kernen wel zinvol is. Uit energieoogpunt zou een ontwikkelaar ervoor kunnen kiezen om tien SPE‘s te gebruiken en de andere zes kernen uit te schakelen.

Het inzetten van extra rekenkernen heeft op voorhand niet altijd duidelijke consequenties. Factoren als geheugeneffecten en het wisselen van threads kunnen de applicatie juist vertragen in plaats van versnellen. Om hier wat zinnigs over te kunnen zeggen, zijn goede benchmarks nodig. Helaas ontbreken die op dit moment nog. Ook is er nog veel werk te verrichten aan de manieren om software in parallelle termen uit te drukken. Deze programmeermodellen zijn steeds harder nodig om multicorearchitecturen binnen de tijds- en budgetlimieten te kunnen ontwikkelen.

Op 18 oktober aanstaande geeft Ana Lucia Varbanescu tijdens Bits&Chips 2007 Embedded Systemen een presentatie over het poorten van Marvel naar de Cell-processor.