Rekisterien uudelleennimeäminen: prosessorin optimointi ja rinnakkaisuus
Rekisterien uudelleennimeäminen: tehosta prosessorin suorituskykyä ja rinnakkaisuutta — vähemmän viivettä, parempi pipeline-hyöty ja nopeammat ohjelmat.
Tietokonetekniikassa rekisterien uudelleennimeämisellä tarkoitetaan tekniikkaa, jota käytetään välttämään ohjelman ohjeiden tarpeetonta sarjamuotoista suorittamista, koska kyseiset ohjeet käyttävät samoja rekistereitä uudelleen.
Miksi rekisterien uudelleennimeäminen on tarpeen?
Prosessorit pyrkivät suorittamaan useita ohjeita rinnakkain (opeartion-level parallelism, ILP) ja pitämään putkistonsa täynnä. Monissa ohjelmissa samaa loogista rekisteriä käytetään eri vaiheissa usean ohjeen välillä, mikä aiheuttaa keinotekoisia riippuvuuksia ja estää rinnakkaisuuden. Rekisterien uudelleennimeäminen poistaa nämä väärät riippuvuudet siten, että eri ohjeiden käyttöön liitetään eri fyysiset rekisterit, vaikka ne viittaisivat samaan loogiseen rekisteriin.
Riippuvuustyypit — mitä uudelleennimeäminen korjaa
- RAW (Read After Write) — todellinen riippuvuus, jossa lukemisen pitää tapahtua kirjoituksen jälkeen. Tätä ei voi poistaa rekisterien uudelleennimeämisellä.
- WAR (Write After Read) — väärä riippuvuus: myöhempi kirjoitus estää aiempaa lukua, ellei rekistereitä eriytetä.
- WAW (Write After Write) — väärä riippuvuus kahden kirjoituksen välillä; uudelleennimeäminen mahdollistaa molempien kirjoitusten erillisen käsittelyn.
Rekisterien uudelleennimeäminen poistaa erityisesti WAR- ja WAW-tyyppiset väärät riippuvuudet, mikä lisää rinnakkaisuutta ja parantaa putkiston läpäisyä.
Miten uudelleennimeäminen toteutetaan käytännössä?
Nykyisissä suorittimissa rekisterien uudelleennimeäminen tehdään yleensä laitteistotasolla käyttämällä seuraavia rakenteita:
- RAT (Register Alias Table) tai muut kartoitustaulukot, jotka pitävät kirjaa loogisten rekistereiden ja niihin liitettyjen fyysisten rekisterien välisestä kartoituksesta.
- Vapaa rekisterilista (free list), josta otetaan uusia fyysisiä rekistereitä ohjeiden uudelleennimeämisiin.
- ROB (Reorder Buffer), joka tallentaa ohjeiden tulokset ja varmistaa oikean järjestyksen sitoutumisen (commit) programman näkökulmasta; rob helpottaa tarkkojen virhetilojen palauttamista ja tarkkaa suoritustilaa.
- Reservation stations / Tomasulo-tyylinen arkkitehtuuri, jossa riippuvuudet jaonaista varaustilojen kautta mahdollistavat dynaamisen ohjeiden uudelleenjärjestelyn.
Esimerkkejä ja historiaa
Monet modernit suorittimet (Intel, AMD, ARM) käyttävät jotain rekisterien uudelleennimeämisen muotoa osana out-of-order-suoritusta. Historian kannalta merkittävä ratkaisu oli Tomasulon algoritmi (1960–1970-luvuilla), joka yhdisti dynaamisen uudelleenjärjestelyn, varausasemat ja rekisterien uudelleennimeämisen. Sittemmin ratkaisua on laajennettu mm. ROB:lla ja spekulatiivisella suorittamisella.
Spekulatiivinen suoritus ja haavoittuvuudet
Uudelleennimeäminen toimii hyvin yhdessä spekulatiivisen haarojen ennustuksen kanssa: ohjeita voidaan suorittaa eteenpäin ennen kuin haarapäätös on lopullinen. Jos ennuste osoittautuu vääräksi, arkitehtuuri voi kumota muutokset käyttämällä ROB:ia ja palauttaa rekisterikartoitukset aiempaan tilaan. On kuitenkin huomioitava, että spekulointi + uudelleennimeäminen on ollut mukana myös eräissä sivukanavahyökkäyksissä (esim. Spectre-luokka), joten prosessorisuunnittelussa on kiinnitettävä huomiota turvallisuuteen ja tietovuotoihin.
Rinnakkaisuus, monisäikeisyys ja resurssien jakaminen
Rekisterien uudelleennimeäminen parantaa sekä yksittäisen säikeen ILP:ta että kokonaisjärjestelmän suorituskykyä. Monisäikeisyydessä (SMT / Hyper-Threading) fyysisten rekisterien jakaminen useiden kontekstien kesken voi kuitenkin aiheuttaa resurssipaineita: suoritin voi varata rekistereitä molemmille säikeille, ja riittämätön määrä fyysisiä rekistereitä voi rajoittaa hyötyä. Arkkitehtuurit voivat ratkaista tämän erottamalla rekisterit säikeittäin tai käyttämällä dynaamisia jakoalgoritmeja.
Rajoitukset ja mitä uudelleennimeäminen ei tee
- Se ei poista todellisia tietoriippuvuuksia (RAW).
- Se vaatii lisähardwarea (lisärekisterit, taulukot, logiikka), mikä lisää piin kokoa ja virrankulutusta.
- Väärin toteutettuna uudelleennimeäminen voi monimutkaistaa virheiden käsittelyä ja poikkeusten palauttamista.
Kompilaattorin rooli vs. laitteistopohjainen uudelleennimeäminen
Kompilaattorit tekevät oman rekisterinhallintansa (rekisteriallokointi) staattisesti käännösaikana, mutta laitteistopohjainen uudelleennimeäminen toimii dynaamisesti suorituksen aikana. Nämä lähestymistavat täydentävät toisiaan: compile-aika pyrkii minimoimaan tarpeettomat rekisterien vaihtelut, kun taas hardware voi hyödyntää lisääntynyttä rinnakkaisuutta ajonaikaisesti.
Yhteenveto
Rekisterien uudelleennimeäminen on keskeinen tekniikka nykyaikaisissa prosessoreissa, jolla poistetaan väärät rekisteririippuvuudet ja lisätään ohjeiden rinnakkaista suorittamista. Se parantaa suorituskykyä yhdessä out-of-order- ja spekulatiivisen suorituksen kanssa, mutta tuo myös suunnittelun ja turvallisuuden haasteita sekä vaatii lisäresursseja. Oikein toteutettuna se on yksi tärkeimmistä tavoista hyödyntää laitteiston rinnakkaisuus tehokkaasti.
Ongelman määritelmä
Ohjelmat koostuvat ohjeista, jotka toimivat arvoilla. Ohjeiden on nimettävä nämä arvot, jotta ne voidaan erottaa toisistaan. Tyypillinen käsky voisi kuulua seuraavasti: Lisää X ja Y ja laita tulos paikkaan Z. Tässä käskyssä X, Y ja Z ovat tallennuspaikkojen nimiä.
Kompaktin käskykoodauksen aikaansaamiseksi useimmissa prosessorin käskykokonaisuuksissa on pieni joukko erikoispaikkoja, jotka voidaan nimetä suoraan. Esimerkiksi x86-käskykokonaisuusarkkitehtuurissa on 8 kokonaislukurekisteriä, x86-64:ssä 16, monissa RISC-järjestelmissä 32 ja IA-64:ssä 128. Pienemmissä prosessoreissa näiden paikkojen nimet vastaavat suoraan rekisteritiedoston osia.
Eri ohjeet voivat kestää eri aikaa (esim. CISC-arkkitehtuuri). Prosessori voi esimerkiksi pystyä suorittamaan satoja käskyjä, kun yksi lataus keskusmuistista on käynnissä. Lyhyemmät ohjeet, jotka suoritetaan latauksen ollessa kesken, valmistuvat ensin, jolloin ohjeet valmistuvat alkuperäisestä ohjelmajärjestyksestä poiketen. Järjestyksen ulkopuolista suoritusta on käytetty uusimmissa huipputehokkaissa suorittimissa joidenkin nopeusetujen saavuttamiseksi.
Ajattele tätä ohjeiden sekvenssiä, joka suoritetaan epäjärjestyksessä olevalla suorittimella:
1.LOAD R1, LOC MEM[1024] 2.R1 = R1 + 2 3.STORE R1, LOC MEM[1024+8] 4.LOAD R1, LOC MEM[2048] 5.R1 = R1 + 4 6.STORE R1, LOC MEM[2048+8]
Käskyt 4, 5 ja 6 ovat riippumattomia käskyistä 1, 2 ja 3, mutta prosessori ei voi suorittaa käskyä 4
loppuun ennen kuin käsky 3 on valmis, koska 3 kirjoittaisi silloin väärän arvon.
Ongelman ratkaisu
Voimme poistaa tämän rajoituksen muuttamalla joidenkin rekisterien nimiä:
1.LOAD R1, LOC MEM[1024] 2.R1 = R1 + 2 3.STORE R1, LOC MEM[1024+8] 4.LOAD R2, LOC MEM[2048] 5.R2 = R2 + 4 6.STORE R2, LOC MEM[2048+8]Nyt ohjeet 4, 5 ja 6 voidaan suorittaa rinnakkain ohjeiden 1, 2 ja 3 kanssa, jolloin ohjelma voidaan suorittaa nopeammin.
Mahdollisuuksien mukaan kääntäjät tekevät tämän uudelleennimeämisen. Kääntäjiä rajoittaa kuitenkin suorittimen rekisterien määrä. Monissa suorituskykyisissä suorittimissa on enemmän fyysisiä rekistereitä kuin mitä voidaan nimetä suoraan käskykokonaisuudessa, ja ne voivat nimetä rekisterit uudelleen laitteistossa parempien käskytason rinnakkaistoimintojen saavuttamiseksi.
Kaikki luettava ja kirjoitettava voidaan nimetä uudelleen. Yleiskäyttö- ja liukulukurekisterit ovat yleisimpiä, mutta myös lippu- ja tilarekistereitä tai jopa yksittäisiä tilabittejä nimetään yleisesti uudelleen.
Muistipaikkoja voidaan myös nimetä uudelleen, vaikkakaan sitä ei yleensä tehdä samalla tasolla kuin rekisterien uudelleen nimeämistä.
Vaarat Ongelma
Kun useampi kuin yksi käsky viittaa tiettyyn operandin paikkaan joko lukemalla sitä (syötteenä) tai kirjoittamalla sitä (tulosteena), näiden käskyjen suorittaminen alkuperäisestä ohjelmajärjestyksestä poikkeavassa järjestyksessä voi aiheuttaa kolmenlaisia ongelmia, joita kutsutaan myös vaaratekijöiksi:
- Kirjoituksen jälkeinen lukeminen (RAW)
Rekisteristä tai muistipaikasta luettaessa on palautettava arvo, joka on asetettu sinne ohjelman järjestyksessä viimeisellä kirjoituksella, ei jollain muulla kirjoituksella. Tätä kutsutaan todelliseksi riippuvuudeksi tai virtausriippuvuudeksi, ja se edellyttää, että ohjeet suoritetaan ohjelmajärjestyksessä.
- Kirjoituksen jälkeinen kirjoitus (WAW)
Tietyn rekisterin tai muistipaikan peräkkäisten kirjoitusten on jätettävä kyseinen paikka sisältämään toisen kirjoituksen tulos. Tämä voidaan tarvittaessa ratkaista puristamalla (synonyymit: peruuttamalla, mitätöimällä, poistamalla) ensimmäinen kirjoitus. WAW-riippuvuuksia kutsutaan myös tulostusriippuvuuksiksi.
- Lukemisen jälkeinen kirjoitus (WAR)
Rekisteristä tai muistipaikasta luetun arvon on palautettava viimeisin kyseiseen paikkaan kirjoitettu arvo, ei lukemisen jälkeen ohjelmallisesti kirjoitettua arvoa. Tällainen väärä riippuvuus voidaan ratkaista nimeämällä uudelleen. WAR-riippuvuuksia kutsutaan myös antiriippuvuuksiksi.
Sen sijaan, että kirjoitusta viivytettäisiin, kunnes kaikki lukukerrat on suoritettu, voidaan säilyttää kaksi kopiota sijainnista, vanha arvo ja uusi arvo. Uuden arvon kirjoitusta ohjelmajärjestyksessä edeltävät lukukerrat voivat saada vanhan arvon, vaikka muut kirjoitusta seuraavat lukukerrat saavat uuden arvon. Väärä riippuvuus katkeaa ja luodaan lisää mahdollisuuksia järjestyksen ulkopuoliseen suoritukseen. Kun kaikki vanhaa arvoa tarvitsevat lukukerrat on tyydytetty, se voidaan hylätä. Tämä on rekisterien uudelleennimeämisen keskeinen käsite.
Aiheeseen liittyvät sivut
- Rinnakkaislaskenta
- Käskytason rinnakkaisuus
Etsiä