0xDEADBEEF

[RSS]
««« »»»

Branch prediction (implementace v procesorech)

28. 8. 2017

Dan Luu napsal dobrý článek o tom, jak fun­guje a jak je im­ple­men­to­vána branch pre­diction v pro­ce­so­rech a proč je dů­le­žité, aby byla co nej­přes­nější.

V běžném kódu je ne­pod­mí­něný skok (branch) prů­měrně každou pátou in­strukcí. V pi­pe­li­no­va­ných pro­ce­so­rech je cíl skoku známý až v poz­děj­ších fázích pi­pe­line, ale pro­ce­sor po­tře­buje znát cíl co nejdříve, aby mohl začít na­čí­tat a de­kó­do­vat in­strukce, a v pipline ne­vznikla bub­lina. To řeší branch pre­dic­tor, který od­ha­duje díl skoku na zá­kladě dří­věj­šího cho­vání. Vět­šina skoků se chová před­ví­da­telně a velká část z nich je ve smyč­kách. Když skočil sto­krát, s nej­větší prav­dě­po­dob­ností skočí i teď.

Branch miss (tedy špatný odhad) zna­mená za­ho­zení celé pi­pe­line, která ob­sa­huje in­strukce z ne­správné větve pro­gramu. Pro pi­pe­line s hloub­kou 20 to tedy zna­mená ztrátu ~20 taktů. Pokud je každá pátá in­strukce skok a pro­ce­sor by ne­dě­lal žádné odhady vedlo by to ke ~4x zpo­ma­lení.

V článku jsou pre­zen­to­vány pre­dic­tory se vzrůs­ta­jící so­fis­ti­ko­va­ností, které se snaží za­chy­tit stéle kom­pli­ko­va­nější a kom­pli­ko­va­nější vzory a omezit pa­to­lo­gické cho­vání (BP je za­lo­žen na ha­sho­vání a proto se okra­jově dotýká ha­shmap, bloom fil­terů, count-min skečů a kolizí hashů).

Co nej­větší přes­nost je po­třeba, pro­tože (v pre­zen­to­va­ném modelu) i pou­hých 5% ne­přes­nosti vede k po­klesu výkonu o ~20%. Proto vývoj v tomto oboru ne­u­stává.

Ně­které no­vější pre­dic­tory jsou po­psány na­pří­klad v:

Ale to ani zda­leka není vy­čer­pá­va­jící seznam. Mnoho dal­ších metod a zlep­šení bylo na­vr­ženo od té doby.

Re­le­vantní čtení:

píše k47 (@kaja47, k47)