2. Függőségek Flashcards
Függőségek típusai
A függőségek akadályozzák a párhuzamos végrehajtás teljesítmény növelésének maximalizálását.
Típusai:
* Adatfüggőség
* Vezérlésfüggőség
* Erőforrásfüggőség
Adatfüggőség és csoportosítása
Adatfüggőségről beszélünk, ha egy utasítás végrehajtásához az előző utasítás eredményére van szükségünk.
Csoportosítása:
- jelleg szerint:
— utasítás szekvenciában jelenlevő (lineáris utasításfeldolgozás)
—— valós függőség (RAW – Read After Write)
——— műveleti adatfüggőség
——— lehívási adatfüggőség
—— álfüggőség
——— WAR (Write After Read)
——— WAW (Write After Write)
— ciklusban jelenlevő
- operandus típus szerint:
— regiszter
— memória
Műveleti adatfüggőség
Műveleti adatfüggőség akkor lép fel, amikor olyan regisztertartalmat szeretnénk kiolvasni, aminek a tartalma az előző műveletből még nem állt elő. Ilyen futószalagos párhuzamos végrehajtásnál fordulhat elő, ahol az utasítás lehívás (Fetch) és végrehajtás (Execute) átfedheti egymást. Ilyenkor a művelet nem folytatódhat, míg a függősége fel nem oldódik -> elakadás, várakozás következik be.
Megoldás: Egyik, hogy NOP utasítással tudjuk kezelni, ami viszont rontani fogja a teljesítményt.
Másik megoldás, hogy egy extra hardver segítségével az eredményt visszavezetjük a következő művelet forrásregiszterébe. Ezzel elérhető, hogy a második művelet kritikus t időpontjában az operandus már elérhető legyen.
Lehívási adatfüggőség
A lehívás menete DATA CACHE -> REGISTER -> Végrehajtó Egység
Előfordul, hogy a közvetett adatlekérés túl lassú és jó lenne a cacheből egyenesen a végrehajtó egységnek adni az adatot. Extra hardver segítségével megoldható, hogy a cacheből egyenesen a VE-be töltsön az adat, így megspórolunk 1 óraciklust.
WAR (Write After Read)
Az ál adatfüggőség teljesen megszüntethető.
Egyik típusa az olvasás utáni írás. Olyankor fordul elő, amikor olyan regiszterbe szeretnénk írni, amiből az előző művelet még olvasni szeretne az előző ottani értékkel. Ilyenkor ha I2 utasítás felülírja pl. az r1 regisztert, aminek az előző értéke kell I1-nek, akkor sérül a szekvenciális konzisztencia.
Megoldás átnevezési regiszterekkel. Célja, hogy hozzárendeljük az átnevezési regisztert az érintett architektúrális regiszterhez, és a hozzárendelést számontartjuk. Az átnevezési regiszterből csak akkor írjuk át az eredményt a cél regiszterbe, ha a sorban megelőző feladat befejeződött.
Tulajdonságaik:
- új, önálló regiszterek
- saját címtartománnyal rendelkezik
- programozó számára transzparens
- extra hardvernek számít
Ezáltal két féle regiszterkészletet különböztetünk meg:
- architektúrális regiszterkészlet: ezeket tudja használni a programozó
- átnevezési regiszterkészlet: vezérlés használja arra, hogy az ál adatfüggőségeket kiküszöbölje
WAW (Write After Write)
Olyankor fordul elő, amikor olyan regiszterbe szeretnénk írni, amibe az előző utasítás írása még nem fejeződött be, tehát két soronkövető utasításnak a célregisztere azonos, és az első utasítás feltehetően lassabb, mint a második. Ekkor előfordulhat, hogy az I2 lefutása végén a célregiszterben nem I2, hanem I1 eredménye kerül, mivel az lassabb volt, és felülírta a futása végén. Ez sérti a szekvenciális konzisztenciát.
Megoldása szintén átnevezési regiszterekkel.
A regiszter átnevezés egyébként történhet statikusan compiler segítségével, vagy dinamikusan átnevezési egységgel.
Ciklusbeli függőség
Probléma: egy ciklus mindig az eggyel korábbi iteráció eredményét használja, azaz az aktuális eredményhez szükség van az előző iteráció eredményére.
Kezelés: ez erős függőség, hardveresen nehezen feloldható. Megoldás az algoritmus áttervezése
Vezérlés függőség
Akkor léphet fel, ha feltétlen vagy feltételes elágazáshoz érünk.
Feltétlen elágazás
Lényege, hogy a feltétlen ugrást követő parancs néha előbb lefut, minthogy maga az ugrás végbemenjen. Ez veszélyteti az architektúrális regiszerek tartalmát.
Kezelés:
a) Utasítások átrendezésével
b) Ugrási buborékkal (statikus kezelés): a JMP utasítás mögé egy vagy több NOP utasítás kerül be, ezzel lassítva a futószalagot, míg elő nem áll az ugrási cím.
Feltételes elágazás
A feltételtől függ, hogy ugrás vagy soros folytatás következik. Kezelése dinamikusan történik végrehajtás során. Ez vezetett a spekulatív elágazáskezeléshez (branch prediction)
Erőforrás függőségek
Akkor lép fel, ha több utasítás akarja ugyanazt az erőforrást használni. Ilyenkor az egyiket várakoztatni kell. Erőforrások lehetnek például:
- regiszterek
- pufferek
- végrehajtó egységek
Példa: A logikai futószalagok különböző célokra dedikált végrehajtó egységekben vannak megvalósítva. Ilyen például a lebegőpontos vagy a fixpontos végrehajtó egység. Ha sok olyan utasítás van, ami lebegőpontos végrehajtást igényel, előfordulhat, hogy a lebegőpontos végrehajtó egységnél sorban állnak az utasítások, míg a fixpontos kihasználatlanul várakozik.
Kezelés: Úgy kell tervezni a processzort, hogy az erőforrás függőség ne okozzon szűk keresztmetszetet. Ezt az erőforrások többszörözésével érhető el. Fontos szempont a hatékonyság, 70-80%-os kihasználtság az általános.
Szekvenciális konzisztencia megőrzése
A programozó a programot szekvenciális logika szerint készíti el és a hardver vagy a compiler feladata, hogy az utasítások egymásutániságában a lehető legtöbb rendelkezésre álló párhuzamosságot ki tudja használni, miközben a logikai integritás megmarad.
Típusai:
- utasítás feldolgozás soros konzisztenciája
– utasítás végrehajtás soros konzisztenciája (processzor konzisztencia)
– memória hozzáférés soros konzisztenciája (memória konzisztencia)
- kivételkezelés (megszakítás) soros konzisztenciája
– pontatlan kivételkezelés (gyenge konzisztencia)
– pontos kivételkezelés (erős konzisztencia)
Processzor konzisztencia
Probléma: párhuzamos végrehajtás esetén előfordulhat, hogy I2 utasítás hamarabb lefut, mint I1.
I1 – DIV r3 r2 r1
I2 – ADD r5 r6 r7 – gyorsabb
I3 – JZ címke – ha az eredmény 0, akkor ugrás
Mivel a JZ utasítás mindig a legutoljára végzett utasítás eredményét használja fel a feltételes ugrás eldöntéséhez, ha I1 később végez, mint I2, előfordulhat, hogy a JZ a I1 eredménye alapján fog ugrani, ami hibás működéshez vezethet.
Megoldás: a hardvert úgy kell tervezni, hogy a feltételes utasítás csak az előtte lévő utasítás eredményét vegye figyelembe, ne azt, ami utoljára befejeződik. Például plusz flagek bevezetése.
Pontatlan kivételkezelés
Akkor lép fel, amikor egy művelet még nem végzett, de a soronkövetkező valamely művelet megszakítást eredményez. Ekkor a processzor elmenti a regiszterek állapotát egy verem regiszterbe. Miután kezeljük a kivételt, a veremből visszatöltődik a kontextus és folytatódik a végrehajtás. Visont a nem végzett művelet definiálatlan állapothoz vezethet és akár kékhaltált is okozhat.
Megoldása a pontos kivételkezelés.
Pontos kivételkezelés
Minden mai CPU a megszakítás kéréseket csakis az utasítások eredeti sorrendjében fogadja el. Az előző példában a CPU csak akkor fogadja el a megszakítási kérést, ha az előtte lévő utasítások befejeződtek és nem küldtek megszakításkérést.
Megvalósítás:
* átrendező puffer segítségével: a CPU a megszakítást csak akkor fogadja, ha az adott utasítást kiírjuk ebből az átrendező pufferből.
* Például: Intelnél ROB (Reorder Buffer)
* címkézés: az utasításokat sorszámokkal látjuk el és akkor fogadjuk el a megszakítást, ha egyetlen megelőző sorszámú sem kért.
