Branch prediction (implementace v procesorech)
Dan Luu napsal dobrý článek o tom, jak funguje a jak je implementována branch prediction v procesorech a proč je důležité, aby byla co nejpřesnější.
V běžném kódu je nepodmíněný skok (branch) průměrně každou pátou instrukcí. V pipelinovaných procesorech je cíl skoku známý až v pozdějších fázích pipeline, ale procesor potřebuje znát cíl co nejdříve, aby mohl začít načítat a dekódovat instrukce, a v pipline nevznikla bublina. To řeší branch predictor, který odhaduje díl skoku na základě dřívějšího chování. Většina skoků se chová předvídatelně a velká část z nich je ve smyčkách. Když skočil stokrát, s největší pravděpodobností skočí i teď.
Branch miss (tedy špatný odhad) znamená zahození celé pipeline, která obsahuje instrukce z nesprávné větve programu. Pro pipeline s hloubkou 20 to tedy znamená ztrátu ~20 taktů. Pokud je každá pátá instrukce skok a procesor by nedělal žádné odhady vedlo by to ke ~4× zpomalení.
V článku jsou prezentovány predictory se vzrůstající sofistikovaností, které se snaží zachytit stéle komplikovanější a komplikovanější vzory a omezit patologické chování (BP je založen na hashování a proto se okrajově dotýká hashmap, bloom filterů, count-min skečů a kolizí hashů).
Co největší přesnost je potřeba, protože (v prezentovaném modelu) i pouhých 5% nepřesnosti vede k poklesu výkonu o ~20%. Proto vývoj v tomto oboru neustává.
Některé novější predictory jsou popsány například v:
- The YAGS Branch Prediction Scheme (snaží se eliminovat kolize výčtem negativních případů, zároveň jsou tu vysvětleny další druhy predictorů)
- Dynamic Branch Prediction with Perceptrons (BP založený na jednoduchých neuronových sítích, které se snaží naučit lineární funkci namísto historických tabulek)
Ale to ani zdaleka není vyčerpávající seznam. Mnoho dalších metod a zlepšení bylo navrženo od té doby.
Relevantní čtení: