Niek Linnenbank voerde zijn onderzoek uit in het kader van een mastertraject Parallel Distributed Computer Systems aan de Vrije Universiteit Amsterdam (pdcs.vu.nl), onder begeleiding van Tomas Ruby, Dirk Vogt en Andrew Tanenbaum. Vandaag de dag werkt hij als software-engineer bij ICT Automatisering. 

16 November 2012

Processormakers blijven steeds meer cores aansluiten op dezelfde geheugenpool, met steeds meer schaalbaarheidsproblemen tot gevolg. Voor toekomstige generaties manycore processoren zouden principes uit rekenclusters een oplossing kunnen bieden, maar dan verkleind naar een enkele chip. Niek Linnenbank bestudeerde voor zijn afstudeerwerk hoe het Minix-besturingssysteem op een experimentele Intel-processor met 48 kernen verspreid kan worden – een ideale omgeving voor een microkernel-OS.

Symmetrische multicore (SMP) werd een paar jaar terug grootschalig uitgerold als de meest voor de hand liggende manier om nog prestatieverbeteringen uit de wet van Moore te persen: in plaats van de extra transistoren te steken in steeds complexere CPU-ontwerpen legden chipmakers simpelweg twee uitvoeringen van hun core naast elkaar. Het aantal rekenkernen in dergelijke SMP-processoren is daarna gestaag opgekrikt van twee naar vier, acht en in sommige modellen zelfs zestien. Zowel hardware als software krijgt steeds meer schaalbaarheidsproblemen naarmate het aantal cores toeneemt.

In een standaard SMP-systeem zijn alle kernen aangesloten op een gedeelde interne databus. Hierover worden gegevens uitgewisseld met externe apparaten zoals het geheugen, videokaarten, netwerkkaarten en opslagmedia. In een SMP-systeem kunnen alle cores hetzelfde geheugen benaderen, dus een softwareprogramma ’ziet‘ altijd hetzelfde geheugen ongeacht de kern waarop hij op dat moment draait.

Het gedeelde geheugen maakt het voor de softwaredesigner iets eenvoudiger om met deze processoren te werken, maar voor niks gaat de zon op. Om de gegevens in het gedeelde geheugen consistent te houden, kan er maar één core tegelijk naar gedeelde datastructuren in het geheugen schrijven. Vaak wordt dit opgelost door middel van een locking-mechanisme: één rekenkern kan het sleuteltje pakken om een gedeeld stuk geheugen te beschrijven.

Intel SCC 2
Intels single-chip cloud computer (SCC) integreert op een enkele chip 48 Pentium-cores, die in tegenstelling tot gebruikelijke multicore processoren hun geheugenruimte niet hoeven te delen.

Daarnaast hebben cores in een SMP-systeem vaak een eigen privé-cache waar ze een deel van het geheugen tijdelijk naartoe kopiëren om leestoegang tot het relatief slome geheugen enigszins te versnellen. Een probleem hiermee is dat de ene kern het zo niet merkt als de data in het gedeelde geheugen door een andere core wordt gewijzigd – die ziet alleen zijn eigen kopie. Zonder maatregelen zullen softwareprogramma‘s op verschillende cores dus mogelijk andere gegevens lezen uit het gedeelde geheugen. In de meeste moderne SMP-systemen wordt dit probleem opgelost door een cachecoherentieprotocol dat op de achtergrond in de hardware draait: wanneer een kern naar een gebied van het gedeelde geheugen schrijft dat andere cores nog in hun cache hebben, zorgt het protocol in de hardware ervoor dat hun privé-caches worden bijgewerkt. Cachecoherentie is veelal aanwezig in de nieuwste SMP-processoren van Intel, zoals de Xeon- en I5-productlijnen.

 advertorial 

Free webinar ‘Modernizing your code base with C++20’

As many production tool chains now adopt C++20 features, the potential this brings is unlocked. What advantages can recent versions offer to your code base? In this webinar we’ll look at the great improvements C++ has gone through and how features like concepts and ranges can transform your code. Register for 2 February, 4PM.

