Branchpredikering

Branchpredikering er en teknik inden for computerarkitektur, der forsøger at forudsige udfaldet af en betinget gren i en instruktionsstrøm for at holde en processorens pipeline så fuld som muligt. Ved korrekt forudsigelse kan instruktionshastigheden øges, fordi unødvendige pauser undgås, mens en forkert forudsigelse kan føre til en pipeline-flush og ekstra omkostninger.

Der findes statiske og dynamiske prediktorer. Statiske prediktorer følger faste regler, som f.eks. altid at tro at grene er taget eller ikke-taget, eller anvender en simpel regel baseret på grenens kendingsmønster. Dynamiske prediktorer lærer af historik og tilpasser sig programmeringsmønstre. De mest almindelige dynamiske tilgange deles i lokale og globale prediktorer og kan omfatte to-niveau adaptive strategier.

Lokale prediktorer knytter en historiesignatur til hver gren og husker tidligere udfald for den enkelte gren. Globale prediktorer deler en fælles historik for alle grene og bruger denne globale tilstand til forudsigelse. Two-level adaptive prediktorer kombinerer ofte global eller lokal histories information med en tabel af tællere (saturation counters) til at afgøre udfaldet. Eksempler inkluderer gshare (global historie blandet med programmodersted ved hjælp af XOR) og bimodal/pattern history tables (PHT) til mønstergenkendelse. Avancerede varianter kan også indeholde løkke-prediktorer og tour- eller indirect-branch forudsigelse.

Branch Target Buffer (BTB) caches måladresser for taget grene og støtter hurtigt hent af den forrige instruerionsadresse. For indirekte grene og kalde-/returretningsadresser anvendes ofte en Return Address Stack (RAS) for at forbedre forudsigelse af returer.

Effekten af branchpredikering er reduktion af stald og forbedret ydelse, men misprediktioner medfører pipeline-flush og energiforbrug. Moderne processorer bruger ofte multiple niveauer af forudsigere for at opnå høj præcision og lavt energiforbrug.