Vanredno izvršavanje

U računarstvu, vanredno izvršavanje (engl. out-of-order execution, OoOE ili OOE) je paradigma koja se koristi kod procesora visokih performansi da bi iskoristili instrukcijske cikluse koji bi, u suprotnom, bili neiskorišćeni zbog nekog određenog tipa kašnjenja. U ovoj paradigmi procesor izvršava instrukcije u redosledu koji određuje dostupnost ulaznih podataka, za razliku od njihovog originalnog redosleda u programu. Radeći tako, procesor može da izbegne da bude nezaposlen dok se podaci vraćaju za sledeću instrukciju u programu, umesto obrađivanjem sledećih instrukcija koje su u stanju da se izvrše odmah.

Istorija

Vanredno ozvršavanje je ograničena forma računanja toka podataka, koji je bio velika oblast istraživanja u računarskoj arhitekturi 70-ih godina i ranih 80-ih. Bitna akademska istraživanja u ovoj temu je vodio Jejl Pet (Yale Patt) i njegov HPSm simulator.^[1] List koji su Džejms E. Smit i A. R. Plezkun objavili 1985. dopunjava šemu opisujući kako određena ponašanja izuzetaka mogu biti održavana u mašinama sa vanrednim izvršavanjem.

Ubedljivo prva mašina koja koristi vanredno izvršavanje je bila CDC 6600 (1964), koja je koristila scoreboarding da bi rešila konflikte. Danas se u upotrebi, takav scoreboarding se smatra "rednim" izvršavanjem a ne vanrednim, pošto takve mašine odugovlače na prvom RAW konfliktu ("čitaj posle pisanja", engl. Read After Write). Striktno govoreći, takve mašine pokreću redno izvršavanje, iako mogu da upotpune vanredno izvršavanje.

Oko tri godine kasnije, IBM 360/91 (1966) je uveo Tomasulo algoritam, koji podržava potpuno vanredno izvršavanje.

IBM je, 1990., uveo prvi vanredni mikroprocesor, POWER1, iako je vanredno izvršavanje bilo ograničeno samo na instrukcije sa pokretnim zarezom.

Kroz 90-e godine, vanredno izvršavanje je postalo učestalije i bilo je istaknuto u sledećim mašinama: IBM/Motorola PowerPC 601 (1993), Fujitsu/HAL SPARC64 (1995), Intel Pentium Pro (1995), MIPS R10000 (1996), HP PA-8000 (1996), AMD K5 (1996) i DEC Alpha 21264 (1998). Značajni izizeci u ovom trendu su bile mašine: Sun UltraSPARC, HP/Intel Itanium, Transmeta Crusoe, Intel Atom, i IBM POWER6.

Logička kompleksnost šema vanrednog izvršavanja je bila razlog zbog koga ova tehnika nije dostigla mejnstrim mašine do sredine 90-ih godina. Mnogo "low-end" procesora namenjenih tržištima sa osetljivim cenama i danas ne koriste ovu paradigmu zbog velike silikonske oblasti koja je potrebna da se napravi ova klasa mašina. Mala potrošnja je još jedan cilj dizajna koji je teže postići sa OoOE dizajnom.

Osnovni koncept

Redni procesori

U ranijim procesorima, obrada instrukicja se obično izvršavala sledećim koracima:

Instrukcijsko hvatanje.
Ako su ulazni operandi dostupni (na primer u registrima), instrukcija se šalje prikladnoj funkcionalnoj jedinici Ako jedan ili više operanada nisu dostupni za vreme trenutnog ciklusa kloka (obično zato što ih hvata memorija u tom trenutku), procesor odugovlači dok ne postanu dostupni.
Intrukciju izvršava prikladna funkcionalna jedinica.
Funkcionalna jedinica piše rezultat nazad u registarski fajl.

Vanredni procesori

Ova nova paradigma se deli na obrađivanje instrukcija sledećim koracima:

Hvaltanje instrukcija
Instrukcija se prosleđuje instrukcijskom redu (engl. queue, još poznat kao i istrukcijski bafer.)
Instrukcija čeda u redu dok ulazni podaci ne postanu dostupni. Instrukciji se onda dozvoljava da napusti red.
Instrukcija se izdaje prikladnoj funkcionalnoj jedinici i izvršava je ta jedinica.
Rezultati se smeštaju u red.
Tek pošto sve starije instrukcije dobiju svoje rezutate nazad napisane u registarski fajl, onda se ovaj rezultat piše nazad u registarki fajl. Ovo se zove faza diplomiranja ili faza penzionisanja.

Ključ za koncept OoO obrade je da se dozvoli procesoru da može da izbegne klasu odugovlačenja do kojih dolazi kada je potreban podatak nedostupan. U šemi gore, OoO procesor izbegava odugovlačenja koja de dešavaju u koraku (2) rednog procesora kada instrukcija nije potpuno spremna da se obradi zbog nedostataka podataka.

OoO procesori popunjavaju ove proreze u vremenu sa drugim instrukcijama koje jesu spremne, i onda reorganizuju rezultat na kraju tako da bi izgledalo kao da su se instrukcije obradile najobičnije. Način na koji se instrukcije raspoređuju u originalnom kodu je poznat pod terminom redosled programa. U procesoru sa njima se barata u redosledu podataka, u redosledu u kome podaci tj. operandi, postaju dostupni u proserovoim registrima. Dosta kompleksna kola su potrebna da se konvertuje iz jednog redosleda u drugi i da se održi logički redosled izlaznih podaka. Čini se kao da sam procesor pokreće instrukcije u nasumičnom redosledu.

