Bits&Chips

De impact van multicore op het ontwerp van embedded software

Auteur: David Kalinsky
8 februari 2008 

Voor het ontwikkelen van software voor multicoreprocessoren kunnen we in eerste instantie veel leren van traditionele ontwikkeling voor gedistribueerde systemen. Duiken we echter dieper de materie in, dan lopen we tegen een aantal belangrijke verschillen aan, zoals communicatiesnelheden tussen de processorkernen. David Kalinsky geeft een overzicht van de aanpak en wijst de zwakke punten aan.

Ik ben onderwijzer van beroep. Jarenlang gaf ik een cursus genaamd ’Architectural design of real-time software‘, gericht op het ontwerp van embedded software voor een enkele processor. Een aantal jaar geleden besloot ik om er een uur aan toe te voegen over ontwerpen voor multicore. Maar toen ik me in dit onderwerp ging verdiepen, ontdekte ik al gauw dat dit veel meer omvat dan het simpelweg aanpassen van een onderdeel voor enkelprocessorontwerpen. Sterker nog, het was nodig om grote delen van de bestaande cursus te vervangen met totaal ander materiaal dat zich richt op nieuwe aanpakken en valkuilen bij multicore. Uiteindelijk had ik geen andere keus dan opsplitsen in twee cursussen.

Wij embedded-software-engineers kunnen niet langer meer van chipontwerpers verwachten dat ze ons van meer en meer krachtig silicium blijven voorzien, waarmee de software van een jaar oud weer bijna twee keer zo snel draait. Chipontwerpers lopen tegen de fysieke limieten aan die de wetten van de thermodynamica stellen. Dat dwingt ze om de steeds snellere enkelprocessorontwerpen in te ruilen voor multiprocessoren op een chip, die vergelijkbare totale rekenkracht bieden met een lagere warmteontwikkeling. Voor de eerste keer in de geschiedenis van het embedded programmeren vragen chipontwerpers aan ons om onze ontwerpen radicaal aan te passen, zodat zij hun versnellingsdoelen halen.

Op het eerste gezicht lijkt het ontwerpen van software voor multicoresystemen vergelijkbaar met multitaskingsoftware. Maar applicatiesoftware voor multicoresystemen is vaak grootschaliger en veel complexer dan de programmacode die in het verleden is ontwikkeld voor traditionele enkelkernsystemen. Daarom hebben we aanvullende methodologie nodig die ons helpt op deze nieuwe schaal en dit nieuwe niveau van complexiteit. In een eerste benadering kunnen we de richtlijnen baseren op die voor het ontwerpen van gedistribueerde multiprocessorsystemen. Multicoresystemen zijn echter niet simpelweg geminiaturiseerde gedistribueerde systemen. Voordat we aan het ontwerp van software voor multicoresystemen kunnen beginnen, moeten we aandacht besteden aan de verschillen tussen gedistribueerde en multicoreontwerpen. Veel uitgangspunten die de fundamenten vormden van multitaskingsoftware de afgelopen 20 tot 30 jaar zijn niet langer geldig bij het ontwerpen voor multicore-Soc‘s.

Eenheid

Aan de basis van multicoreontwerpen ligt het opdelen in stukjes van de embedded software. Elk van deze onderdelen heeft een kleinere schaal en complexiteit dan het softwaresysteem in zijn geheel en is dus makkelijker om mee te werken. We kunnen enkele richtlijnen voor deze partitionering baseren op de concepten van methodoloog Hassan Gomaa. Sla zijn boek ’Software design methods for concurrent and real-time systems‘ er eens op na.

We kunnen de stukjes waarin we het grote en complexe systemen verdelen, beschouwen als subsystemen. Deze subsystemen zijn, indien nodig, weer onder te verdelen in kleinere brokken (subsubsystemen, et cetera). Deze hiërarchische decompositie van complexe systemen kan zo lang doorgaan als nodig is – totdat de architect iets kan zeggen in de trend van ’O, ik weet hoe ik de software voor dit deel waarschijnlijk in minder dan 1000 coderegels kan schrijven‘, of ’O, ik weet hoe ik dit onderdeel kan implementeren in waarschijnlijk minder dan tien gelijktijdige taken.‘

Ik beschouw de kleinste subsystemen in de hiërarchie als kneedbare containers, die elk een aantal aan elkaar gerelateerde applicatietaken bevatten en zo een hoofdtaak vervullen. Sommige besturingssystemen die we in de embedded wereld gebruiken, hebben zelfs zo‘n container-voor-taken-concept. Linux-processen zijn bijvoorbeeld te beschouwen als containers voor Posix-threads.

