Szinte minden számítógépes programban vannak a kód részei, amelyek külön utakra ágaznak el. Például egy if-then-else utasításnak két lehetséges kimenetele van. Ezek az állítások nem jelentenek problémát a szekvenciális processzoroknak, mivel a CPU minden parancsot sorrendben dolgoz fel. Az ágak nagy problémát jelentenek a csővezetékes processzorok számára, mivel egyszerre több utasítást hajtanak végre.
A forgatókönyv
Egy két lehetséges kimenetelű elágazó utasítással rendelkező program esetében a két lehetséges kódút nem lehet ugyanazon a helyen. Az egyes opciók végrehajtásához szükséges feldolgozás eltérő lesz. Ellenkező esetben a program nem ágazik el. Valószínűleg szép számmal lesznek olyan elágazó állítások, amelyeket csak egyszer veszünk fel, például egy if-utasítást.
Vannak hurkot képező elágazó utasítások is. Bár ezek számszerűen nem olyan gyakoriak, mint az egyszer használatos állítások, statisztikailag általában ismétlődnek. Feltételezhető, hogy valószínűbb, hogy egy ág visszavisz egy hurkon, mint nem.
Miért probléma ez?
Nem mindegy, hogyan fogalmazzák meg ezt a problémát egy teljesen szekvenciális processzorban. Ez egyszerűen nem probléma. A következő utasítás első részének feldolgozása előtt ismert, hogy melyik ágat veszik fel.
Egy csővezetékes processzorban azonban a következő utasítások sorba állnak. Már folyamatban vannak, amikor a processzor tudja, hogy melyik ágat veszik fel. Tehát hogyan kezelje a processzor ezt a forgatókönyvet? Van néhány lehetőség. A legrosszabb egyszerűen csak vár, és tétlenül hagyja a csővezetéket, miközben az arra vár, hogy melyik ágon vegye fel a választ. Ez azt jelentené, hogy minden alkalommal, amikor elágazási utasítása van, mindig legalább annyi processzoridő-ciklust veszít, ahány szakasz van folyamatban.
Alternatív megoldásként megpróbálhatja mindkét lehetőséget futtatni a folyamatban, és elvetheti a rossz választást. Ez annak a büntetésnek a felével járna, hogy nem tesz semmit, de még mindig teljesítménybüntetéssel járna minden elágazó kijelentés esetén. Tekintettel arra, hogy a modern CPU-k is képesek az utasításokat nem megfelelően futtatni, lehetséges, hogy megpróbálhatja az összes elágazó utasítást a lehető leghamarabb futtatni. Tehát az eredmény ismert, mielőtt szükség lenne rá. Ez a lehetőség hasznos lehet, kivéve, hogy nem méretezhető. Tegyük fel, hogy viszonylag nagy sűrűségű elágazó állításai vannak. Ebben az esetben egyszerűen képtelen lesz mindegyiket korán futtatni anélkül, hogy tétlensége lenne.
Hogyan kezelik ezt a problémát valójában?
A valóságban a processzor tartalmaz egy elágazás-előrejelzőt. Az elágazás-előrejelző megpróbálja kitalálni, hogy egy elágazási választás melyik eredménye lesz. A processzor ezután feltételezi, hogy az előrejelzés helyes, és ütemezi az utasításokat. Ha az elágazás előrejelző pontos, nincs teljesítménybüntetés.
Ha az elágazás-előrejelző hibát követ el, ki kell öblítenie a folyamatot, és el kell kezdenie a tényleges eredmény feldolgozását. Ez valamivel rosszabb teljesítménybüntetést eredményez, mintha nem tett volna semmit, és csak várta volna az eredményt. A legjobb teljesítmény elérése érdekében fontos, hogy az elágazás-előrejelző a lehető legpontosabb legyen. Ennek számos különböző megközelítése létezik.
Egyező kód
A gépi kódban az elágazás mindig választás a következő utasítás olvasása között, vagy ugrás egy másik utasításkészletre. Az elágazás-előrejelzők néhány korai megvalósítása egyszerűen azt feltételezte, hogy az összes ágat mindig vagy soha nem veszik fel. Ennek a megvalósításnak meglepően jó sikeraránya lehet, ha a fordítók ismerik és ismerik ezt a viselkedést úgy tervezték, hogy a gépi kódot úgy állítsa be, hogy a legvalószínűbb eredmény igazodjon a processzor általános értékéhez feltevés. Ez sok hangolást és szoftverfejlesztési szokások módosítását igényel.
Egy másik alternatíva az volt, hogy megtanuljuk a statisztikából, hogy a hurkokat általában veszik, és mindig ugranak, ha az ág hátrafelé megy utasításfolyamot, és soha ne ugorjon, ha az ugrás előre történik, mert általában ez lenne a statisztikailag kevésbé valószínű állapot egy hurok. Mindkét típusú statikus elágazás előrejelzése, ahol az elágazás eredményét a fordítási időben megjósolják.
Dinamikus ág-előrejelzők
A modern elágazás-előrejelzők dinamikusak, és a jelenleg futó program statisztikáit használják fel a jobb előrejelzési sikerességi arány elérése érdekében. A telítési számláló az összes aktuális ág előrejelző alapja. Az első tipp statikusan vagy véletlenszerűen dől el. Ha egy elágazás megtörtént, vagy nem, az eredmény a memória egy részében tárolódik. Amikor legközelebb ugyanaz az elágazás jön, az elágazás előrejelzője ugyanazt az eredményt jósolja, mint korábban.
Ez természetesen jó előrejelzési arányt eredményez a hurkok esetében. Ennek két változata létezik. A korai verziók egyszerűen egyetlen adatbitet használtak annak jelzésére, hogy az elágazás megtörtént-e vagy sem. A későbbi verziók két bitet használnak a gyengén vagy erősen vett vagy nem vett választás jelzésére. Ez a beállítás továbbra is képes megjósolni a hurok felvételének eredményét, ha a program visszatér hozzá, általában növelve a sikerarányt.
Követési minták
A minták nyomon követése érdekében egyes ág-előrejelzők nyomon követik a meghozott döntések előzményeit. Tegyük fel például, hogy egy hurkot folyamatosan hívnak, de csak négyszer körbefordul, mielőtt kitörne a hurokból. Ebben az esetben egy kétszintű adaptív előrejelző képes azonosítani ezt a mintát, és megjósolni, hogy megismétlődik. Ez még tovább növeli a sikerességi arányt egy egyszerű telített számlálóval szemben. A modern elágazás-előrejelzők erre építenek tovább azáltal, hogy neurális hálózatot használnak a minták észlelésére és előrejelzésére.
Egyes ág-előrejelzők több algoritmust használnak, majd összehasonlítják az eredményeket, hogy eldöntsék, melyik előrejelzést használják. Egyes rendszerek külön-külön nyomon követik az egyes elágazási utasításokat az úgynevezett helyi elágazás előrejelzésben. Mások globális elágazás-előrejelző rendszert használnak az összes legutóbbi elágazási utasítás nyomon követésére. Mindkettőnek megvan a maga haszna és hátránya.
Következtetés
Az elágazás-előrejelző egy csővezetékes CPU speciális része. Megkísérli megjósolni egy elágazó utasítás kimenetelét, mielőtt a tényleges utasítás feldolgozásra kerülne. Ez a folyamatban lévő CPU alapvető funkciója, mivel lehetővé teszi a CPU számára, hogy a folyamat telítettségét tartsa akkor is, ha nem biztos benne, hogy milyen utasításokat kell végrehajtani. Nem csökkentik a teljesítményt, ha helyesek. A modern algoritmusok az esetek 97%-ában pontosak lehetnek viszonylag kiszámítható terheléseknél.
Nincs tökéletes előrejelzési módszer, ezért a megvalósítások eltérőek. A rossz előrejelzés teljesítményre gyakorolt hatása a folyamat hosszától függ. Pontosabban a folyamat hosszát, mielőtt meg lehessen határozni, ha az előrejelzés rossz volt. Ez attól is függ, hogy hány utasítás van az egyes folyamatszakaszokban. A modern, csúcskategóriás asztali CPU-k körülbelül 19 folyamatszakaszból állnak, és mindegyik szakaszban legalább négy utasítást tudnak egyszerre futtatni.