Waardevoorspelling
Stel je voor dat een kok in een drukke keuken niet wacht tot een bestelling binnenkomt, maar op basis van ervaring al vast begint met het voorbereiden van het gerecht dat hij denkt dat er besteld gaat worden. Klopt zijn gok, dan heeft hij tijd gewonnen. Klopt het niet, dan gooit hij het weg en begint opnieuw. Iets vergelijkbaars doen moderne computerchips met waardevoorspelling (in het Engels: value prediction): de processor gokt wat de uitkomst van een berekening zal zijn, nog vóórdat die berekening daadwerkelijk is uitgevoerd, en gaat daar alvast mee verder rekenen.
Dat klinkt vreemd voor iets dat we vaak als foutloos en exact beschouwen, maar het is een logisch vervolg op een techniek die al decennia in processors zit: speculatie. Net zoals chips al gissen welke kant een if-else-vertakking in een programma opgaat (dat heet branch prediction, ofwel taksvoorspelling), proberen onderzoekers ook de waarden te voorspellen die uit berekeningen komen. Lukt de gok, dan is de chip sneller klaar. Lukt het niet, dan wordt het speculatieve werk weggegooid en opnieuw gedaan met de juiste waarde — net als bij de kok.
Wat is het precies?
Moderne processors voeren instructies niet altijd keurig één voor één uit in de volgorde waarin een programma ze aanbiedt. Ze proberen zoveel mogelijk instructies tegelijk te verwerken, omdat chips tegenwoordig meerdere rekeneenheden naast elkaar hebben. Het probleem is dat veel instructies van elkaar afhankelijk zijn: instructie B heeft de uitkomst van instructie A nodig om te kunnen beginnen. Zolang A niet klaar is, moet B wachten. Dat wachten kost tijd, vooral als A een langzame operatie is, zoals het ophalen van gegevens uit het geheugen.
Waardevoorspelling doorbreekt dat wachten. De processor houdt een klein geheugen bij — een voorspeller — waarin het bijhoudt welke waarden een bepaalde instructie in het verleden opleverde. Blijkt een instructie vaak dezelfde of een goed voorspelbare waarde te geven (bijvoorbeeld omdat een geheugenadres steevast hetzelfde getal bevat), dan geeft de chip die verwachte waarde alvast door aan instructie B, nog voordat A daadwerkelijk is uitgerekend. Instructie B rekent daar speculatief mee verder.
Zodra de echte uitkomst van A bekend is, controleert de chip of de gok klopte. Was de voorspelling juist, dan is er tijd gewonnen: B was allang klaar. Was de gok fout, dan verwijdert de chip ("squasht") al het speculatieve werk dat op de foute waarde was gebaseerd en herhaalt het met de juiste waarde — net als bij foutieve taksvoorspelling. Dit hele proces gebeurt volledig binnen de hardware, in nanoseconden, zonder dat software of gebruiker er iets van merkt.
De reden dat dit vaak werkt, is een fenomeen dat onderzoekers waardelocaliteit noemen: in echte programma's herhalen bepaalde berekeningen zich verrassend vaak met identieke of sterk gelijkende uitkomsten. Denk aan een teller die met kleine stapjes omhoog gaat, of een geheugenadres dat steeds naar hetzelfde soort gegeven wijst.
Wat wil men ermee bereiken?
Het achterliggende doel is simpel: processors sneller maken zonder dat de kloksnelheid (het aantal keer per seconde dat een chip tikt) omhoog hoeft. Kloksnelheden zijn sinds het midden van de jaren 2000 nauwelijks meer gestegen, omdat chips anders te heet worden en te veel stroom verbruiken. Fabrikanten zoeken daarom naar slimmere manieren om binnen dezelfde tijdspanne meer werk te verzetten — dat heet het vergroten van de instructieparallellie: hoeveel instructies een chip tegelijk kan afhandelen.
Onderzoekers noemen dit ook wel het doorbreken van de "dataflow-limiet": de gedachte dat een programma nooit sneller kan lopen dan de kortste keten van onderling afhankelijke berekeningen toelaat, tenzij je iets doet dat buiten die keten om gaat. Waardevoorspelling is precies zo'n truc: door afhankelijkheden te doorbreken met een gok, kan een programma in theorie sneller lopen dan zijn eigen wiskundige structuur normaal gesproken toestaat.
Een tweede, meer specifieke toepassing heet load value prediction (voorspelling van geheugenwaarden): het voorspellen van gegevens die uit het geheugen moeten worden opgehaald. Geheugentoegang is relatief traag vergeleken met rekenen zelf, dus als een chip alvast kan gokken wat er in het geheugen staat, wint dat veel tijd op precies de plekken waar processors vaak vastlopen.
Voorbeelden uit de praktijk
Het onderzoeksveld begon serieus vorm te krijgen met het werk van Mikko Lipasti en John Paul Shen aan de University of Wisconsin-Madison, die halverwege de jaren negentig lieten zien dat waardevoorspelling in simulaties merkbare snelheidswinst kon opleveren door de dataflow-limiet te omzeilen. Dit wordt algemeen beschouwd als het startpunt van het vakgebied en heeft sindsdien talloze vervolgstudies geïnspireerd.
Na die eerste doorbraak volgden jarenlang vooral academische studies, uitgevoerd met chipsimulatoren zoals gem5, waarin onderzoeksgroepen wereldwijd varianten van voorspellers testten: eenvoudige "laatste waarde"-voorspellers, patroongebaseerde voorspellers en hybride ontwerpen die meerdere technieken combineren.
Interessanter — en leerzamer — is wat er gebeurde toen een fabrikant het daadwerkelijk in silicium bouwde. Rond 2020 bevatte AMD's Zen 3-architectuur naar verluidt een vorm van waarde- of geheugenvoorspelling. Kort na de introductie kwamen beveiligingsonderzoekers echter met aanwijzingen dat dit soort speculatieve mechanismen, net als eerdere Spectre-achtige kwetsbaarheden, gegevens konden laten "lekken" via zijkanalen. AMD paste de functionaliteit daarop aan via een firmware-update. De precieze technische details en de exacte onderzoekers achter deze ontdekking zijn niet met volledige zekerheid vast te stellen zonder de oorspronkelijke bronnen erbij te pakken, maar het algemene patroon — een fabrikant die speculatieve waardevoorspelling inbouwt en vervolgens beperkt vanwege beveiligingsrisico's — is illustratief voor de spanning in dit vakgebied tussen snelheid en veiligheid.
Daarnaast verschijnen er op grote computerarchitectuurconferenties zoals ISCA, MICRO en HPCA nog regelmatig nieuwe papers over waardevoorspelling, vaak gericht op het combineren ervan met machine learning om betere voorspellingen te doen, of op het toepassen ervan in open architecturen zoals RISC-V, waar onderzoekers vrijer kunnen experimenteren dan bij gesloten commerciële ontwerpen.
Hoe ver is de techniek?
Waardevoorspelling is, meer dan dertig jaar na de eerste voorstellen, nog altijd voornamelijk een onderzoeksonderwerp en geen standaardonderdeel van de meeste processors die in laptops, telefoons of servers zitten. Dat komt niet doordat het niet zou werken, maar door een aantal praktische obstakels.
Ten eerste is de "boekhouding" duur: elke instructie die je speculatief laat rekenen, moet je kunnen terugdraaien als de voorspelling fout blijkt. Hoe meer speculatie, hoe complexer en foutgevoeliger de hardware die alles moet controleren en eventueel terugdraaien.
Ten tweede, en dat is de laatste jaren steeds belangrijker geworden, brengt speculatie beveiligingsrisico's met zich mee. Sinds de ontdekking van Spectre en Meltdown in 2018 weten chipontwerpers dat speculatieve uitvoering onbedoeld gevoelige gegevens kan blootleggen aan aanvallers, via zogeheten side-channel-aanvallen (zijkanaalaanvallen): technieken waarbij niet de data zelf wordt gestolen, maar indirecte sporen ervan — zoals timingverschillen — worden afgeluisterd. Waardevoorspelling voegt weer een nieuwe vorm van speculatie toe, en dus ook een nieuw potentieel lek, wat verklaart waarom fabrikanten hier terughoudend mee zijn.
Het tempo van vooruitgang is daardoor grillig: er is een gestage stroom van academisch onderzoek, maar de stap naar massaal ingezette commerciële hardware verloopt traag en voorzichtig. Voor gewone gebruikers verandert er dan ook weinig op korte termijn; dit is vooral een achtergrondgevecht tussen snelheid en veiligheid dat zich afspeelt in onderzoekslabs en chipontwerpafdelingen.
Wie werken eraan?
Het fundamentele onderzoek is decennia geleden op gang gebracht aan de University of Wisconsin-Madison, dat sindsdien geldt als een van de bakermatten van computerarchitectuuronderzoek op dit gebied. Wereldwijd houden universitaire onderzoeksgroepen zich met varianten van het onderwerp bezig, vaak in samenwerking met of gefinancierd door chipfabrikanten.
Onder de grote commerciële partijen die relevant onderzoek doen of gerelateerde speculatieve technieken in hun processors verwerken, vallen Intel, AMD en ARM: alle drie hebben onderzoeksafdelingen die publiceren over speculatieve uitvoeringstechnieken, en AMD heeft als een van de weinigen daadwerkelijk een vorm van waardevoorspelling in commerciële chips beproefd. Ook binnen het open-source RISC-V-ecosysteem experimenteren onderzoeksgroepen met dit soort technieken, omdat de open architectuur ruimte biedt voor experimenten die bij gesloten ontwerpen moeilijker zijn.
Verder wordt het vakgebied gedragen door de bredere computerarchitectuurgemeenschap rond conferenties als ISCA, MICRO en HPCA, waar zowel universiteiten als de onderzoeksafdelingen van grote chipbedrijven jaarlijks nieuwe bevindingen presenteren.