Gedurende de laatste decennia hebben we een spectaculaire evolutie in processor design meegemaakt. Twintig jaar geleden waren computerarchitecten nog processoren aan het bouwen met ´e´en enkele rekenkern met 100 miljoen transistoren aan een klokfrequentie rond de 1.5 GHz. De nieuwste processoren
daarentegen kunnen klokfrequenties bereiken tot 4.5 GHz in de ‘turbo boost’ mode. Ook kunnen ze over meer dan 24 rekenkernen beschikken, die bovendien tegelijkertijd nog verschillende draden kunnen uitvoeren.
Architecten hebben de exponenti¨ele groei in het aantal transistoren gebruikt om de prestatie van een rekenkern te verhogen door het toevoegen van allerlei prestatieverhogende technieken zoals speculatie, pijplijning, out-of-order
uitvoering, grote caches, prefetching, enz. Tegenwoordig zijn brede out-oforder processoren de standaard en is het verder verbeteren van de prestatie van ´e´en enkele rekenkern moeilijk geworden. Daarom gebruiken architecten het toenemend aantal transistoren tegenwoordig voor het verhogen van het
aantal rekenkernen per processor. Door het aantal rekenkernen te verhogen is het mogelijk voor de software-architect om werk simultaan uit te voeren en op
die manier de uitvoeringstijd van parallelle programma’s te verkorten. Technieken zoals herbestemmingsbuffers, bredere pijplijnen, out-of-order verwerking van instructies maken de processor niet alleen sneller, maar ook complexer.
Door deze toenemende complexiteit is de nood aan snelle en nauwkeurige hulpmiddelen om de nieuwe processoren te evalueren heel groot. Het hulpmiddel bij uitstek is tot nog toe altijd simulatie geweest. De nauwkeurigheid
van simulatie is heel hoog, waardoor dit de perfecte oplossing lijkt. Maar omdat deze simulatoren het ontwerp gedetailleerd modelleren, zijn ze heel traag.
Voor langdurende computerprogramma’s leidt dit tot simulatietijden die zo lang duren dat het eigenlijk niet meer nuttig is om te simuleren.
Bij het simuleren van langlopende programma’s kunnen computerarchitecten niet langer vertrouwen op de gedetailleerde simulatoren. Daarom maken ze vaker gebruik van een functionele en/of bemonsterde simulatie. Maar zelfs
deze simulatietechnieken zijn niet altijd bruikbaar als langdurende programma’s
of grote systemen gesimuleerd moeten worden.
Technieken zoals analytische modellen zijn een goede manier om gedetailleerde simulatie aan te vullen. Analytische modellen voorspellen de uitvoeringstijd van programma’s door middel van wiskundige modellen. Het gebruik van de resultaten uit functionele simulatie door de wiskundige modellen
zorgt ervoor dat ze veel sneller zijn ten opzichte van gedetailleerde simulatie.
Desondanks kunnen deze modellen een hoge nauwkeurigheid garanderen. Een voorbeeld van een analytisch model is het intervalmodel [20]. Dit model is gebaseerd op de observatie dat de maximale prestatie of de hoeveelheid instructies die de processor per klokcyclus kan verwerken gelijk is aan de breedte van de pijplijn. De instructiestroom zal echter niet altijd perfect verlopen. Om een nauwkeurige schatting te verkrijgen, modelleert het interval model ook onderbrekingen zoals foutief voorspelde sprongen en/of instructie- en data-cache
missers.
Het intervalmodel is in staat om op een snelle en nauwkeurige manier de prestatie van een programma te voorspellen. Voor elk ontwerp in de ontwerpsruimte dient een nieuwe functionele simulatie uitgevoerd te worden. Deze terugkerende kost is een probleem bij een grote ontwerpsruimte. Om dit probleem aan te pakken wordt er gebruik gemaakt van micro-architecturaal onafhankelijke profileringstechnieken. Een dergelijk profiel bevat enkel eigenschappen die onafhankelijk zijn van de onderliggende micro-architectuur waardoor een programma slechts ´e´en keer geprofileerd moet worden. Vervolgens kan
dit profiel gebruikt worden om micro-architectuurafhankelijke inputs te bepalen voor een analytisch model. Gezien het profiel slechts ´e´en keer opgesteld dient te worden is dit dus de perfecte oplossing voor het profileren van grote ontwerpsruimtes.
De grote uitdaging is het bouwen van deze micro-architecturaal onafhankelijke profileringstechnieken. Om het geheugengedrag te modelleren is reeds een model beschikbaar, StatStack genaamd [18]. StatStack maakt gebruik
van hergebruiksafstanden tussen geheugentoegangen om te voorspellen wat de prestatie is voor een cache-geheugen van eender welke grootte. Er bestaat ook werk rond het modelleren van spronggedrag zoals ‘taken rate’ en ‘transition
rate’ [9, 24]. Ook bestaat er een werk van Yokota et al. dat gebruik maakt van sprongentropie [61]. Bij het gebruik van deze technieken kan er echter geen nauwkeurige voorspelling gemaakt worden van de kost ten gevolge van foutief
voorspelde sprongen. Daarom is er nood aan een nieuwe techniek.
Wij stellen lineaire sprongentropie voor, een nieuwe techniek die bepaalt hoe voorspelbaar het spronggedrag is van een programma. Als de entropie 0
is, betekent dit dat het patroon heel regelmatig is en dat de sprongen makkelijk voorspelbaar zijn. Dit zal leiden tot een laag aantal foutief voorspelde sprongen. Als de entropie 1 is, betekent dit dat er veel willekeurig spronggedrag aanwezig is. Hierdoor zijn sprongen heel moeilijk te voorspellen, wat
zal leiden tot een groot aantal foutief voorspelde spongen. In onze techniek is de definitie van entropie overgenomen van Shannon entropie, maar is de binaire formule omgevormd van een som van logaritmen naar een simpele lineaire
functie. Onze nieuwe lineaire functie komt beter overeen met de werking van sprongvoorspellers, wat een meer nauwkeurige modellering oplevert.
Omdat verschillende sprongvoorspellers een andere prestatie zullen leveren voor deze programma’s, zal elke sprongvoorspeller over zijn eigen model moeten beschikken. We voorspellen het aantal foutief voorspelde sprongen als een
lineaire functie van de sprongentropie. De volgende vergelijking geeft het aantal foutieve voorspellingen M aan in functie van de entropie E: M(E) = α + β × E. (1)
In deze formule zullen α en β berekend worden door middel van training.
Deze parameters zullen anders zijn voor elke prongvoorspeller. Wij valideren deze nieuwe techniek door het voorspellen van de voorspellingsnauwkeurigheid van vijf sprongvoorspellers: GAg, GAp, PAp, gshare en een gecombineerde voorspeller, voor 95 programma’s uit SPEC CPU 2006 en CPB 2011. Deze
techniek levert een gemiddelde fout op van 0.70 MPKI1 voor CBP en 0.89 MPKI voor de SPEC programma’s.
Lineaire sprongentropie kan gebruikt worden voor het sturen van if-conversie. Lineaire sprongentropie is een techniek die met een hoge nauwkeurigheid sprongen kan classificeren in gemakkelijk en moeilijk te voorspellen sprongen.
Dit gebeurt voor elke individuele sprong in een programma waardoor dit profiel gebruikt kan worden voor het sturen van if-conversie. De invloed van het spronggedrag in een programma hangt af van de hoeveelheid foutief voorspelde sprongen. Met andere woorden, als sprongen heel moeilijk te voorspellen zijn,
zal de invloed heel groot zijn. Die impact verkleinen zal moeten gebeuren door het vermijden van deze sprongen. Door onze techniek te implementeren in de LLVM compiler, wordt de prestatie van programma’s tot 2.4% verbetert ten
opzichte van standaard if-conversie.
Lineaire sprongentropie is ook bruikbaar om de invloed van spronggedrag op de prestatie van een programma te bepalen. Eerst wordt een entropieprofiel opgesteld van het programma door het uit te voeren met onze profileringstool. Vervolgens wordt gebruik gemaakt van deze entropie samen
met het model van de gebruikte sprongvoorspeller om het aantal foutief voorspelde sprongen te bepalen. Hieruit kan de totale invloed van alle sprongen bepaald worden op de uitvoeringstijd van het programma. Lineaire sprongentropie is gebruikt in het model van Van den Steen et al. [56] dat werd
voorgesteld op de ISPASS 2015 conferentie. In dit model is de fout van de sprongcomponent slechts 1% in vergelijking met simulatie. Dit leidt tot een fout van 0,16% op de volledige uitvoeringstijd. Het oude model van Yokota daarentegen onderschat de invloed met gemiddeld 60%. Dit leidt tot een fout
van 7% op de totale uitvoeringstijd.
Het model voorgesteld door Van den Steen et al. [56] kan gebruikt worden om de prestatie te schatten van een computerprogramma dat uit slechts ´e´en draad bestaat. Maar aangezien softwareprogrammeurs niet langer kunnen
rekenen op de computerarchitect om de prestatie van ´e´en enkele rekenkern te verbeteren, moeten programma’s aangepast worden om hun rekenwerk parallel uit te voeren. Alleen door veel parallel werk uit te voeren kan de software de
hardware ten volle benutten. Dit voegt weer extra complexiteit toe, zowel voor de softwareontwikkelaar, als voor de hardwaredesigner. Om de softwareon1MPKI: Het aantal fouten per 1000 instructies.Otwikkelaar te ondersteunen bij het optimaliseren van zijn programma’s en om de hardwaredesigner toe te laten snel en effici¨ent een grote ontwerpsruimte te analyseren is er een hoge nood aan betere tools die de noodzakelijke inzichten geven.
Om deze nieuwe uitdagingen aan te pakken, stellen we RPPM voor, een micro-architecturaal onafhankelijke modelleringstool voor het maken van een snelle prestatieschatting voor meerdradige programma’s op parallelle hardware.
Meerdradige programma’s maken gebruik van meerdere, zogenaamde, werkdraden die het rekenwerk verdelen en parallel kunnen uitvoeren. Door het verdelen van het werk zal het programma hetzelfde werk sneller kunnen uitvoeren, maar hierdoor zal de complexiteit van het programma toenemen. Deze draden zullen elkaar be¨ınvloeden, zowel direct door synchronisatie als indirect via het geheugen.
Het eerste grote verschil tussen enkeldradige en meerdradige programma’s is de directe invloed die de verschillende draden kunnen uitoefenen op elkaar door synchronisatie. Deze functies zijn beschikbaar via verschillende bibliotheken
zoals OpenMP, pthread, enz. Draden be¨ınvloeden elkaar via het geheugen.
Om de invloed die draden op elkaar uitoefenen via het geheugen te modelleren, gebruiken we een nieuwe versie van StatStack [1]. Deze tool is in staat om het geheugengedrag van deze meerdradige programma’s te modelleren.
Om synchronisatiegedrag te modelleren worden alle oproepen naar de synchronisatiebibliotheken opgevangen tijdens een profileringsfase, dit samen met alle andere eigenschappen die nodig zijn om de prestatie van elke individuele draad te bepalen alsook het geheugengedrag. Om de uitvoeringstijd van meerdradige programma’s te bepalen, wordt eerst de uitvoeringstijd van alle draden tussen de verschillende synchronisatiepunten bepaald. Dit gebeurt door het
enkeldradige model uit te breiden met de meerdradige StatStack versie. De laatste stap is het terug toevoegen en modelleren van alle synchronisatiegebeurtenissen.
RPPM is in staat de uitvoeringstijd van alle Parsec en Rodinia programma’s te voorspellen met een gemiddelde absolute fout van 11%, een aanzienlijke verbetering ten opzichte van na¨ıve uitbreidingen van het enkeldradige model die leiden tot een gemiddelde fout van 28%. Wij tonen ook aan dat RPPM een
nuttig model is om op een snelle en nauwkeurige manier een ontwerpsruimte te onderzoeken en inzicht te verkrijgen in het gedrag van een computerapplicatie op toekomstige hardware