Preimenovanje registara

U arhitekturi računara preimenovanje registara se odnositi na tehniku koja pomaže pri izbegavanju nepotrebnih serijalizacija programskih operacija, koje se događaju usled reupotrebe registara.

Definicija problema

U registarskoj mašini, programi su sastavljeni od instrukcija koje operišu nad vrednostima. Instrukcije moraju da imenuju vrednosti kako bi ih razlikovali jedne od drugih. Tipična instrukcija bi mogla da glasi: saberi X i Y i smesti rezultat u Z. U ovoj intrukciji X, Y i Z su imena skladišnih lokacija.

Kako bi sistem enkodiranja instrukcija postajao kompaktan, mnogi procesorski skupovi instrukcija imaju mali skup specijalnih lokacija koje se mogu direktno imenovati. Na primer, skup instrukcija x86 arhitekture ima 8 celobrojnih registara, x86-64 ima 16, mnogi RISC procesori imaju 32 i IA-64 ima 128. U malim procesorima, imena ovih lokacija odgovaraju elementima registarskog fajla.

Različite instrukcije mogu zahtevati različito vreme izvršavanja (tj. CISC arhitektura). Na primer, procesor može biti u stanju da izvrši stotine instrukcija dok je u toku jedan unos iz glavne memorije. Kraće instrukcije, koje se izvršavaju dok je unos učitan, će se prve izvršiti, tako da se instrukcije izvršavaju vanredno. Vanredno izvršavanje se koristi u većini novijih procesora visokih performanski kako bi se dobilo na brzini,

Posmatrajmo ovaj deo koda koji se vanredno izvršava na procesoru:

1. R1 = M[1024]

2. R1 = R1 + 2

3. M[1032] = R1

4. R1 = M[2048]

5. R1 = R1 + 4

6. M[2056] = R1

Instrukcije 4, 5 i 6 su zavisne od instrukcija 1, 2 i 3, ali procesor ne može da završi 4. sve dok se 3. ne izvrši, zato što bi 3. onda dala pogrešan rezultat.

Možemo izbaciti ovo ograničenje tako što bi izmenili imena nekih registara

1. R1 = M[1024]	4. R2 = M[2048]
2. R1 = R1 + 2	5. R2 = R2 + 4
3. M[1032] = R1	6. M[2056] = R2

Sada instrukcije 4, 5 i 6 mogu da budu izvršene paralelno sa instrukcijama 1, 2 i 3, tako da se program brže izvršava.

Kada je to moguće, kompajler primećuje takvu instrukciju i pokušao bi da je dodeli drugom registru. Međutim, postoji konačan broj registarskih imena koja se mogu koristiti u asemblerskom kodu. Mnogi procesori visokih performansi imaju više fizičkih registara koji se mogu imenovati u skupu instrukcija, tako da oni preimenuju hardverske registre radi dostizanja dodatnog paralelizma.

Konflikti podataka

Glavni članak: Konflikti podataka

Kada više od jedne instrukcije referencira neku lokaciju za operand, bilo pri učitavanju, bilo pri ispisu, izvršavanje te instrukcije može dovesti do tri tipa konflikta:

"Čitaj posle pisanja" (RAW)

Čitanje iz registra ili memorijske lokacije mora da vrati vrednost koja je tamo upisana prilikom poslednjeg upisa u programskom redosledu. Ovo se naziva "suštinska zavisnost" ili "zavinost toka" i zahteva da se intrukcije izvrše u programskom redosledu.

"Piši posle pisanja" (WAW)

Uzastopni upis u određeni registar ili memorijsku lokaciju moraju rezultovati time da ta lokacija sadrži sadržaj drugog upisa. Ovo može da se reši poništavanjem prvog upisa ako je potrebno. WAW zavisnoti su još poznate i kao "zavisnosti izlaznih podataka".

"Piši posle čitanja" (WAR)

Čitanje iz registra ili memorijske lokacije mora da vradi poslednju vrednost upisanu u tu lokaciju, a ne onu upisanu nakon čitanja. Ovo je vrsta lažne zavisnosti koja može da se reši preimenovanjem. WAR zavisnosti su još poznate i kao "anti-zavisnosti".

Umesto odlaganja ispisa dok se svi upisi ne izvrše, dve kopije lokacije se mogu održavati, stara vrednost i nova vrednost. Upisi koji prethode, u programskom poretku, ispisu nove vrednosti, mogu dobiti staru vrednost, čak i ako drugi upisi koji slede nakom ispisa dobijaju novu vrednost. Lažna zavisnost se razbija i dodatne prilike za vanredno izvršavanje se pojavljuju. Kada se zadovolje svi upisi koji traže staru vrednost, ona može biti odbačena. Ovo je ključan koncept iza preimenovanja registara.