De subsystemen moeten zo zelfstandig mogelijk zijn, maar zullen natuurlijk nooit geheel onafhankelijk van elkaar zijn – want dan zouden het aparte projecten of producten zijn. Voor het opdelen van complexe systemen in delen die slechts minimaal van elkaar afhankelijk zijn, zijn enkele richtlijnen te hanteren. Het partitioneren moet gebaseerd zijn op het op te lossen probleem. Dit betreft dus de systeem- en softwarerequirements. Verder moet een subsysteem één hoofdtaak vervullen, niet een halve of twee. De onderdelen van een subsysteem moeten een grote cohesie hebben. En dataopslag moet nooit dienen als directe interface tussen subsystemen, het moet altijd ingekapseld worden in een subsysteem.

Wat zijn de typische hoofdtaken die een eigen subsysteem verdienen? Denk hierbij aan zaken als realtime besturing, realtime coördinatie, data-acquisitie, data-analyse, serverfunctionaliteit, gebruikersdiensten en systeemdiensten. Zie Figuur 1.

Wanneer een groot en complex subsysteem eenmaal is onderverdeeld en de subsystemen op hun beurt weer hiërarchisch zijn opgesplitst tot het benodigde aantal niveaus, is de volgende stap om de kleinste subsystemen (mijn ’containers‘) in gelijktijdige taken op te delen. Dit gebeurt grotendeels op dezelfde manier als bij traditionele enkelkernsontwerpen. Communicatie verloopt primair door het versturen van berichten.

Pas nadat al deze ontwerpstappen zijn afgerond, kan de architect gaan nadenken over het verdelen van de software over de processorkernen. Hierbij moet hij rekening houden met extra aspecten, zoals de nabijheid tot de databron, de autonomie of bijna-autonomie van de subsystemen, de prestaties, de interfaces naar de hardware, de gebruikersinterface en servers en grote dataopslag. Deze aspecten kunnen leiden tot een herontwerp van de subsysteemhiërarchie.

Over het algemeen zullen een of meer subsystemen in een enkele kern terechtkomen. De kleinste subsystemen moeten als eenheid aan een kern worden toegewezen. Met andere woorden, een dergelijk subsysteem mag je niet zo opsplitsen dat sommige onderdelen op de ene en sommige onderdelen op een andere kern draaien.


Figuur 1: Een complex systeem is op te delen in een aantal eenvoudigere deelsystemen, die elk precies een hoofdtaak vervullen.


Figuur 2: Een asymmetrisch multiprocessing-OS (AMP) gaat uit van verschillende instanties of zelfs verschillende systemen voor de aparte processorkernen. De services van elke kernel zijn georganiseerd rondom een prioriteitgebaseerde preëmptieve scheduler met daaromheen mechanismen voor communicatie en synchronisatie tussen de taken die op dezelfde processor draaien, het dynamisch toekennen van geheugen, timerdiensten en het beheren van device drivers. Voor een multicoreomgeving moet dit worden uitgebreid met mechanismen voor communicatie en synchronisatie tussen taken op verschillende kernen. Dit kan met hetzelfde model als voor communicatie binnen de kern.

In deze eerste benadering mogen de richtlijnen voor het ontwerpen van multicoresystemen en gedistribueerde systemen op elkaar lijken, maar als we meer de diepte in gaan wordt het duidelijk dat ze verre van identiek zijn. Deze systemen verschillen als dag en nacht in hun mogelijkheden voor interprocescommunicatie tussen de kernen. De bandbreedte van multicore-Soc‘s is één tot twee ordes groter, met enkele ordegroottes kleinere vertragingen en een betrouwbare onderliggende fysieke laag. Voor de beeldvorming zijn ze te beschouwen als kleine processoren verbonden via dikke leidingen. Gedistribueerde systemen moeten meer gezien worden als grote processoren verbonden via smalle leidinkjes. Binnen een multicore-Soc kunnen kernen dus grotere datastromen uitwisselen dan bij in een gedistribueerd systeem. En dat met minder overhead voor het garanderen van de betrouwbaarheid dan bijvoorbeeld bij TCP/IP.

Een ander verschil is dat multicore-Soc‘s een klein en vaststaand aantal kernen hebben in een stabiele topologie, terwijl dit bij gedistribueerde systemen constant kan veranderen. Het monitoren van softwarefunctionaliteit kan daardoor verschillend worden afgehandeld. In het algemeen is de supervisie veel eenvoudiger in een multicoresysteemchipomgeving.

Inkapselen

