Hoe programmeurs maximale rekenkracht uit jouw processor persen

De klassieke processor heeft zijn snelheidslimiet bereikt. Waar de kloksnelheid van een processorkern vroeger geregeld verdubbelde, blijft deze nu al een tijdje stabiel.

Om toch vooruitgang te boeken op het gebied van prestaties voegen hardwarefabrikanten steeds meer processoreenheden aan hun chips toe. Quadcore is al lang ingeburgerd en eind dit jaar komt ook Intels eerste octocore op de markt.

Een verdubbeling van het aantal processorkernen brengt echter niet noodzakelijk een verdubbeling van de prestaties met zich mee. De uit te voeren berekeningen moeten immers efficiënt verdeeld worden tussen de verschillende rekeneenheden. Dat is moeilijk, maar niet zo moeilijk als we tot nu toe dachten, aldus een team van onderzoekers aan het MIT.

[related_article id=”152275″]

Algoritmes
Vandaag programmeren ontwikkelaars met zogenaamde lock-free parallelle algoritmes. Lock-freecode is vrij eenvoudig en kan zelfs automatisch geconverteerd worden van sequentiële code. Theoretisch resulteert lock-free echter niet zonder meer in de beste resultaten. Dat heeft de maken met de manier waarop de code werkt.

Lock-free garandeert dat ten minste één rekenkern vooruitgang boekt met een thread binnen een bepaalde termijn. Meerdere threads kunnen namelijk op hetzelfde moment dezelfde systeemmiddelen vereisen. Zo kunnen ze elkaar tegenwerken en raakt er niemand vooruit.

Het gaat om een vrij abstract concept; denk om je er iets bij in te beelden misschien aan twee dikke mannen die door dezelfde deuropening willen. Als ze allebei tegelijk blijven proberen, raakt niemand door de deur. Lock-free zorgt ervoor dat er tenminste één man vooruitkomt.

Theoretisch wil dat zeggen dat het mogelijk is dat één kern vrijwel altijd voorrang krijgt. Dat zou de prestaties van een systeem met meerdere kernen doen terugvallen tot die van een systeem dat er slechts één heeft.

Om zulke situaties te voorkomen werken computerwetenschappers aan alternatieven, wait-free algoritmes gedoopt. Wait-free moet garanderen dat elke kern een minimum aan vooruitgang boekt binnen een bepaalde tijdspanne. Wait-free zou een beter alternatief zijn voor lock-free, maar heeft het nadeel erg ingewikkeld te zijn. Omdat code niet gemakkelijk naar wait-free kan omgezet worden, laten softwareontwikkelaars de methode meestal links liggen.

Willekeur
De studie van MIT lijkt er nu op te wijzen dat lock-free in de praktijk beter werkt dan theoretisch werd aangenomen. In vele gevallen zouden de prestaties van lock-free die van wait-free zelfs evenaren.

Door een computerchip met meerdere kernen in zijn geheel te bekijken stelden de onderzoekers vast dat de kans dat een thread aan een bepaalde kern wordt toegewezen willekeurig is. Een thread zal dus niet elke keer aan dezelfde kern worden toegewezen om dan structureel geblokkeerd te worden om de vooruitgang van het hele systeem te vrijwaren. Die ontdekking resulteerde in de realisatie dat de eigenlijke prestaties van lock-free een stuk hoger liggen dan het aangenomen theoretische minimum.

Zelfs wanneer de computerwetenschappers keken naar het slechtste scenario voor lock-free bleken de resultaten beter te zijn dan het aangenomen minimum. Dat is goed nieuws voor softwareontwikkelaars. Zij kunnen vrolijk blijven verder werken met lock-free zonder zich te moeten verdiepen in het aartsmoeilijke wait-free, en zonder een dip in rekenkracht te moeten verwachten. Ook voor ons is dat mooi meegenomen, want op die manier wordt onze hardware optimaal benut.