Branchprediktion

Branchprediktion er en teknikk i moderne prosessorer som forsøker å forutsi om en gren i programflyten vil bli tatt (taken) eller ikke (not taken) før grenbeslutningen blir kjent. Målet er å holde instruksjonsflyten jevn i en pipelined CPU og dermed redusere unødvendige avbrudd og misprediksjoner som kan koste ytelse.

Historisk sett ble enkle prediktorer basert på 1-bit tilnærming eller en 2-bit saturerende teller brukt. Etter hvert ble to-nivå prediksjon utviklet, der historien til grenene (lokal) eller global historikk ble lagret i tabeller. Slike prediktorer kunne oppdage mønstre i grenadferd og forbedre nøyaktigheten betraktelig.

Det finnes flere tilnærminger: lokal prediksjon bruker en egen historikktabell for hver gren; global prediksjon bruker en felles global historikk (global history register, GHR) og en felles mønsterhistorietabell (PHT). Hybrid- eller kombinasjonsprediktorer velger mellom forskjellige prediksjoner basert på tidligere resultater. Branch Target Buffer (BTB) lagrer mulige måladresser for grener.

Komponentene: BTB for måladresser, GHR for historikk, PHT for selve beslutningen, og ofte en return address stack (RAS) for å håndtere subrutine- og returgren.

Nyere teknikker inkluderer prediktorer basert på maskinlæring, som perceptron-baserte prediktorer, og spesialiserte ordninger for indirekte grener og returgrener. Branchprediksjon er derfor en viktig del av ytelsen i moderne prosessorer, og kontinuerlig forskning søker å øke nøyaktigheten samtidig som kostnader og strømforbruk holdes nede.