Dit gecentraliseerde geheugenontwerp van SMP-systemen blijkt een hindernis te zijn voor de schaalbaarheid van de software die erop draait. Naarmate het aantal cores en daarmee het verkeer op dezelfde gedeelde databus groeit, vormt de contentie een steeds grotere beperking voor de prestaties. Met name de onderlinge afstemming van de caches speelt hierin een grote rol; het cachecoherentieprotocol moet immers ’onder water‘ steeds meer synchronisatieverkeer versturen. Ook het locking-mechanisme kan leiden tot contentie. Rekenkernen zullen steeds vaker op elkaar moeten wachten om een gedeelde datastructuur te beschrijven naarmate er meer cores in het systeem aanwezig zijn.

SCC_Platform_Overview
De cores op de SCC zijn in een grid-netwerk geplaatst en communiceren door elkaar berichten te sturen.

Valkuil

In een poging een nieuw type microprocessor te bouwen dat verder schaalbaar is, zijn fabrikanten begonnen met systemen die afwijken van de centrale SMP-architectuur. De nieuwste trend is om de cores zelfstandiger te maken. Een goed voorbeeld is Intels single-chip cloud computer (SCC), een experimenteel prototype met 48 Pentium-cores (P58C) aan boord. In de SCC zijn alle rekenkernen verbonden via een on-chip meshnetwerk waarmee ze databerichten naar elkaar kunnen sturen en naar externe apparaten zoals het geheugen. Deze interconnect kan met een bandbreedte van 256 GB/s data uitwisselen tussen twee componenten. In tegenstelling tot de gedeelde databus in een SMP-systeem kunnen meerdere datapakketten op het meshnetwerk prima tegelijk worden verstuurd, mits ze niet over dezelfde lijn tussen twee cores gaan.

In de SCC zijn vier DDR-geheugencontrollers met in totaal maximaal 16 GB aangesloten op het meshnetwerk. Via software is instelbaar welk deel van het geheugen iedere core krijgt. De SCC heeft geen hardware voor cachecoherentie aan boord. Dat maakt het mogelijk de hardware zonder problemen verder op te schalen.

Voor het besturingssysteem is dit echter nog een grote uitdaging. Een standaard Linux-kernel met SMP-ondersteuning gaat ervan uit dat al het systeemgeheugen direct beschikbaar is vanuit alle cores, waarbij gedeeld geheugen altijd dezelfde data moet afleveren aan alle kernen.

Onderzoekers van de ETH Zürich en Microsoft Research hebben een interessante manier gevonden om besturingssystemen te herontwerpen voor manycore systemen zonder cachecoherentie. Het idee achter hun zogeheten multikernel is om de computerarchitectuur te beschouwen als een gedistribueerd systeem. In plaats van het OS te ontwerpen als één groot programma in gedeeld geheugen stellen de onderzoekers voor om de kernel te verdelen in meerdere instanties. Elke kernelinstantie draait op een eigen core en heeft zijn eigen lokale geheugen dat niet fysiek gedeeld is met de andere instanties. Om informatie uit te wisselen, sturen de OS-instanties elkaar berichten.

Een groot verschil tussen een multikernel- en een standaard SMP-kernelarchitectuur is dat alle OS-datastructuren standaard lokaal zijn. Alleen informatie die noodzakelijkerwijs moet worden gedeeld met andere instanties, zoals de procestabel, wordt gesynchroniseerd, en dit gaat via expliciete berichten in plaats van met intrinsiek gedeeld geheugen. Dit maakt het moeilijk schaalbare locking-mechanisme overbodig.

Het repliceren van toestandsinformatie en het synchroniseren van die informatie door middel van message passing is geen nieuw mechanisme; bij gedistribueerde systemen in een netwerk wordt dit al langer toegepast. Nu wordt het echter ook ingezet in een OS. Een subtiele valkuil hierbij is wel dat het uitwisselen van berichten via gedeeld geheugen gaat, wat weer kan leiden tot cachinggerelateerde problemen.

Hot topic

