Hoe parallelliseer je een loop?

Author:

Bryon Moyer is VP Marketing bij Vector Fabrics.

Reading time: 6 minutes

Embedded systemen krijgen meer en meer te maken met architecturen die uit meerdere rekencomponenten bestaan – multicore processoren, maar ook complexe heterogene systemen zoals mobieltjes-Socs. Softwareontwikkelaars moeten de vaardigheid bezitten om de programmatuur in stukken te ’breken‘ zodat de delen parallel aan elkaar kunnen opereren. Vaak gaat het dan ook nog eens om code die ze zelf niet geschreven hebben, zoals opensource programmatuur die ze moeten aanpassen of oude code die moet worden overgezet naar het nieuwe platform.

Bij desktopapplicaties zijn de kansen voor parallelle taken overduidelijk aanwezig door de rijke gebruikersinterface en vele andere functies van de software – denk aan spellingscontrole, indexeren, rekenen en dergelijke. Embedded systemen vormen echter een grotere uitdaging. Daar voeren de meeste programma‘s slechts één enkele taak uit, vaak op een lineaire (sequentiële) manier.

Wat embedded software kwalitatief echter van desktopsoftware onderscheidt, is het grote aantal loops (lussen). De meeste embedded programma‘s bestaan uit een while running-loop die blijft herhalen totdat het programma eindigt. Binnen die lus wordt de meeste tijd weer besteed in andere loops.

De loops kunnen het resultaat zijn van algoritmische eisen, bijvoorbeeld het doorlopen van matrices. Een andere reden voor hun introductie kan zijn dat er meer data moet worden verwerkt dan mogelijk is in een enkele bewerking, zoals bij het lezen en verwerken van een bestand. Ze kunnen ook ontstaan doordat een dataverwerker herhaaldelijk controleert of er informatie is, zoals een packet-processor die het netwerk in de gaten houdt en kijkt of er nieuwe pakketjes op verschijnen.

Oneven

Een lus begint met in beginsel kleine taken, maar door de eindeloze herhaling kan het oplopen naar een grote compute load. Hierom zijn loops een interessant aanknopingspunt voor het parallelliseren van een programma en het verdelen over meerdere processing-cores.

De meest gebruikelijke aanpak is dataparallellisatie. Dit betekent dat meerdere identieke componenten tegelijkertijd op verschillende stukken van de data werken. In essentie wijzen we verschillende iteraties van de loop toe aan verschillende processing-cores. Dit kan eenvoudig door een vectoriserende compiler te gebruiken. Als de lussen simpel en voorspelbaar zijn met weinig onderlinge data-afhankelijkheden, dan kan de compiler succesvol vectortaken creëren uit simpele instructies. Programmeurs kunnen ook een systeem als OpenMP gebruiken om aan te geven waar er kan worden geparallelliseerd.

Vaak zullen de kritieke loops echter te complex zijn voor dataparallellisatie. In deze gevallen kan functioneel parallellisme een alternatief zijn, ook wel pipelining genoemd in de hardwarewereld. Dit vereist echter veel meer tijd, moeite en ervaring van de programmeur. Nieuwe producten zoals de VFAnalyst-tool helpen bij het bepalen of een loop baat heeft bij een functionele splitsing en geven aan hoe dit kan worden gedaan.

Functionele parallellisatie heeft betrekking op het opsplitsen van de lusbewerking zelf. Als een enkele iteratie al veel rekenwerk vereist, is het mogelijk om de loop in twee of meer taken te splitsen. Het eerste deel van de taak voert dan een gedeelte van het werk uit en geeft het resultaat door aan het tweede deel, dat zijn resultaat weer doorgeeft aan het derde, enzovoorts.

Daarbij kunnen er wel afhankelijkheden zijn tussen de verschillende stappen. Zo kan de tweede stap doorgaans niet beginnen voordat de eerste stap is uitgevoerd. Dit introduceert vertragingen. In de ideale situatie kan elke stap meteen beginnen omdat hij totaal onafhankelijk van informatie die in een eerdere stap wordt gegenereerd. Daarom is er bij loopdistributie aandacht nodig voor de plaats waar de loop wordt gesplitst. Als gegevens worden geproduceerd voor de splitsing en pas verwerkt na de splitsing, dan moeten die data gecommuniceerd – gesynchroniseerd – worden tussen de twee onderdelen. Eerder kan het tweede gedeelte niet beginnen.