Sve što je učitano i ispisano može biti preimenovano. Dok se najviše diskutuju registri opšte namene, flegovi i statusni registri ili čak individualni statusni bitovi se takođe često preimenuju.

Memorijske lokacija se mogu takođe preimenovati iako se to ne radi često. Transmeta Cruso procesorov bafer za skladištenje predstavlja formu preimenovanja memorije.

Ako se programi uzdršavaju od neposrednog ponovnog korišćenja registara, preimenovanje registara neće biti potrebno. Neki skupovi instrukcija, kao kod IA-64, specifikuju veoma velike brojeve registara specijalno iz ovog razloga. Međutim, postoje ograničenja ovom pristupu:

• Kompajleru je veoma teško da izbegne ponovno korišćenje registara bez velikog povećanja koda. Na primer, u petljama, su uzastopne iteracije mogu da koriste različite registre, što zahteva pravljenje kopija koda u procesu koji se naziva "odvijanje petlje".
• Veliki broj registara zahteva puno bitova da bi odredio te registre, što čini kod većim.
• Dosta skupova instrukcija određuju manji broj registara i ranije i kasnije se ti brojevi ne mogu promeniti.

Povećanja koda su bitna zato što, kada je kod veći onda keš instrukcija često promašuje i procesor odugovlači dok čeka nove instrukcije.

Arhitektonski registri ili fizički registri

Programski jezici mašina specifikuju pisanja i čitanja na ograničen skup registara koji određuje skup instrukcija (engl instruction set architecture, ISA). Na primer, Alpha ISA određuje 32 celobrojnih registara, svaki širok po 64 bita i određuje 32 registra sa pokretnim zarezom, svaki po 64 bita širok. Ovo su arhitektonski registri. Programi pisani za procesore koji koriste Alpha skup instrukcija mogu odrediti operacije čitanja i pisanja tih 64 registara. Ako programer zaustavi program debagovanjem, mogu se posmatrati sadržaj ovih registara da bi se odredilo napredovanje mašine.

Jedan određeni procesor koji implementira ovaj ISA, Alpha 21264, ima 80 celobrojnih i 72 sa pokretnim zarezom fizičkih registara. Na Alpha 21264 čipu postoji 80 fizički odvojenih lokacija na kojima se može skladištiti rezultat celobrojnih operacija i 72 lokacije koje mogu sadržati rezultate operacija sa pokretnim zarezom. U stvari, postoji i više lokacija od toga, ali se te lokacije ne povezuju sa registrima sa operacijama za preimenovanje.

Ispod su opisana dva načina za preimenovanje registara, karakterizovani kolima koji nose podatke spremne za jedinicu izvršavanja.

U svim šemama za preimenovanje, mašine konvertuju arhitektonske registre (sa kijima se radi u strimu instrukcija) u oznake. Arhitektonski registri mogu biti određeni sa 3 do 5 bitova, dok su oznake obično dužine 6 do 8 bitova. Fajl koji se preimenuje mora imati port za čitanje za svaki ulazni podataka za svaku instrukciju koja se preimenuje u svakom ciklusu. Mora imati i port za pisanje za svaki izlazni podatak svake instrukcije koja se preimenuje u svakom ciklusu. Zato što veličina registarskog fajla obično raste kao kvadrat broja portova, fajl preimenovanja je obično fizički velik i zahteva značajnu količinu energije.

U načinu na koji se registarski fajl indeksira po oznaci, postoji jedan veliki registarski fajl za vrednosti podataka koji sadrži jedan registar za svaku oznaku. Na primer, ako mašina ima 80 fizičkih registara, onda bi koristila sedmobitne tagove. Od svih mogućih vrednosti za oznake, njih 48 se ne koristi u ovom slučaju.

U ovom načinu, kada se neka instrukcija pozove, oznake izvornih registara se šalju na fizički registarski fajl, gde vrednosti odgovaraju onim oznakama koji su pročitani i poslati na jedinicu za izvršavanje.

U nalinu sa rezervacionom stanicom, postoji mnogo malih asocijativnih registarskih fajlova, obično jedan na ulazu svake jedinice za izvršavanje. Svaki operand svake instrukcije u nekom redu poziva ima mesto za vrednost u nekom od ovih registarskih fajlova.

U ovom načinu, kada neka se instrukcija pozove, ulazni podaci registarskog fajla odgovaraju ulazima reda poziva i prosleđuju se jedinici za izvršavanje.