Voor mijn afstudeerscriptie aan de Vrije Universiteit Amsterdam (VU) hebben we het multikernelprincipe toegepast op het Minix-besturingssysteem. Minix is een experimenteel OS dat in de jaren tachtig door Andrew Tanenbaum op de VU is gebouwd voor onderzoeks- en onderwijsdoeleinden. Vanaf de eerste regel code is het geschreven met enkele kernwaarden in het achterhoofd. Ten eerste is isolatie een fundamenteel ontwerpprincipe. Alle softwarecomponenten in Minix, zoals bestandssystemen en devicedrivers, zijn een geïsoleerd proces. Het grote voordeel is dat mogelijk fatale fouten binnen een softwarecomponent geen invloed hebben op de andere componenten, wat het OS fouttolerant maakt – de tweede kernwaarde. De Minix-microkernel zorgt ervoor dat de processen razendsnel informatie kunnen uitwisselen door middel van message passing. Zo kan het proces van het bestandssysteem bijvoorbeeld een bericht naar het diskdriverproces sturen om data te lezen of te schrijven. Een ander voordeel van isolatie is dat softwarecomponenten eenvoudiger on-the-fly geüpdatet kunnen worden – de derde kernwaarde van Minix: OS-software kan worden bijgewerkt zonder dat het complete systeem herstart hoeft te worden, iets wat Windows-gebruikers waarschijnlijk als muziek in de oren klinkt.

Voor Minix is het dus belangrijk om isolatie van onderdelen zo strikt mogelijk te houden. Daarom krijgt elke softwarecomponent slechts minimale toegang tot systeemhardware voor uitvoering van zijn functie. De toepassing van het least privilege-principe – de vierde kernwaarde – beperkt de impact van fouten tot een minimum. Als vijfde en laatste kernwaarde streven de Minix-designers ernaar om het OS zo veel mogelijk conform de Posix-specificatie te houden, zodat het een groot aantal bestaande applicaties kan draaien.

De microkernelarchitectuur is in de geschiedenis van computersystemen vaak onderwerp geweest van soms heftige discussies. Voorstanders benadrukken de betrouwbaarheidsvoordelen zoals beschreven in de kernwaarden. Tegenstanders brengen daartegen in dat microkernels complexer zijn en een hoop overhead introduceren, met prestatieverliezen van dien. De CPU moet namelijk voortdurend van proces wisselen, het zogenaamde contextswitchen – Minix bestaat typisch uit tien tot twintig aparte processen.

Beide partijen hebben terechte argumenten, maar de strijd is nog niet gestreden. Microkernels, en met name Minix, hebben van nature een aantal eigenschappen die ze geschikt maakt voor manycore machines. Op dit moment is het een hot topic bij onderzoekers. Doordat softwarecomponenten maximaal geïsoleerd zijn als aparte processen met hun eigen lokale data, is er weinig behoefte aan gedeeld, coherent geheugen. En elke component kan op een eigen core draaien, waardoor parallelliseren en opschalen vrij makkelijk gaan. De overhead van het contextswitchen wordt daarmee verdeeld over alle kernen in het systeem, waardoor de prestatieverliezen afnemen. Sterker nog: met voldoende rekenkernen kan elke component zelfs zijn eigen dedicated core krijgen en is er helemaal geen contextswitch meer nodig.

Belangrijke stappen

De potentiële schaalbaarheid van een microkernel als Minix in manycore machines hebben we aangetoond door het OS te implementeren op Intels SCC. Daarbij hebben we het multikernelprincipe toegepast: elke core draait een eigen Minix-microkernel, die processen op de kern beheert en het uitwisselen van berichten verzorgt.

Om het OS te kunnen booten op de SCC-cores hebben we eerst de Minix-opstartcode moeten herschrijven. De SCC-kernen missen een aantal belangrijke hardwarecomponenten die wel in een standaard multicore pc aanwezig zijn: Bios, ACPI, Uart, Pic, Pit, IOApic, Ata/IDE-disk, keyboard en muis. Daarnaast verwacht de SCC een speciaal geformatteerd geheugenimage waarmee het OS dient op te starten.

