0xDEADBEEF

RSS
««« »»»

Branch prediction (implementace v procesorech)

28. 8. 2017

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 ~4x 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:

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í:

píše k47 (@kaja47, k47)