Konflikti protočne obrade

U dizajnu procesora, konflikti su problemi sa protočnom obradom instrukcija u arhitekturi centralne procesorske jedinice kada se sledeća instrukcija ne može izvršiti u sledećem ciklusu kloka. Potencijalno, može doći do dobijanja netačnih rezultata izračunavanja. Postoje tri tipa konflikta:

• konflikti podataka
• strukturni konflikti
• konflikti kontrole (grananja)

Postoji nekoliko metoda koje se bave konfliktima, uključujući oduglovlačenja protočne obrade (engl. pipeline stalls), "penušanje" protočne obrade (engl. pipeline bubbling), prosleđivanje registara i, u slučaju vanrednog izvršavanja (engl. out-of-order execution, OOE'), scoreboarding metoda i Tomasulio algoritam.

Pozadina

Za više informacija pogledajte: Protočna obrada instrukcija

Instrukcije u procesoru sa protočnom obradom se izvršavaju u nekoliko faza tako da se, u bilo kom trenutku, nekoliko instrukcija obrađuju u različitim fazama protočne obrade (npr. fetch (donesi) i execute (izvrši)). Postoji više različitih arhitektura za protočnu obradu instrukcija i instrukcije mogu biti vanredne (OOE). Do konflikta dolazi kada dve ili više ovih instrukcija (verovatno neka OOE) dođu u sukob.

Tipovi

Konflikti podataka

Do konflikta podataka dolazi kada instrukcija koja izlaže zavisnost podatka modifikuje podatak u drugoj fazi protočne obrade. Ignorisanje potencijalnih konflikta može dovesti do stanja trke (engl. race conditions). Postoje tri simulacije u kojima može doći do konflikta podataka:

1. Čitaj posle pisanja (engl. read after write, RAW), prava zavisnost
2. Piši posle čitanja (engl. write after read, WAR), anti-zavisnost
3. Piši posle pisanja (engl. write after write, WAW), zavisnost izlaza

Razmatramo dve instrukcije: i1 i i2, gde se i1 dešava pre i2 po redosledu programa.

Čitaj posle pisanja (RAW)

(i2 pokušava da čita izvor pre nego što i1 zapiše na podatku) "Čitaj posle pisanja" konflikt se odnosi na situaciju gde jedna instrukcija pokušava da pristupi rezultatu koji se još uvek nije ili učitao ili izračunao. Ovo se može dogoditi zato što, iako se jedna instrukcija izvršila posle prethodne instrukcije, prethodna instrukcija se nije još uvek potpuno obradila u procesu protočne obrade.

Primer

i1. R2 <- R1 + R3
i2. R4 <- R2 + R3

Prva instrukcija računa vrednost koja se čuva u registru R2, a druga hoće da iskoristi ovu vrednost da izračuna rezultat za registar R4. Međutim, kod protočne obrade, kada se donose (fetch) operandi za drugu operaciju, rezultati iz prve neće još uvek biti sačuvani čime imamo zavisnost podataka.

Kažemo da postoji zavisnost podataka sa instrukcijom i2, jer ona zavisi od toga da li je i1 potpuno završena.

Piši posle čitanja (WAR)

(i2 pokušava da piše na nekoj lokaciji pre nego što je i1 pročita) "Piši posle čitanja" konflikt predstavlja problem sa istovremenim izvršavanjem.

Primer

i1. R4 <- R1 + R5
i2. R5 <- R1 + R2

Ako se nađemo u situaciji gde postoji šansa da se i2 završi pre i1 (npr. kod istovremenog izvršavanja), moramo se osigurati da se sačuva rezultat registra R5 pre nego što i1 dobije šansu da preuzme operande.

Piši posle pisanja (WAW)

(i2 pokušava da napiše operand pre nego što ga je napisao i1) Do "piši posle pisanja" konflikta može doći u okruženju sa istovremenim izvršavanjem.

Primer

i1. R2 <- R4 + R7
i2. R2 <- R1 + R3

Moramo odložiti WB (Write Back) i2 dok ne dođe do izvršavanja tt>i1.

Strukturni konflikti

Do strukturnih konflikata dolazi kada je dvema ili više instrukcija, u isto vreme, potreban deo procesorovog hardvera. Kanonski primer bi bila jedna jedinica memorije kojoj se pristupa i u fazi donošenja (fetch), gde se iz memorije traži neka instrukcija, i u fazi kada se podatak piše i/ili čita sa memorije. Obično ovo može rešiti odvajanjem komponenata u ortogonalne jedinice (kao što su odvojeni keševi) ili "penušanjem" protočne obrade (engl. bubbling the pipeline).

Konflikti kontrole (grananja)

Konflikti grananja (još poznati kao i konflikti kontrole) se dešavaju, kao što naziv kaže, kada imamo grananja (odnosno grane). Na mnogim arhitekturama protočne obrade instrukcija, procesor neće znati ishod grane kada je potrebno da se unese nova instrukcija u protočnu obradu (obično u fazi donošenja (fetch)).

Eleminisanje konflikta

Opšti slučaj

"Penušanje" protočne obrade

Glavni članak: Bubble (computing)

"Penušanje" protočne obrade (poznato i kao prekid protočne obrade ili oduglovlačenje protočne obrade) je metod za sprečavanje strukturnih konflikta, konflikta podataka i konflikta grananja. Kako se donose instrukcije (fetch), kontrolna logika određuje do kog konflikta može doći ili ne. Kontrolna logika onda ubacuje NOP-ove (engl. no operations) u protočnu obradu. Tako, pre izvršenja sledeće instrukcije (koja bi izazvala konflikt), prethodna instrukcija će imatii dovoljno vremena da se završi i time spreči konflikt. Ako je broj NOP-ova jednak broju faza protočne obrade, procesor će biti očišćen od svih instrukcija koje bi mogle da nastave sa radom bez konflikta. Ovo se naziva "ispiranje protočne obrade" (engl. flushing the pipeline). Sve forme odugovlačenja uvode kašnjenje pre nego što procesor može da nastavi sa izvršavanjem.

Konflikti podataka

Postoji nekoliko glavnih rešenja i algoritama koji se koriste da se reše konflikti podataka:

• dodavanje "mehurića" protočne obrade kad god se naiđe na "čitaj posle pisanja" zavisnost, koja garantuje povećanje kašnjenja
• iskorišćavanje vanrednog izvršavanja (OOE) da bi se, potencijalno, sprečila potreba za "mehurićima" protočne obrade
• iskorišćavanje prosleđivanja registara radi korišćenja podataka iz kasnijih faza protočne obrade

U slučaju OOE, algoritam koji se koristi bi mogao biti:

• scoreboarding, u čijem slučaju će "mehurić" protočne obrade biti potreban samo tamo gde nema funkcionalne jedinice
• Tomasulio algoritam, koji iskorišćava preimenovanje registara i time dozvoljavajući kontinualno izdavanje instrukcija

Možemo prebaciti zadatak uklanjanja zavisnosti podataka na kompajler, koji onda može da popuni prikladan broj NOP instrukcija između zavisnih instrukcija da bi osigurao tačnu operaciju ili reogranizovao redosled instrukcija gde je to moguće.

Prosleđivanje registara

Prosleđivanje uključuje preusmeravanje izlaznih podataka u prethodnu fazu protočne obrade. Prosleđivanje se implementira preusmeravanjem izlaznih podataka instrukcije u prethodne faze protočne obrade čim izlazni podaci te instrukcije postanu dostupni.

Primer

Beleška: U sledećem primeru, izračunate vrednosti su označene boldovano dok brojevi registara nisu.

Na primer, recimo da želimo da upišemo vrednost 3 u registar 1 (koji već sadrži vrednost 6) i da onda dodamo 7 registru 1 i uskladištimo rezultat u registar 2:

Instrukcija 0: Registar 1 = 6

Instrukcija 1: Registar 1 = 3

Instrukcija 2: Registar 2 = Registar 1 + 7 = 10

Posle izvršavanja, registar 2 bi trebalo da sadrži vrednost 10. Međutim, ako istrukcija 1 ne napusti protočnu obradu u potpunosti pre nego što instrukcija 2 počne izvršavanje, onda registar 1 neće sadržati vrednost 3 kada instrukcija 2 obavi svoju funkciju sabiranja. Ovako, instrukcija 2 dodaje 7 na staru vrednost registra 1 (6) tako da će sada registar 2 sadržati vrednost 13:

Instrukcija 0: Registar 1 = 6

Instrukcija 2: Registar 2 = Registar 1 + 7 = 13

Instrukcija 1: Registar 1 = 3

Do ove greške dolazi zato što instrukcija 2 čita registar 1 pre nego što je instrukcija 1 sačuvala rezultat svoje operacije pisanja u registar 1. Kada instrukcija 2 pročita sadržaj registra 1, registar 1 će i dalje sadržati 6, a ne 3.

Prosleđivanje (opisano dole) pomaže ispravljanju ovakvih grešaka jer izlazni podatak instrukcije 1 (koji je 3) može koristiti sledeća instrukcija pre nego što se vrednost 3 sačuva u registar 1.

Prosleđivanje koje se primenjuje u našem primeru znači da mi ne želimo da čekamo na skladištenje izlaznih podataka instrukcije 1 u registru 1 (u ovom primeru, izlazni podatak je 3) pre nego što taj izlazni podatak postane dostupan sledećoj instrukciji (u ovom slučaju, instruciji 2). Dobijeni efekat je da instrukcija 2 koristi tačnu (poslednju) vrednost registra 1, odnosno, skladištenje je obavljeno neposredno i nije protočno obrađeno.

Sa uključenim preusmeravanjem, faza za dekodovanje/izvršavanje instrukcija (engl. Instruction Decode/Execution, ID/EX) sada ima dva ulazna podatka: vrednost učitanu iz registra (u ovom primeru vrenost je 6) i novu vrednost registra 1 (u ovom primeru vrednost je 3), koji je prosleđen sa sledeće faze izvršavanja/memorijskog pristupa instrukcija. Dodatna kontrolna logika se koristi da odredi koji ulazni podatak se koristi.

Konflikti kontrole (grananja)

Da bi se izbegli konflikti grananja arhitekture mogu:

• ubaciti "mehurić" protočne obrade (više o tome iznad), što garantuje povećanje kašnjenja
• koristiti predikciju grana(nja) i u suštini napraviti nagađanja o tome koje instrukcije da ubaci. U tom slučaju bi "mehurić" protočne obrade bio potreban samo u slučaju loše predikcije.

U slučaju da grana izazove "mehurić" protočne obrade pošto su nekorektne instrukcije ušle u protočnu obradu, mora se voditi računa o sprečavanju da bilo kakva pogrešno učitana instrukcija ima efekat na stanje procesora (isključujući uzaludnu obradu instrukcija pre nego što je otkriveno da su učitane pogrešne).

Vidi još

• Paralelizam na nivou naredbe
• Zavisnost podataka

Literatura

• Patterson, David; Hennessy, John (2009). Computer Organization and Design (4th izd.). Morgan Kaufmann. ISBN 978-0-12-374493-7. 
• Patterson, David; Hennessy, John (2011). Computer Architecture: A Quantitative Approach (5th izd.). Morgan Kaufmann. ISBN 978-0-12-383872-8. 
• John P. Shen and Mikko H. Lipasti, Modern Processor Design: Fundamentals of Superscalar Processors. 2004. ISBN 978-0-07-057064-1.