Fundamenteler is de aanpassing aan het message passing-mechanisme van Minix. De SCC biedt hier aparte hardware voor, de message passing buffer (MPB). Dit is een supersnel stukje geheugen van 8 kB op elke core dat vanaf elke andere rekenkern kan worden beschreven. Een van de technische uitdagingen was om de message passing-Api in Minix zodanig te hergebruiken dat bestaande softwarecomponenten niet aangepast hoefden te worden, maar dat er in de adressering wel onderscheid kan worden gemaakt tussen processen op dezelfde core en processen op andere cores. Hiervoor hebben we verschillende alternatieven geëvalueerd. Uiteindelijk hebben we ervoor gekozen om in de procestabel op elke kern stubs te introduceren voor remote processen: een proces stuurt gewoon met de standaard message passing-Api berichten naar de processen, maar als de kernel ziet dat er een stub staat, levert hij het bericht af bij de andere core middels de MPB.

Voor een correcte message passing-implementatie zijn er twee fundamentele mechanismen noodzakelijk: aflevering en notificatie. De aflevering is op verschillende manieren te implementeren. Als eerste poging hebben we in alle MPB‘s voor elke andere core een eigen geheugengebiedje gereserveerd. Hierdoor kan iedere rekenkern altijd berichten afleveren op elke andere core, zonder last te hebben van het overige verkeer. De ruimte voor berichten is echter beperkt: een zevenenveertigste van de totale MPB, ofwel 174 bytes.

De tweede manier is om de MPB te zien als een wachtrij, ook wel circulaire queue genoemd. Om hier berichten aan toe te voegen, moet een core eerst de MPB-specifieke lock bemachtigen om racecondities te vermijden. Een kern heeft dan echter wel veel meer ruimte beschikbaar voor berichten en kan ook meerdere berichten tegelijk in de wachtrij zetten. Uit performanceresultaten is de methode daarom als beste naar voren gekomen. De locking-overhead voor het beschrijven van de MPB vormt in de Minix-implementatie nog geen probleem.

Naast een mechanisme voor de aflevering moet er ook een manier zijn om de software te informeren over de berichten. De beste manier voor notificatie in de SCC bleek door middel van interprocessor interrupts (IPI): elke core in de SCC kan een interrupt veroorzaken op een willekeurige andere kern. Die stopt dan tijdelijk met het huidige programma om het binnenkomende bericht te verwerken.

Een alternatief voor notificatie is polling, waarbij de software zelf op geregelde tijdstippen kijkt of er wat nieuws is. Het systeem heeft daarmee minder last van de vertraging die IPI‘s veroorzaken. Toch bleken de prestaties met dit mechanisme meestal lager dan bij notificatie. Bij het versturen van berichten moet namelijk niet alleen de ontvanger worden ingeseind dat er een nieuw bericht is, maar moet ook de verzender weten dat zijn bericht is aangekomen. Met polling moet een kern dus voortdurend via de mesh in de MPB van de ontvanger kijken of zijn verstuurde berichten zijn aangekomen, terwijl er bij notificatie slechts één IPI wordt gegenereerd. Wanneer een rekenkern communiceert met veel andere cores wordt de mesh daardoor te veel belast. Alleen bij een-op-eenverkeer tussen kernen levert polling een snelheidswinst op ten opzichte van IPI‘s.

Al staat het onderzoek naar besturingssystemen voor manycore machines nog in de kinderschoenen, de eerste belangrijke stappen zijn al gezet. Mijn werk legt een stevige basis voor verder onderzoek naar Minix als manycore besturingssysteem op de SCC. Het message passing-mechanisme is efficiënt, betrouwbaar en schaalbaar gebleken. Toekomstig werk zal meer inzicht geven in de mogelijkheden die een microkernel biedt voor manycore systemen. De experimenten met multi- en microkernels op manycore systemen tonen aan dat de toekomst van besturingssystemen gedistribueerd van aard is. Zolang hardwareleveranciers doorgaan met het verbeteren van parallellisme in microprocessoren zullen wij softwaredesigners telkens de lat hoger leggen met het opschalen van besturingssystemen, zodat manycore systemen uiteindelijk kunnen ontwikkelen in kwalitatief hoogwaardige producten.

Edited by Pieter Edelman