Arhitektonski registarski fajl ili registarski fajl penzionisanja (engl. Retirement Register File, RRF)

Posvećeno registarsko stanje mašine. Logički registarski broj indeksira RAM. Tipično upisan kada se rezultati penzionišu iz bafera za promenu redosleda.

Budući fajl

Najspekulativnije stanje mašine. Logički broj registara indeksira RAM.

Aktivan registarski fajl

termin za "budući fajl" Intel P6 grupa.

Bafer istorije: Uglavnom se koristi u kombinaciji sa budućim fajlom. Sadrži stare vrednosti registara preko kojih je pisano. Ako je proizvođač i dalje u letu, ovaj bafer može indeksirati RAM. Pošto loša predikcija grananja mora da koristi rezultate iz ovog bafera, ili se oni kopiraju, ili se traženje budućeg fajla zabranjuje i bafer je CAM indeksiran od stranje broja registara.

Bafer za promenu redosleda (engl. Reorder Buffer, ROB)

struktura koja je sekvencijalno indeksirana na bazi "po operaciji" za instrukcije u letu. Razlikuje se od bafera istorije zato što ovaj bafer obično dolazi posle budućeg fajla (ako ovaj postoji) i pr earhitektonskog registarskog fajla.

Bafer za promenu redosleda dolazi u verzijama bez podataka i sa podacima.

U Vilametovom (Willamette) ROB-u, ulazni podaci ukazuju na registre u fizičkom registarskom fajlu (engl physical register file, PRF) i takođe sadrže drugi mehanizam za rezervisano čuvanje. Ovo je takođe bio prvi vanredni dizajn koji je uradio Endi Glu (Andy Glew) u Ilinoisu sa HaRRM-om.

Ulazni podaci kod P6-ovog ROB-a sadrže podatke. Nema odvojenog PRF-a. Vrednosti podataka iz ROB-a se kopiraju iz ROB-a u RRF pri penzionisanju.

Jedan mali detalj: ako postoji privremena lokalnost na ROB ulazima (tj., ako se instrukcije koje su blizu jedna drugoj u fon Nojmanovoj sekvenci instrukcija ispišu zajedno na vreme, moguće je izvesti operaciju pisanja kombinovanjem ROB ulaza i tako imati manje portova nego što ima odvojeni ROB/PRF). Ne zna se da li ovo pravi neku razliku pošto bi PRF trebalo da bude pun.

ROB-ovi obično nemaju asocijativnu logiku a i ni jedan od Endi Gluovih ROB-ova nemaju CAM-ove. Kit Difendorf (Keith Diefendorff) je insistirao da ROB-ovi imaju kompleksni asocijativnu logiku već godinama. Prvi ROB predlozi su možda imali CAM-ove.

Detalji: registarski fajlovi koji su ideksirani po oznakama

Ovo je način preimenovanja koji se koriste u MIPS-u R10000, Alpha 21264 i u FP sekciji AMD Athlon-a.

U fazi preimenovanja, svaki referencirani arhitektonski registar (bilo za pisanje ili čitanje) se zaključava u arhitektonski indeksirani remapiran fajl. Ovaj fajl vraća oznaku i bit koji označava spremnost. Oznaka nije spremna kada postoji instrukcija u redu koja se još nije izvršila. za operande čitanja, ova oznaka uzima mesto arhitektonskog registra u instrukciji. Za svako pisanje u registar, nova oznaka se dovlači iz free tag FIFO strukture i piše se novo mapiranje u remapiran fajl tako da će buduće instrukcije koje budu čitale arhitektonski registar referencirati na ovu novu oznaku. Oznaka se označava kao nespremna, zato što se instrukcija još nije izvršila. Prethodni fizički registar koji je alociran za taj arhitektonski registar biva sačuvan sa insturkcijom u baferu za promenu redosleda, koji je FIFO struktura i sadrži instrukcije u programskom redosledu između faza dekodovanja i penzionisanja.

Instrukcije se onda smeštaju u razne redove izvršavanja.

Kako se instrukcija izvrši, oznake za njen rezultat se šalju dalje i redovi izvršavanja proveravaju preklapanja ovih oznaka sa oznakama svojin nespremnih izvornih operanada. Poklapanje znači da je operand spreman. Remapiran fajl takođe poklapa ova oznake tako da može označiti odgovarajući fizički registar spremnim.

Kada se svi operandi u instrukciji u nekom redu izvršavanja spremni, ta instrukcija je spremna za korišćenje. Redovi izvršavanja biraju spremne instrukcije i u svakom ciklusu ih šalju različitim funkcionalnim jedinicama. Nespremne instrukcije ostaju u redovima izvršavanja. Ovo neredosledno uklanjanje instrukcija iz redova izvršavanja je jedan od stvari koje ih čine velikima i da koriste puno energije.

