4. Az adat-, vezérlés és az erőforrás- függőségek Flashcards
Függőségek csoportosítása
Adatfüggőségek: Egymást követő utasítások ugyanazt az adatot használják.
Vezérlési függőség: feltétlen vagy feltételes ugró utasítások esetén
Erőforrás függőség: utasítások ugyanazt az erőforrást (VE) akarják használni
Adatfüggőség
Problémafelvetés:
1.: x * y => z
2.: z * 2 => z » a 2. utasítás az 1. utasíáts eredményét akarja használni » párhuzamosan problémás
Alapfeltételek: 1 utasítás = 4 rész (F – D – E – W/B) (Fetch – Decoder – Executing – eredmény visszaírása)
Valós függőségek – RAW
RAW = Read After Write
A hatásuk csak mérsékelhető, nem kiküszöbölhetőek
Műveleti adatfüggőség
Probléma:
I1: MUL r3, r2, r1 (vagyis r3 « r2*r1)
I2: SHL r3
Mivel r3-ban még nincs kész az eredmény akkor, amikor az I2 már használni szeretné, ezért NOP utasításokkal várakoztatjuk az I2-t.
A NOP-ok használata csökkenti a hatékonyságot. Ettől nem lehet megszabadulni, csak csökkenteni a káros hatást.
kép4
Műveleti adatfüggőség megoldása
Megoldás: FWD
Operandus előrehozással. Ez extra hardvert jelent!
A CPU érzékeli, hogy szükség lesz még az adatra, ezért W/B-kor nem csak a regiszterbe mentjük az eredményt, hanem visszatöltjük azt az ALU-ba.
Behívási adatfüggőség
A CPU a gyorsítótárból a regisztertárba szállítja az adatot. Érzékeli, hogy neki is szüksége lesz rá.
Megoldás: szintén operandus előlehívás
kép6
Álfüggőségek
Az állfüggőségek feloldhatóak.
- WAR (ritka) Write After Read
- WAW (gyakrabb) Write After Write
WAR (ritka) Write After Read
Probléma:
I1: MUL r3 r2 r1
I2: ADD r2 r4 r5
A MUL sokkal lassabb, mint az ADD, úgyhogy az utóbbi megelőzheti az előbbit párhuzamos feldolgozásnál! Lehet, hogy az r4 és r5 összegével szorzunk, amikor ez nem kívánt működés lenne.
Megoldás: Regiszter átnevezés: r2 » r27. Ez egy átmeneti regiszter önálló címtartománnyal.
I1: MUL r3 r2 r1
I2: ADD r27 r4 r5
Ez is extra hardvert jelent: átnevezési regiszterkészlet.
WAW (gyakrabb) Write After Write
Probléma:
I1: MUL r3 r2 r1
I2: ADD r3 r4 r5
A MUL lassúsága miatt lehet, hogy a két utasítás lefutása után nem r4 + r5 lesz r3-ban hanem a később lefutó MUL utasítás eredménye.
Megoldás: Itt is átnevezési regiszterkészlet beépítése oldja meg a függőséget.
I1: MUL r3 r2 r1
I2: ADD r31 r4 r5
Ciklusbeli függőségek
Probléma:
do i=2, n
x(i) := a(i) * x(i - 1) + b(i) //Valós és Erős függőség !
end do
Ha ezt párhuzamosan hajtjuk végre akkor nem biztos, hogy már ki van számolva az előző elem, pedig mi azzal akarunk számolni.
Megoldás: Át kell alakítani az algoritmust!
Vezérlés függőségek
- Feltétlen vezérlés átadás
- Feltételes vezérlés átadás
Feltétlen vezérlés átadás
Probléma: (Valós) I1 MUL ... I2 JMP címke I3 SUB ... ... címke SHL
Mivel feltétlen ugrás van, a SUB-nak nem szabad végrehajtódnia, rögtön az SHL-nek kell jönnie. » Feleslegesen van lehívva a SUB, emiatt veszélyeztetve van a regiszterkezelés » biztosítani kell, hogy a JMP utáni utasítás ne hajtódjon végre.
Feltétlen vezérlés átadás statikus megoldása
A CPU érzékeli, hogy JMP utasítás következik, majd berak annyi NOP utasítást, amennyire szükség van ahhzo, hogy a vezérlésátadás kiértékelődjön. Ezt hívják ugrási buboréknak. NOP-ok száma: n-1, ahol n a futószalag fokozatok száma.
Lényege: fölösleges utasításokat végzünk, de a regiszter tartalmakat nem veszélyeztetjük, azonban lassú megoldás.
Feltétlen vezérlés átadás dinamikus megoldása
Lényege: a fordító megpróbál változtatni az utasítások sorrendjén. A JMP előttről áttesz egy vagy több adatmanipuláló utasítást a JMP mögé.
kép7
A feltöltés valószínűsége 2 fokozatú futószalagnál ~85%, 3 fokozatúnál ~50%… Ez csak a korai CPU- kban volt használatos.
Feltételes vezérlés átadás
Kezelése csak dinamikusan! (Elág. becsl. eljárások: Branch Prediction és Spekulatív elágazás kezelés)