Een multicoresysteemchip kan homogeen of heterogeen zijn. De Omap-Soc‘s van TI bijvoorbeeld, populair in mobieltjes en PDA‘s, bevat zowel een generieke Arm-processor als een DSP voor signaalverwerking. Dit is een voorbeeld van een heterogene multicorechip, waarbij de verschillende kernen verschillende instructiesets en besturingssystemen draaien. De kernen krijgen totaal verschillende taken toegewezen, in wat bekend staat als asymmetrische multiprocessing (AMP).

Aan de andere kant hebben sommige multicore-Soc‘s meerdere identieke kernen, met een gezamenlijk geheugen. In dat geval is het mogelijk om een enkel besturingssysteem te draaien die de software-uitvoering op alle kernen beheert. Het besturingssysteem beschouwt al zijn kernen gelijkwaardig en kan taken naar andere kernen overhevelen om de prestaties te maximaliseren. Dit staat bekend als symmetrische multiprocessing (SMP).

Het is overigens mogelijk om asymmetrische multiprocessing te doen op een Soc met identieke kernen, een homogene systeemchip. Maar het is niet mogelijk om symmetrische multiprocessing op een heterogene systeemchip te doen.

Voor deze verschillende categorieën van multicorerekenen zijn er verschillende typen besturingssystemen. Een SMP-besturingssysteem kan load balancen of worden geïnstrueerd om specifieke taken aan een kern toe te wijzen, zogenaamde processor affinity. Aan de andere kant zijn de AMP-OS‘en gebouwd als aparte, mogelijk verschillende systemen voor de verschillende kernen. Ze lijken op de traditionele RTos‘en uit de enkelkernsprocessorwereld en zijn geschikt voor hard realtime en deadlinegeoriënteerde toepassingen (Figuur 2).

De RTos-kernelservices zijn georganiseerd rondom een prioriteitgebaseerde preëmptieve scheduler die het hart van het taakbeheer vormt. Boven het taakbeheer ligt een aantal mechanismen voor communicatie en synchronisatie tussen de taken die op dezelfde processor draaien, waaronder messenging, semaforen, mutexen en misschien zelfs vlaggen. Bijkomende hoofdcategorieën van RTos-kerneldiensten zijn het dynamisch toekennen van geheugen, timerdiensten en het beheren van device drivers.


Een spinlock kan een gedeelde hardwarebron beschermen in een multicoreomgeving. De twee Posix-threads in Linux-processen roepen elk pthread_spin_lock() aan om de spinlock te vergrendelen voordat ze de bron aanspreken. Als ze klaar zijn met de bron roepen ze pthread_spin_unlock() aan om de spinlock weer te ontgrendelen.

Maar deze RTos-kerneldiensten moeten worden uitgebreid in een multicoreomgeving: er moeten ook mechanismen komen voor betrouwbare communicatie met taken die op andere kernen draaien. Als multicoreprocessoren over gedeeld geheugen beschikken kan het RTos een deel hiervan gebruiken als communicatiekanaal – misschien met een vergrendelingsmechanisme om conflicten te voorkomen, of door het inkapselen in een abstracter mechanisme zoals message passing.

Het is mogelijk om precies hetzelfde message passing-model te gebruiken als voor intertaakcommunicatie op een enkele processor en deze uit te breiden voor taken op verschillende, wellicht heterogene, kernen. Een aantal RTos‘en is uitgebreid met deze functionaliteit.


Figuur 4. Een race condition kan zijn kop opsteken bij het gebruik van message passing tussen taken. Stel dat de thermometer aan de linkerkant een temperatuur van 72 meet in Fahrenheit. Als de managementtaak een boodschap stuurt om de meting in graden Celsius te veranderen, kan het gebeuren dat deze pas aankomt bij de displaytaak nadat die de meetupdate ontvangen heeft. Die heeft nog steeds de waarde 72. Deze update wordt dan weergeven als 72 graden Celsius. Dit is duidelijk een fout. De software zou hierna al snel de juiste temperatuur van rond de 22 graden Celsius weergeven. Met andere woorden, de blunder is een voorbijgaand probleempje.

Spinnen

SMP-besturingssystemen verschillen sterk van hard deadlinegeoriënteerde RTos‘en. Ze gebruiken een enkele instantie voor alle kernen. Sommige van hen bieden de coretransparante intertaakcommunicatie zoals bij AMP, zoals Posix‘ <mqueue.h> in de Linux-wereld. Een aantal SMP-besturingssystemen heeft bovendien een mechanisme voor wederzijdse uitsluiting dat wel wat op een semafoor of mutex lijkt, maar gespecialiseerd is in multiprocessing. Dit mechanisme is de spinlock. Zie bijvoorbeeld de threads-bibliotheek van Posix.