Pozvane instrukcije pročitane od strane fizičkog registra indeksiranog oznakom se onda izvršavaju.

Rezultati izvršavanja se pišu na fizički registar koji je indeksiran oznakom, kao i objava obilaznoj mreži koja prethodi svakoj funkcionalnoj jedinici.

Penzionisanje stavlja prethodnu oznaku za napisani arhitektonski registar u prazan red tako da se može ponovo iskoristiti za novodekodovanu instrukciju.

Neki izuzetak ili loša predikcija grananja mogu izazvati da se remapiran fajl vrati u repamirano stanje na zadnju važeću instrukciju putem kombinacije snapshots stanja i kruženja kroz prethodne oznake u redu pre "penzionisanja". Pošto se zahteva ovaj mehanizam i pošto može povratiti svako remapirano stanje (ne samo stanje pre nego što se instrukcija penzionisala), lošom predikcijom grananja se može baratati pre nego što grana stigne da se penzioniše. Time se potencijalno sakriva kašnjenje loše procene.

Detalji: rezervacione stanice

Ovo je način koji se koristi u celobrojnoj sekciji AMD-ovih K7 i K8 dizajna.

U fazi remapiranja, svaki referencirani arhitektonski registar za čitanje se zaključava u oba arhitektonski indeksirana fajla (buduću fajl i fajl preimenovanja). Čitanje budućeg fajla daje vrednost tog registra, ako još uvek ne postoji istaknuta instrukcija na koju treba da se piše (tj. ako još uvek nije spremna). Kada se intrukcija smesti u red izvršavanja, vrednosti pročitane iz budućeg fajla se pišu u odgovarajuće ulaze u rezervacionim stanicama. Registar beleži novu, nespremnu oznaku za instrukciju koja će se pisati u fajl preimenovanja. Broj oznake se obično serijski alocira u instrukcijskom redosledu. Nije potreban free tag FIFO,

Kao i sa šemom sa označenim indeksiranjem, redovi izvršavanja čekaju na nespremne operande da bi videli informaciju o poklapanju oznaka. Za razliku od šeme sa označenim indeksiranjem, poklapanje oznaka izaziva da se vrednost koja se prosleđuje svima napiše u rezervacionu stanicu ulaznog reda izvršavanja .

Pozvane instrukcije čitaju svoje argumente iz rezervacionih stanica, zaobilaze just-broadcast operande i onda se izvršavaju. Kao što je pomenuto ranije, registarski fajlovi rezervacionih stanica su obično mali sa možda 8 ulaza.

Rezultati izvršavanja se pišu u bafer za promenu redosleda, u rezervacionu stanicu (ako ulazni red izvršavanja ima poklapanje oznaka), i u budući fajl ako je to poslednja instrukcija koja selektuje taj arhitektonski registar (u tom slučaju se regustar označava kao spreman).

Penzionisanje kopira vrednost iz bafera u arhitektonski registarski fajl. Jedina upotreba arhitektonski registarskog fajla je da se oporavi od izuzetaka i loše predikcije grananja.

Izuzecii loše predikcije grananja, koje se prepoznaju u penzionisanju, izazivaju da se arhitektonski fajl kopira u budući fajl i da se svi registri označe kao spremni u fajlu preimenovanja. Obično ne postoji način da se za neke instrukcije rekonstruiše stanje budućeg fajla odmah između dekodovanja i penzionisanja tako da obično ne postoji način da se dobije rani oporavak od loše procene grananja.

Poređenje šema

U obe šeme instrukcije se ubacuju u određenom redosledu u redove izvešavanja ali se vanredno izbacuju. Ako redovi ne uklonjaju prazne slotove, onda će oni ili ili imati puno nekorišćenih slotova ili će zahtevati neku vrstu kodiranja prioriteta promenljivih za kada je više instrukcija spremno da se izvrši istovremeno. Redovi koji uklanjaju rupe imaju jednostavniji sistem za kodiranje prioriteta ali zahtevaju jednostavna ali velika kola da proguraju instrukcije kroz red.

Stanice rezervacija imaju manje kašnjenje od preimenovanja do izvršavanja zato što faza preimenovanja nalazi vrednosti registara direktno, umesto da ih traži po fizičkom broju registara i da onda koristi to da nađe vrednost. Ovo kašnjenje se pokazuje kao komponenta kašnjenja lošeg predviđanja grananja.