Loops kunnen we verder parallelliseren door distributie te combineren met unrolling. Loop-unrolling betekent dat de lusbewerking per iteratie vaker wordt herhaald, waardoor er minder iteraties zijn en de daarmee gepaarde overhead wordt gedrukt. Als een loop bijvoorbeeld zestien iteraties heeft en er wordt vier keer een unroll uitgevoerd, dan bestaat de loopbewerking nu uit vier expliciete kopieën van de originele lus aan elkaar geschakeld. Deze resulterende loop hoeft maar vier keer uitgevoerd te worden.

Twee processoren kunnen het aantal loopiteraties splitsen door één keer een unroll toe te passen en de resulterende lus te distribueren over de processoren. Op deze manier kan de eerste processor bijvoorbeeld de oneven iteraties nemen en de tweede processor alle even iteraties.

Fijnmazig

Dit is in principe ver door te voeren. Als de loop helemaal ’uitgerold‘ is en er net zo veel processoren als iteraties zouden zijn, worden alle iteraties in parallel uitgevoerd. Er is echter een factor die de mate van parallellisatie door unrolling sterk beperkt: het synchroniseren van de data tussen de iteraties. Dit is vergelijkbaar met het synchronisatieprobleem bij simpele loopdistributie. Relaties tussen de loopiteraties worden loop-carry dependencies genoemd. Deze afhankelijkheden hebben synchronisatie nodig als er parallellisatie op wordt toegepast.

Er zijn verschillende manieren om synchronisatie te implementeren – soms is er zelfs aparte hardware voor. Welke manier we ook kiezen, er zal altijd een overhead zijn die we in acht moeten nemen bij het maken van parallellisatiekeuzes. Deze kan zo klein zijn als een simpele indicator die aangeeft dat er data beschikbaar is, maar het kan ook gaan om het sluiten en ontsluiten van datastructuren en kopiëren van flinke hoeveelheden gegevens. De overhead leidt direct tot vertraging bij het introduceren van parallellisatie.

Afhankelijk van het programma kan synchronisatie vrij regelmatig plaatsvinden. Grote regelmaat is een indicatie van heel fijnmazige parallellisatie. Onregelmatige synchronisatie geeft aan dat de parallellisatie grotere brokken betreft.

Neem als voorbeeld een simpele gedistribueerde loop waar een enkele waarde moet worden gesynchroniseerd. Synchronisatie gebeurt dan elke loopiteratie voor een klein beetje data. Het tegenovergestelde is de geneste loop, bijvoorbeeld een lus die zelf weer twee loops bevat: een die data genereert en een andere die deze weer consumeert. Deze twee loops kunnen worden gedistribueerd over verschillende processoren. Synchronisatie zal niet gebeuren voordat de eerste loop volledig klaar is met het genereren van data. Als deze eerste lus zestien iteraties heeft en een verzameling van zestien waardes produceert, dan wordt tijdens de synchronisatie die volledige set doorgegeven aan de tweede taak. Hoe meer datapunten er in de verzameling zijn, hoe langer de consumerende taak moet wachten. Als we data dus in kleinere hoeveelheden per keer kunnen doorzetten, kunnen we meer parallel doen.

We moeten dus een afweging maken tussen de vertraging door synchronisatieoverhead en de vertraging die ontstaat doordat minder syncs betekent dat er minder efficiënt kan worden gerekend. Algemene richtlijn is dat het beter is om een parallellisatiemethode te kiezen waar de minste data moeten worden overgezet.

Het handmatig parallelliseren van code is een lastig karwei. Bij verkeerde keuzes kan de efficiëntie zelfs af- in plaats van toenemen. Als we echter de juiste keuzes maken, geeft dit ingenieurs weer een nieuwe mogelijkheid om de output van hun systemen te vergroten in een tijd waar meer en meer functionaliteit wordt geëist van, in toenemende mate, overbelaste platformen.