Jeg er igang med at skrive en artikel om processor arkitektur, og er lige blevet færdig med Branch Prediction og vil lige hører om jeg jeg har fandt i noget forkert eller andet, men jeg er åben for kritik.
Det skal lige siges at den er lidt lang og kan være svær for helt nybegyndere at forstå
_____
Hvad er branch prediction og hvorfor er den en vigtig del af nutidens processorer?
- For moderne processorer er det vigtig at tilfører deres pipelines en konstant strøm af data, så de ikke løber tør, hvilket vil resultere i et resursespild, da den ikke fortager sig noget i de clock cykluser hvor dens pipelines er tomme.
Dette kan bl.a. ske med if og loop sætninger.
Hvor de ældre processorer måtte vente på udførelsen af disse forgreninger for at se om den skal hente en instruktion fra cachen eller om instruktionen bare skal fortsætte, så er nyere processorer udstyret med det man kalder ”speculative execution" hvor de 2 mest brugte metoder indenfor dette er ”static prediction” og”dynamic prediction”.
Branch prediction er en enhed i processorens forreste del, som styrer strømmen af data i processorens forreste del, og antager hvad resultatet bliver af forgreninger ved at benytter speculative execution til dette.
Speculativ execution går simpelhed ud på at antage hvad forgreningerne bliver med en af de flere metoder der findes til dette: når dekoderen finder en funktion med forgreninger, så sender den instruktionen til branch prediction unit, som vurdere om den skal fortsætte og derved ved sendes tilbage eller om den skal have fat i en anden instruktion fra level1 cachen og ved den sidst mulighed har vi dette scenario:
Branch unit sørger for at den instruktion, der skal bruges ved det udfald den har forudset i fx if-sætninger, bliver hentet vha. branch target og udfører instruktionen samtidig med at instruktionen med forgreningerne bliver udført. Derved spare processoren tid ved at udfører de forskellige instruktioner med forgreninger hurtigere og udnyttelsen af pipelines bliver forbedret, som alt sammen fører til en hurtigere processor.
Dog skal man ikke tro at alt er fryd og gammen: Hvis der bliver antaget forkert, så har det drastiske konsekvenser for ydelsen, da al det arbejde processoren har lavet er til at smide ud og pipelines skal have et ”flush”, hvilket betyder at al data i dem fjernes og processoren må begynde fuldstændig forfra med at udføre instruktionerne, hvilket giver et kæmpe tap af resurser, dog er branch prediction ret præcis og gætter rigtig i ca. 93-95 % af tilfældene.
Static prediction er meget hurtig og kræver ingen beregninger, men dens succesrate afhænger af programmets sammensætning af instruktioner. Ved loop er den ok, men ved andre tilfælde yder den dårligt. Ved et loop antager den at ved fx i < k, hvor k = 1000 vil i hele tiden være mindre end k.
Dvs. at den har nogle fast algoritmer (algoritmer = at beskrive løsningsmetode) til at forudsige simple forgreninger.
Dynamic prediction benytter sig af to tabeller, algoritmerne i denne prediction benytter sig af enten den ene eller begge tabeller.
De to tabeller et:
Branch History Table (BHT)
Branch Target Buffer (BTB)
Disse tabeller indeholder data fra forgreninger, som er blevet udført i processoren.
BHT indeholder dataene fra de forgreninger Branch Prediction Unit´en har mødt i de sidste par cykluser og med de informationer ser den om instruktionen har en indgang til BHT og med de informationer den har indgang til, vil Branch Prediction Unit´en bestemme om der skal benyttes speculative execution eller ej.
Ved speculative execution skal den vide præcis hvor i level1 cachen forgreningen peger, eller Branch target.
BTB gemmer informationen fra tidligere udførte instruktioner, så vil BPU tage fat i Branch target og henter de instruktioner fra adressen, som branch target peger på