Stanice rezervacije takođe imaju manje kašnjenje od instrukcija koje se koriste za ivršavanje, zato što je svaki lokalni registarski fajl manji od velikog centralnog fajla šeme sa označenim indeksiranjem. Generacija sa ovim indeksiranjem i obrada izuzetaka su takođe jednostavini u šemi rezervacije stanica.

Fizički registarski fajlovi (koje koriste rezervacione stanice) obično uklanjaju ulaze koji se ne koriste, sa redom izvršavanja kome služe, što čini ove registrarske fajlove ukupno većima i takođe troše više energije i više su komplikovaniji od jednostavnih registarskih fajlova koje koriste rezervacione stanice u šemi sa označenim indeksiranjem. Što je još gore, svaki ulaz u svakoj stanici može biti ispisan svakim rezultatom magistrale, tako da mašina sa rezervacionim stanicama sa, npr. 8 ulaza (za redove izvršavanja) po funkcionalnoj jedinici će imati 9 puta više zaobilazaka mreže kao i mašina sa označenim indeksiranjem sa istim karakteristikama. Kao rezultat toga imamo mnogo veću potrošnju energije i oblasti nego kod dizajna sa označenim indeksiranjem.

Štaviše, šema sa rezervacionim stanicama ima 4 mesta (budući fajl, rezervacionu stanicu, bafer za promenu redosleda i arhitektonski fajl) gde se rezultat može smestiti, dok šema sa označenim indeksiranjem ima samo jedno (fizički registarski fajl). Zbog rezultata funkcionalnih jedinca, obaveštenje koje se prosleđuje svim lokacijama za skladištenje, mora dostići mnogo veći broj lokacija u mašini koja koristi šemu sa označenim indeksiranjem. Ova funkcija troši više vremena, snage i prostora. Ipak, kdo mašina koje su opremljene sa veoma preciznom šemopm predikcijom grananja rezervacione stanice mogu da rade veoma dobro ako kašnjenja izvršavanja predstavljaju veliku brigu.

Istorija

IBM System/360 Model 91 je bila mašina koja je trebalo da podrži vanredno izvršavanje instrukcija. Koristila je Tomasulio algoritam koji koristi preimenovanje registara.

POWER1 je prvi mikroprocesor koji je koristio preimenovanje registara i vanredno izvršavanje (1990).

Originalni dizajn R10000 mašine nije imao ni problem rušenja niti kodiranje prioriteta promenljivih, a patio je od problema izgladnjivanja. Kao rezultat toga, najstarija instrukccija u redu ponekad ni bi bila izvršena dok se obe instrukcije dekodiranja ne stanu potpuno zboh nedostatka preimenovanih registara i dok se svaka druga instrukcija ne pokrene. Kasnije revizije dizajna, počevši od R12000 su koristile delimično kodiranje prioriteta promenljivih da bi izbegle ovaj problem.

Ranije mašine sa vanrednim izvršavanjem nisu razdvajale funkcije za preimenovanje i ROB/PRF funkcije za skladištenje. Zbog toga, neke od najranijih, kao što je Sohi RUU ili Metaflow DCAF, su kombinovale zakazivanje, preimenovanje i skladištenje sve u jednoj istoj strukturi.

Većina modernih mašina vrše preimenovanje tako što RAM indeksira tabelu mapa sa logičkim registarskim brojevima. P6 je ovo radio - njegovi budući fajlovi su ovo radili i svi podaci za skladištenje su bili u istoj strukturi.

Međutim, ranije mašine su koristile CAM (engl. content-addressable memory, tip hardvera koji je omogućavao funkcionalnost nekog asocijativnog niza u preimenivaču). CAM je koristio HPSM RAT (Register Alias Table) na logičkom broju registara u kombinaciji sa različitim verzijama registara.

U većini slučajeva, priča mikroarhitekture vanrednog izvršavanja je bila kako da se ovi CAM-ovi progresivno eleminišu. Mali CAM-ovi su korisni. Veliki su nepraktični.

P6 mikroarhitektura je bila prva Intel-ova mikroarhitektura koja je implementirala i vanredno izvršavanje i preimenovanje registara. Koristila se u Pentium Pro, Pentium II, Pentium III, Pentium M, Core, i Core 2 procesorima.

Literatura

• Smith, J. E.; Pleszkun, A. 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 Trans. Comput. 37 (5): 562—573. doi:10.1109/12.4607. 
• Smith, J. E.; Pleszkun, A. R. (1998). „Implementation of precise interrupts in pipelined processors”. 25 years of the international symposia on Computer architecture (selected papers) - ISCA '98. str. 291—299. ISBN 1581130589. doi:10.1145/285930.285988.