- Datove zavislosti (Data Dependences)
Datova zavislost znaci, ze instrukcia j je datovo zavisla na i ak instrukcia j vyuziva vysledok instrukcie i
- Menne zavislosti (Name Dependences alebo False Data Dependences)
Instrukcia j je menne zavisla na instrukcii i ak j vyuziva rovnake miesto pre ulozenie vysledkov, z ktoreho i cita, alebo do neho zapisuje.
- Riadiace zavislosti (Control Dependences)
Instrukcia j je zavisla na i ak j zavisi na vysledku i. (napr. skok)
Pri prudovom spracovani vznikaju v zasade 3 typy hazardov
- Datove hazardy
Datovy hazard predstavuje narusenie datovych alebo jmennych zavislosti. Sem patri - Read After Write - skutocna datova zavislost. Instr. j chce citat skor, ako i zapise novu hodnotu.
- Write After Read - protizavislost medzi i a j. Instr. j chce zapisovat na miesto, z ktoreho i bude citat.
- Write After Write - vystupna zavislost. Instr. j chce zapisovat na miesto, kam i este nezapisala novu hodnotu.
Existencia hazardu zavisi na vzdialenost medzi i a j vzhladom k latenicii pipeline (casovej odozvy pipeline alebo opozdenie pipeline). Nie kazda zavislost vsak musi viest k hazardom. Ak su instrukcie dost daleko od seba, tak k hazardu dosjt nemusi, hoci zavislost tam stale existuje (ta tam nakoniec bude vzdy). Medzi takymito instrukciami sa mozu nachadzat nezavisle instrukcie, vlozene prekladacom.
- Riadiace hazardy
Riadiaci hazard znaci narusenie riadiacich zavislosti
- Strukturne hazardy
Je dosledkom neuplnej replikacie prostriedkov na pipeline. Napr. kolizia zdielanych prostriedkov, ktorymi su pamate, porty reg. poli, funkcne jednotky.
Su dve techniky, ktorymi mozme riesit hazardy na pipeline. Bud pomocou pozastavenie, alebo bez neho.
Riesenie hazardov pomocou pozastavenia
Na obrazku vpravo je RAW hazard, kedy 2. instrukcia cita hodnotu R1 pred tym, ako 1. instrukcia zapisala novu hodnotu R1. Takyto druh hazardu sa da riesit tak, ze medzi dve instrukcie vlozi prazdna instrukcia - stall - tak, aby 2. instrukcia zacala citat az po WB faze 1. instrukcie.
SUB teda caka s ID fazou az na dokoncenie WB fazy .
Situacia je trosku komplikovanejsia v pripade riadiaceho hazardu. Problem je v tom, ze ak vlozime do programu instrukciu skoku, tak ta sa musi najprv vyhodnotit, az potom by sa malo zacat so spracovanim dalsich instrukcii. Riesenie pozastavenim znamena, ze musime vlozit tolko stallov, kolko je doba vykonavania instrukcie skoku.
Strukturne hazardy riesime tiez pozastavenim. Jedna sa o problem napr. pri zdielani prostriedkov. Napr. 2 instrukcie chcu zapisovat v tom istom case a je len jedna zbernica a pod. Vlozenim pozastaveni sa nam zmeni rovnica pre vypocet CPI. Musime do nej zapocitat hodnotu stalls per instructionm (nepocitame s pozastavenim strukturnych hazardov).
CPIreal = CPIideal + SPI
CPI idealnej pipeline je 1 a SPI je pomer instrukcie skoku * 3 k celkovemu programu. Znamena to, ze ak mame 13% instrukcii skoku a ta trva 3 takty, tak 0,13*3 je SPI. Pri rieseni s pozastavovanim dojde k stallu pri skoku vzdy.
Celkove zrychlenie bude S = (Tclk_no_pipe / Tclk_pipe) * 1/(1+SPI).
Este pred tym, ako sa skusime zbavit SPI (kolko to len pojde), tak sa pozrieme na to, ako je pozastavenie implementovane.
V cervenej casti nastane stall. Budeme recyklovat vsetky stage pred stallom, az pokial sa nam "neuvolni cesta". Akonahle bude mozne pokracovat, tak pokracujeme cez pipeline.
Riesenie hazardov na pipeline bez pozastavenia - Forwarding
Toto riesenie je postavene na principe preposielania medzi WB a EX fazou. Pocas vykonavania jednej instrukcie dospejeme k vysledku po EX faze a vo WB faze dokazeme preposlat vysledok do EX fazy toho spracovanie, ktore tento vysledok pozaduje (datova zavislost).
Ked je 1. instrukcia vo faze WB/EX, tak dalsia je uz spracovavana. Aby sa forwarding mohol uskutocnit, tak sme museli spravit iste HW upravy. Na zbernicu A a B z registrov do ALU polozime MUXy. Ten, na zbernici B bude prepojeny s vystupnym MUXom vo faze WB. Odtial dokaze prijat data a takto vyzera forwarding WB/EX. Na obrazku je mozne vidiet aj forwarding medzi MEM a EX. Pre tento prenost vezmeme data zo zbernice po tom, ako na nu vysledok vystavi ALU. Z implementacie vidno, ze spat v case posielat nedokazeme. Tymto sposobom mozme riesit datove hazardy.
Riadiace hazardy osetrime trosku inak.U riadiacich hazardov je problem v tom, ze podmienka sa vyhodnoti vo faze EX a PC je zmenene v stupni MEM. V tej chvili uz ale mame dalsie 3 instrukcie v pipeline. Forwarding tu asi fungovat nebude, pretoze nemame co forwardovat. Tento problem mozme riesit
- vyplachnutim pipeline
- vyhodnotenim podmienky pred skokom
- skorsim vypoctom cielovej adresy a skorsou zmenou PC
Vyplachnutie znamena, ze po vyhodnoteni podmienky skoku sa vykonaju dalsie instrukcie v sekvencnom poradi (teda, ako by sme neskocili). V pripade, ze podmienka bude vyhodnotena ako true, tak tieto instrukcie budu vyplachnute (flushed). V nasom pripade by to boli tri instrukcie, pretoze nas skok nas zdrzi o tri instrukcie. Takymto sposobom sa nam podari znizit SPI v zavislosti na uskutocnenych skokoch (cim menej tym lepsie).
SPI = frekvencia skokov * frekvencia uskutocnenych * branch penalty.
Ak bude skok znamenat zdrzanie 3 instrukcie pri uskutocnenom skoku, tak SPI bude SPI = 0,13 * 0,67 * 3 = 0,26. 0,13 je z prikladu pred tym a 0,67 je vymyslene. V tomto pripade sme dosiahli zlepsenie voci prikladu so stallom. V najhorsom pripade (100% skokov skoci), je SPI = 0,39.
Ak skusime vyhodnotit podmienku este pred skokom, tak musime spravit HW upravy. Prideme tak ale o moznost forwardingu do EX stupna. Tym sice zlepsime SPI vzniknute pri skoku, ale nevyriesime datove hazardy. Do systemu sme pridali este jednu scitacku, aby sme nemuseli vyuzivat ALU. Zo zbernic z registra do ALU sme vyviedli data do Condition Evaluation Logic systemu (? komparator ?) a ciselny operand sme prepojili s pridanou scitackou, kde pripocitam PC + 4 (dalsia adresa). Teraz mozme zvysit PC. Aj v tomto pripade ale musime flushnut jednu instrukciu za skokom v pripade, ze skocime.
Dalsou moznostou je oneskoreny skok. V predoslom rieseni sme museli jednu instrukciu flushnut, ak doslo ku skoku. Moznostou, ktora nam este zostava, je za skok, ktory moze/nemusi byt uskutocneny vlozit instrukciu, ktora ma byt vzdy vykonana. Po vykonani tejto instrukcie dojde/nedojde ku skoku. Takto dokazeme zredukovat branch penalty na 0. O instrukcii, ktora je za skokom, vravime, ze je v delay slote. Skok nesmie zavisiet na instrukcii v delay slote.
Do delay slotu mozme dat
- instrukciu spred skoku
- instrukciu z ciela skoku
- instrukciu zo sekv. pokracovania
Posledne dve riesenia su legalne len a len ak instrukcie v delay slote mozu byt bezpecne vykonane aj ked skok povedie naopak, ako je ocakavane.
Instrukcia v delay skoku nesmie sposobit vynimku, ak je uskutocnena v ceste, kde povodne nemala byt uskutocnena (Virtual memory protection fault)
Pokial je instrukcia zrusena po uspesnom skoku, tak hovorime o rusiacom skoku, inak o konvencnom skoku. Ak je vykonana vzdy, tak o oneskorenom skoku.