Spinlocks zijn de mechanismen van een besturingssysteem om de toegang te regelen tot serieel deelbare bronnen in een multiprocessing- of multicoreomgeving. Deze omvatten zaken als datatabellen, I/O-apparaten, of non-reentrant algoritmes, die moeten worden gedeeld over taken op verschillende kernen. Een spinlock kan een dergelijke bron vergrendelen. Alle taken moeten dan de instructie krijgen om permissie te vragen aan de spinlock voordat ze bron aanspreken. En natuurlijk moet de taak de spinlock weer ontgrendelen als deze klaar is met de gedeelde bron (zie Figuur 3).

Tot zover klinkt dat zo ongeveer als een klassieke semafoor. En inderdaad, spinlockgebruikers moeten uitkijken voor een aantal van dezelfde problemen: deadlocks, lock-outs, priority inversions, moeilijkheden met debuggen, et cetera. Maar in tegenstelling tot semaforen of mutexen kan een vergrendelde spinlock de aanroeper in een loop brengen die constant de status controleert, het spinnen. Spinlocks zijn namelijk opgetrokken rondom een test-and-set-bewerking in de hardware. Als de lock niet beschikbaar is, zal de aanroepende software blijven spinnen totdat dit wel het geval is. Deze software komt niet in een geblokkeerde of wachtende status terecht maar blijft actief op zijn processorkern. Gedurende die tijd kan er dus geen andere taak op draaien.

Daarom is het raadzaam om spinlocks alleen in multicoresoftware te gebruiken en ze te vermijden in enkelkernsontwerpen. Bovendien moeten ze alleen worden gebruikt als de verwachte maximale wachttijd kleiner is dan de context switch-tijd van het OS. En de applicatiesoftware mag niet blokkeren terwijl deze een spinlock beheert.

In tegenstelling tot RTos-semaforen en -mutexen is het normaal gesproken niet erg om een spinlock te ver- en ontgrendelen met een interrupthandler of interrupt service routine (ISR) – zelfs als de ISR korte tijd op de lock moet spinnen. Maar dit verhoogt wel de interruptvertraging van de ISR en vermindert de reactietijd.

Oppervlakkig

In dit artikel zijn al een paar valkuilen bij het ontwerpen van SMP-software naar voren gekomen, maar er is nog een aanzienlijk aantal die aandacht verdient. Ze komen allemaal neer op het feit dat mensen, waaronder begaafde softwarearchitecten, niet sterk zijn in het denken over parallellisme in complexe systemen. Menig goed softwareontwerp voor enkele kernen kan falen in een multicoreomgeving. Multicoreontwerp is fundamenteel anders.

In multicoreomgevingen is de timing van taakscheduling minder geordend dan in enkelprocessorsystemen. Daardoor neemt de ernst van timinggerelateerde bugs toe, zoals race conditions, waar de juistheid van een resultaat afhangt van de relatieve timing tussen taken (zie Figuur 4). Om vergelijkbare redenen zijn ook bugs die te maken hebben met het gebrek aan reentrancy waarschijnlijker in SMP.

Bovendien zijn de problemen rondom taakprioriteiten waarschijnlijker in de echt parallelle omgeving van een multicore-Soc dan in de traditionele pseudoparallelle omgeving van een enkelkernsmultitaskingsysteem. Een van de hoofdredenen is dat taakprioriteiten niet langer meer uitsluiting garanderen in de multicorewereld. Aangezien er meerdere kernen zijn, kunnen meerdere taken met dezelfde prioriteit tegelijkertijd draaien – een onmogelijke situatie bij enkelkernsomgevingen. Met andere woorden, ontwerpstrategieën zoals coöperatieve scheduling werken niet in SMP-omgevingen. Meerdere kernen zijn ook te gebruiken om meerdere taken met verschillende prioriteit te draaien. Daarmee overtreden ze de traditionele aanname dat een taak niet kan draaien als er al iets anders met hogere prioriteit actief is.

Multicoresystemen lijken slechts oppervlakkig op geminiaturiseerde gedistribueerde systemen. Er zijn aanzienlijke verschillen in communicatie tussen de kernen en topologie die moeten worden meegenomen bij het ontwerp. Daarom zijn veel van de aannames die de basis vormden voor het traditionele ontwerpen eenvoudigweg niet langer meer geldig.

David Kalinsky is directeur klantonderwijs bij D. Kalinsky Associates, dat korte cursussen geeft over embedded systemen en softwareontwikkeling voor professionele engineers.

Abonneer direct op onze nieuwsbrief

abonneren

Time management in innovation

2 oktober - 1 november

Eindhoven

Advanced motion control

5 november - 11 november

Eindhoven