Techniek die de uitkomst van een voorwaardelijke sprong voor de uitvoering voorspelt en vooruit instructies verwerkt zonder de pipeline stil te leggen. Bij een foute voorspelling wordt het werk opnieuw gedaan.
Japanse benaming: 分岐予測
“Sprongvoorspelling (branch prediction)” komt voor in 12 oefenvragen uit 6 onderwerpen, bijv. CPU en architectuur, Instructieset en assembly, Hardwarebeveiliging.
Vakgebied: CPU en architectuur
Een CPU met pipeline haalt elke cyclus nieuwe instructies op, maar of een voorwaardelijke sprong wordt genomen, en waarheen, is pas bekend wanneer die enkele trappen later wordt uitgevoerd. Wachten zou de pipeline stil laten staan, en ruwweg één op de vijf instructies is een sprong. Sprongvoorspelling raadt in plaats daarvan de uitkomst bij het ophalen en gaat speculatief verder langs het voorspelde pad. Is de gok juist, dan gaat er geen tijd verloren; is hij fout, dan worden de speculatieve instructies weggegooid zonder de architecturale toestand te beïnvloeden en begint het ophalen opnieuw op het juiste pad, wat in een diepe pipeline een tiental tot ongeveer twintig cycli kost.
Statische schema's gebruiken vaste regels, zoals voorspellen dat sprongen terug (lussen) worden genomen en sprongen vooruit niet. Dynamische voorspellers leren van de geschiedenis: een tabel met verzadigende 2-bitstellers, geïndexeerd op sprongadres, heeft twee foute uitkomsten op rij nodig om de voorspelling om te draaien, zodat het verlaten van een lus maar één misser veroorzaakt. Betere voorspellers combineren het adres met een globale geschiedenis van recente uitkomsten om correlaties tussen sprongen te vangen. De richting voorspellen is maar het halve werk; een branch target buffer (BTB) levert het doeladres, en een return address stack voorspelt terugkeer uit functies.
De impact kan worden geschat als extra cycli per instructie (CPI): sprongfrequentie × misvoorspellingspercentage × penalty. Met 20 procent sprongen, 95 procent nauwkeurigheid en een penalty van 20 cycli is dat 0,2 × 0,05 × 20 = 0,2 extra CPI, een groot deel van het budget van een moderne core. Daarom doen verbeteringen in nauwkeurigheid van een procent of twee ertoe. Voor sprongen die van willekeurige data afhangen en niet kunnen worden voorspeld, gebruiken compilers en programmeurs soms code zonder sprongen, zoals conditional moves, waarbij een beetje extra werk wordt ingeruild voor de garantie dat er geen flushes optreden.
Verkeerd voorspelde instructies worden architecturaal weggegooid, maar ze kunnen toch sporen achterlaten in de microarchitecturale toestand, zoals caches. Aanvallen van het Spectre-type trainen de voorspeller zodat een slachtoffer speculatief geheime data leest en die via cachetiming lekt. Verdedigingen zijn onder meer speculatiebarrières na gevoelige grenscontroles (zoals lfence in x86), het maskeren van array-indices, retpoline-reeksen voor indirecte sprongen en microcodeinstellingen voor de voorspellers. Elke beperking kost prestaties, dus worden ze selectief toegepast. Oudere ISA's zoals MIPS gebruikten branch delay slots in plaats van voorspelling, een regel die voor latere ontwerpen een last werd.
Antwoord: A. Het resultaat van een sprong voorspellen en alvast volgende instructies uitvoeren, zodat de pipeline minder vaak stilstaat
In een pipeline staat de volgende instructie pas vast als het resultaat van een sprong bekend is, waardoor de verwerking stilvalt. Bij sprongvoorspelling wordt het sprongdoel op basis van onder meer eerdere historie voorspeld en gaat de uitvoering alvast verder; alleen bij een misser wordt opnieuw begonnen. Ongeveer één op de vijf programma-instructies is een sprong, dus de invloed is groot, en huidige krachtige CPU's voorspellen met een nauwkeurigheid van meer dan 95 %. Doordat één misser circa tien tot twintig klokcycli kost, is zelfs een kleine verbetering van de nauwkeurigheid van belang voor de prestaties.
De CPU gooit de instructies weg die hij speculatief langs het verkeerde pad heeft opgehaald en uitgevoerd, en begint opnieuw vanaf het juiste doel, wat in een typische diepe pipeline ruwweg 10 tot 20 cycli kost.
High-performance voorspellers halen bij gewone code doorgaans meer dan 95 procent nauwkeurigheid, al kunnen sprongen die van willekeurige data afhangen veel moeilijker te voorspellen zijn.
Sprongvoorspelling is de gok welke kant een sprong op gaat; speculatieve uitvoering is het daadwerkelijk uitvoeren van instructies langs dat gegokte pad voordat de gok is bevestigd.
Bij sprongvoorspelling wordt het sprongdoel op basis van onder meer eerdere historie voorspeld en gaat de uitvoering alvast verder; alleen bij een misser wordt opnieuw begonnen.
Wat is het doel van sprongvoorspelling (branch prediction) …Gegevensafhankelijkheden, sprongen en conflicten om middelen kunnen de stroom verstoren (hazards); hiertegen worden forwarding en sprongvoorspelling ingezet.
Wat is het belangrijkste doel van pipelining in een CPU?Superscalaire architectuur, out-of-order uitvoering, sprongvoorspelling en grote caches zijn allemaal technieken die de IPC verhogen.
Welke maat geeft het aantal instructies aan dat per klokcyc…Bij een foute sprongvoorspelling of uitzondering kunnen de resultaten van latere instructies worden weggegooid en kan de juiste toestand worden hersteld, zodat het van buiten lijkt alsof het programma in volgorde is uitgevoerd (precieze uitzonderingen).
Welk mechanisme legt in een out-of-order CPU de resultaten …De interne opbouw, zoals het aantal pipelinetrappen, de cachegrootte en de methode van sprongvoorspelling, heet microarchitectuur en wordt los van de ISA vastgesteld.
Welke uitspraak over twee CPU's met dezelfde instructieseta…Doorvoer (throughput) Instructiesetarchitectuur (ISA) Pipelining IPC CPI PC-relatieve adressering Positie-onafhankelijke code (PIC) Branch delay slot Numerieke apertuur (NA) GPU