SzA19. Az elágazások vizsgálata (Az elágazások csoportosítása, a feltételes utasítások használata, a műveletek eredményének vizsgálata az állapottér módszerrel és közvetlen adatvizsgálattal, az elágazási utasítások aránya az utasítás-mixben, a feltétlen és feltételes elágazási utasítások arányai, az elágazások teljesülési és nem teljesülési arányai)
Feltétlen elágazások −egyszerű feltétlen elágazások →mindig ugrik −eljárás hívás →az ugrás előtt elmentik a visszatérési címet (LIFO elvű tárolás) −visszatérés az eljárásból →felhasználva a visszatérési címet Feltételes elágazások −a cikluszáró feltételes elágazás −egyéb feltételes elágazások (if, case szerkezet) A feltételes elágazások használata Két okból használjuk: Az utasításban meghatározott művelet eredményét vizsgáljuk, pl.: nulla, negatív, átvitel Két operandus összehasonlítása: ha megegyeznek, ugrunk, ha nem, soros folytatás - visszavezethetjük a műveletek eredményének vizsgálatára, kivonjuk egymásból őket és az eredményt vizsgáljuk, tehát gyakorlatilag visszavezettük az előző esetre - A következőekben ismertetett mindkét módszer tartalmaz kifejezetten a két operandus összehasonlítására vonatkozó utasítást. A műveletek eredménye alapján történő feltételvizsgálat a) Állapottér alkalmazásával -Kétféle tér: a művelet eredményének tere, és az eredmény által meghatározott állapottér -Az állapotvizsgálatot a CPU automatikusan végzi, és az eredményt beírja • feltétel kódba (CC – Condition Code) vagy • jelző bitekbe (flag) Működése: •aktualizálása: minden művelet után a CPU karbantartja az állapotteret a megfelelő biteket bebillenti a jelzőbitek közül (pl.: nulla az eredmény, túlcsordulás) •ezt követően a programozó tesztelheti a számára szükséges jelzőbitet, és annak értékétől függően ugrás, vagy soros folytatás Példa: A programozó szeretné elkerülni a nullával való osztást -megoldás1: A művelet elvégzése után közvetlenül kérdezzük le az állapotteret add r1,r2,r3 // r1 ←r2+r3 beq zero // ha az r1=0, akkor ugrik a zero címkére div r5,r4,r1 // r5 ←r4/r1 zero: 1
-megoldás2: Egy korábbi művelet során kaptuk meg az eredményt, és azt regiszterben vagy operatív tárban eltároltuk. Ehhez a vizsgálathoz minden architektúra biztosít utasítást. Legyen az eltárolt eredményünk r1 –ben: teq r1 beq zero div r4,r5,r1 zero:
//ez az r1 tartalma alapján beállítja az állapotteret // r4 ←r5/r1
Példák: IBM 360/370, Intel, Motorola, Power PC, SPARC Értékelés: hátrányok: -Ebben az esetben a tesztelés további időt igényel (párhuzamosítható) -Kiegészítő hardvert is igényel -Megszakítás esetén az adattér mellett az állapotteret is le kell menteni,s ehhez az operációs rendszerre is szükség van -A koncepció alapvetően szekvenciális szemléletű -Párhuzamosítás esetén több jelzőbit-készletet alakítanak ki, pl: az Intel és Motorola: 2db SPARC: 3db PowerPC: 8db Minden utasításhoz hozzá kell rendelni a megfelelő jelzőbit készletet Tesztelésnél nekünk a megfelelő jelzőbit-készletet kell tesztelni -Az állapottér aktualizálása és tesztelése szekvenciális, ami valós függőséget eredményez. Ez visszafogja a teljesítményt, lassít. -(A közvetlen adatvizsgálat kiválóan alkalmas a párhuzamos feldolgozásra) előnyök: -A tárgykód 1-7%-kal rövidebb (nem jelentős manapság) -A jelzőbit (flag) vizsgálata rendkívül gyors Következtetés: A hátrányok súlyosabbak, mint az előnyök, tehát a jövőben inkább a közvetlen adatvizsgálat elterjedése várható b) Közvetlen adatvizsgálat útján -a processzoron belül nem értelmezünk állapotteret -kétféle lehetőség: 1) két utasításos módszer Az egyik utasítással tesztelünk, és az eredményt egy regiszterben tároljuk, a másik utasítással a regiszter tartalmát vizsgáljuk Példa: add r1, r2, r3 cmpeq r7, r1 // ha az r1 tartalma 0, az r7 tartalma logikai igaz lesz beq r7, zero // ha az r7 igaz, ugrik a zero címkére div r5, r4, r1 … zero (Pl: AMD AM29000) 2) egy utasításos módszer Egyetlen utasításban hajtódik végre a tesztelés és a feltételvizsgálat Példa: add r1, r2, r3 beq r1,zero // akkor ugrik a zero címkére, ha az r1 értéke nulla div r5, r4, r1 zero (Pl: Cray szuperszámítógép, DEC Alpha processzorok) Értékelés: -Párhuzamos feldolgozásra is kiválóan alkalmas 2
-Jövőbeli fejlesztésekben várható az alkalmazása Elágazások statisztikája -Az általános célú programokban az utasítások 20% feltételes vezérlés-átadás, tudományosműszaki célú programok esetén 5-10% -A feltételes elágazási utasítások alapblokkokra tagolják a programot -Ha minden 5. utasítás feltételes elágazás, akkor 4db utasítás párhuzamosítható -A gyakorlatban (ha a CPU nem képes feltárni a feloldatlan elágazásokat), ezzel a módszerrel maximum 2x-es gyorsítást érhetünk el -A feltétlen és a feltételes elágazások aránya: Feltétlen elágazások: 1/3 Cikluszáró feltételes: 1/3 -Az ugrás/soros folytatás aránya: fajtái ugrás feltétlen elágazás 1/3 cikluszáró utasítás 1/3 egyéb feltételes 1/6 összesen 5/6 más felmérés 75% SUM 75%
Egyéb feltételes: 1/3
soros folytatás Következmény: mivel az elágazások 75%-a ugrik, ezért a gyorsításnál kiemelten fontos a teljesülő ág gyorsítása
1/6 1/6 25% 25%
3
SzA23. Első generációs (keskeny szuperskalár) processzorokra esettanulmány (Pentium I: Megvalósítás és jellemzők)
-A belső sínrendszer 64 bites -Processzor Két futószalag: o U (master) futószalag: minden utasítás feldolgozására alkalmas (univerzális) o V futószalag: csak az Intel által egyszerűnek titulált utasítások feldolgozására alkalmas pl. FX, L/S, B Mindkét futószalag 5 fokozatú o F, D, gyorsítótár elérés, E, W/B Csak akkor működik párhuzamosan, ha mindkét futószalag egyszerű utasítást dolgoz fel Az FP utasításokat az U futószalag előfeldolgozza, s magát a számítást egy három fokozatú kiegészítő lebegőpontos futószalag végzi -Gyorsítótár: 2 db, egyenként 8KB méretű van belőle, utasítás-, ill. adatgyorsítótár.
4
SzA25. Utasításlehívás I. (A lokális elágazás előrejelzés fogalma, a lokális egyszintű és kétszintű dinamikus elágazás előrejelzés)
Lokális elágazás-becslés Minden egyes elágazási utasítást külön-külön vizsgálunk Egyszintű lokális Fix elágazásbecslés: tipikusan az ugrási irányban folytatjuk a feldolgozást Statikus elágazásbecslés: a programkód alapján, a compiler által, sok ciklus esetén biztosít jobb becslést Dinamikus elágazásbecslés: ugrástörténeten alapul a becslés megvalósítása: IFAR - Instruction Fetch Address Register BHT – Branch History Table
BHT jellemzői: y-tengely: -a számlálóban minden elágazási utasításhoz létrehozunk egy-egy bejegyzést -ezeket az IFAR legkisebb bitjei szerint indexeljük x-tengely: -a hossza lehet 1,2,3 bit, mi a 2 bites változatot vizsgáljuk -telített számláló: a dekrementálásnál a legkisebb érték a 00, inkrementálásnál a legnagyobb érték az 11 értelmezés: 11 erős ugrás a becslés az első 10 gyenge ugrás bithelyiérték alapján 01 gyenge soros folytatás történik 00 erős soros folytatás Működése: becslés: ha a következő végrehajtandó utasítás elágazás, akkor: -a processzor eldönti, hogy a számlálótáblában megtalálható-e az adott elágazási utasítás -ha nem, akkor létrehozza a vonatkozó bejegyzést és az értékét 11-re állítja -ha benne van, akkor a számlálótábla első bitjének értéke alapján következik be a folytatás 5
karbantartás: független a becslési iránytól, amikor kiértékelésre kerül az adott feltétel, akkor: -amennyiben ugrás, akkor az adott bejegyzés értékét inkrementálja -amennyiben soros folytatás, akkor az adott bejegyzés értékét dekrementálja A számlálótábla bejegyzéseinek száma: -1024 (1k) bejegyzést befogadni képes tábla már nagynak számít -nagy tábla esetén minden elágazási utasításhoz egy bejegyzés tartozik -kisebb tábla esetén több elágazási utasítás osztozik egy bejegyzésen -> rosszabb becslés -amennyiben a számlálótábla nagy, akkor a pontosság 93,5% -előnye ennek a módszernek, hogy az ismételt ugrási sorozatokat ugrásként jelzi előre (ciklusok) -pl: Pentium I. Kétszintű lokális
Jellemzői: 1.szint: BHT - y tengely: -A CPU minden elágazási utasításhoz hozzárendel egy bejegyzést a BHT-ban -Ezeket a bejegyzéseket az IFAR legkisebb helyiértékű bitjei szerint indexeli - x tengely: -Esetünkben 4 bites léptet_regiszter -Legutóbbi 4 kiértékelés eredményét tartalmazza Az ugrástörténet tartalmazza: 0, ha soros folytatás volt 1, ha ugrott 2.szint: számláló - y tengely: -Ha a BHT 4 bites, akkor a számláló bejegyzéseinek száma 16 -A BHT táblázatban az adott elágazási utasítás ugrástörténetét címként felhasználva történik az egyes számláló-tábla bejegyzések címzése (pl 0110) - x tengely: -2 bites telített számláló -Értékei megegyeznek a lokális egyszintű előrejelzővel Működése: Becslés: -az aktuális elágazási utasításnak megfelelő BHT bejegyzésre ugrik; az adott BHT bejegyzésben szereplő bitmintának megfelelő számlálócímre ugrik abban a számlálóban, amely az adott bejegyzéshez tartozik. A számláló értékének megfelelően történik a becslés. - Aktualizálás: A becslés után, az elágazási feltétel kiértékelésekor karbantartja a • Léptetőregiszter tartalmát és a 6
• Számláló tartalmát Példa: Váltakozva, hol ugrik, hol nem ugrik, tehát a bitmintája 01010101010 … Lehetséges esetek 4 bites metszetben: - 0101, azaz 5 decimálisan: ezt mindig soros folytatás követi - 1010, azaz 10 decimálisan: ezt mindig ugrás követi A BHT tábla adott bejegyzéséhez tartozó számlálótábla lehetséges értékei: Összesen 2 bejegyzést használunk, a többi üres. 100%-os pontossággal becsül az első két lefutás után (ekkor áll be a soros folytatás). Szabályos minták esetén tökéletes a becslés. Értékelés: előny: a helyes becslés aránya 97,1% szabályos minták esetén. hátrány: viszonylag lassú a két szint miatt további hardver szükséges hozzá Pl.: Pentium Pro, Pentium MMX
7