Beneficija OoO obarde raste kako se protočne obrada produbljuje i kako se brzina razlikuje između glavne memorije (ili keš memorije) i kako se procesor širi. Na modernim mašinama, procesor radi dosta brže nego memorija, tako da, za vreme koje redni procesor provede čekajući na podatke, on može da obradi veliki broj instrukcija.

Otpremanje i pitanje izolacije omogućavaju OoO ishod

Jednu od razlika koju pravi ova paradigma je stvaranje redova koji omogućavaju koraku prosleđivanja da bude odvojen od koraka ishoda i faze diplomiranja da bi bio odvojen od faze izvršavanja. Prvo ime za ovu paradigmu je bilo "odvojena arhitektura". U ranijim rednim procesorima ove faze su radile u protočnoj obradi u obliku "lokstepa".

Da bi izbegli netačne zavisnosti operanada, koji bi smanjili frekvenciju kada instrukcije mogu biti pokrenute van redosleda, koristi se tehnika zvana Preimenovanje registara. U ovoj šemi, postoji više fizičkih registara nego onih definisanih od strane arhitekture. Fizički registri su označeni tako da više verzija samih registara iste arhitekture može postojati u isto vreme.

Izvršavanje i pisanje izolacije omogućava programsko ponovno pokretanje

Red za rezultate je neophodan da bi se rešila pitanja kao što su loša predviđanja grana i izuzeci odnosno zamke. Rezlutovani red omogućava programu da se ponovo pokrene posle izuzetka, što zahteva da se instrukcija završi u programskom redosledu. Red omogućava rezulatima da se odbace zbog lošeg predviđanja na osnovu stariji grana instrukcija i izuzetaka koji su uzeti iz starijih instrukcija.

Sposobnost da se izda instrukcija proteklih grana, koja se još nije razrešila, se naziva spekulativno izvršavanje.

Mikroarhitektonski izbori

Da li su instrukcije odbačene na centralizovan red ili na više distribuiranih redova?

IBM PowerPC procesori koriste redove koji se distribuiraju na različite funkcionalne jedinice dok drugi OoO procesori koriste centralizovani red. IBM koristi termin stanice rezervacije za njihove distribuirane redove.

Da li postoji stvaran rezultat redova ili su se svi rezultati pišu direktno na registarski fajl? Za docniji, funkcijom za čekanje u redu rukuju registarske mape koje drže informacije preimenovanja registara za svaku instrukciju u letu.

Rani Intel OoO procesori koriste rezultujuće redove zvane baferi za promenu redosleda, dok mnogi kasniji OoO procesori koriste registarske mape.

Preciznije: Intel-ova P6 porodica mikroprocesora ima i bafere za promenu redosleda (engl. re-order buffers, ROB) i tabelu za preimenovanje registara (engl. register alias table, RAT). ROB je uglavnom motivisan oporavkom od lošeg predviđanja grana.

Intel-ova P6 porodica je među najranijim OoO procesorima, ali je zamenjena NetBurst arhitekturom. Godinama kasnije se dokazala kao ćorsokak zbog svoje dugačke protočne obrade, koja je podrazumevala mnogo više frekvencije rada. Materijali nisu bili u mogućnosti da se poklope sa dizajnerskim ambicionim metama kloka zbog problema sa toplotom. Kasniji dizajni, bazirani na NetBurst-u, pogotovo Tejas i Jayhawk su bili otkazani. Intel se vratio P6 dizajnu u obliku osnova Core-a, Core-a 2 i Nehalem mikroarhitekrure. Sandy Bridge, Ivy Bridge i Haswell mikroarhitekture predstavljaju polazak od tehnika promene redosleda koje je koristio P6 i zapošljavaju tehnike promene redosleda koje su koristili EV6 i P4 bez dugačke protočne obrade.^[2]

Vidi još

Reference

^ W. Hwu; Y. N. Patt (1986). HPSm, a high performance restricted data flow architecture having minimal functionality. ISCA '86 Proceedings of the 13th annual international symposium on Computer architecture. ACM. str. 297—306. ISBN 978-0-8186-0719-6. Pristupljeno 6. 12. 2013.
^ Kanter, David (25. 9. 2010). „Intel's Sandy Bridge Microarchitecture”.

Dodatna literatura

Smith, James E.; Pleszkun, Andrew R. (1985). „Implementation of precise interrupts in pipelined processors”. ACM Sigarch Computer Architecture News. 13 (3): 36—44. doi:10.1145/327070.327125.
Smith, J.E.; Pleszkun, A.R. (1988). „Implementing precise interrupts in pipelined processors”. IEEE Transactions on Computers. 37 (5): 562—573. doi:10.1109/12.4607.
Smith, James E.; Pleszkun, Andrew R. (1998). „Implementation of precise interrupts in pipelined processors”. 25 years of the international symposia on Computer architecture (Selected papers). str. 291–299. ISBN 1581130589. S2CID 6616701. doi:10.1145/285930.285988.

[1] W. Hwu; Y. N. Patt (1986). HPSm, a high performance restricted data flow architecture having minimal functionality. ISCA '86 Proceedings of the 13th annual international symposium on Computer architecture. ACM. str. 297—306. ISBN 978-0-8186-0719-6. Pristupljeno 6. 12. 2013.

[2] Kanter, David (25. 9. 2010). „Intel's Sandy Bridge Microarchitecture”.

[1]

[2]