Rinnakkaislaskenta¶
Osaamistavoitteet: Erilaisia tapoja toteuttaa rinnakkaislaskentaa moderneissa suorittimissa.
Prosessorin ja muistin sisäisen toiminnan optimoinnin ohella suoritustehoa haetaan nykyään rinnakkaislaskennan avulla, missä ajatus on että ohjelma tai prosessi jaetaan usean suorittimen tai ytimen (engl. core) kesken, jotka suorittavat ohjelmakoodia yhtäaikaisesti ja synkronoidusti.
Tämä luo myös haasteita ohjelmointiin, koska ohjelmat tulisi laatia siten, että niiden suorituksessa voidaan hyödyntää useita ytimiä. Eli ohjelma olisi voitava jakaa osiin, joissa on minimaalisesti riippuvuuksia toisiinsa, joka minomoi data- ja kontrollihasardit. Usein käytetään rinnakkaislaskentaa tukevia ohjelmointikieliä tai -laajennuksia olemassaoleviin kieliin.
Modernit kääntäjät osaavat jo optimoida ohjelmakoodia niin, että rinnakkaisuuden toteuttaminen on mahdollista niiden ja suorittimen yhteispelillä. Kääntäjä voi jo optimoida ohjelmaa valitulle suorittimelle ja muokata koodia niin, että havaitut data- ja kontrollihasardit eliminoidaan. Lisäksi kääntäjä voi arvioida ohjelman käskyjen suoritusjärjestystä (engl. prediction / speculation). Tässä kääntäjä voi esimerkiksi lisätä käskyjä ohjelmaan (nop jne) tai järjestellä käskyt uuteen suoritusjärjestykseen! Kääntäjä voi jopa toteuttaa ohjelmakoodiin valmiiksi erilaisia ohjelman suoritushaaroja, jotka valitaan suoritettavaksi sen mukaan, mikä haara on optimaalisin itse suoritustilanteessa.. Tällainen käännöksen aikainen optimointi on staattista, eli sisäänrakennettu ohjelmaan.
Suoritin voi lisäksi ohjelman ajonaikana dynaamisesti optimoida suoritusta kontrollilogiikan optimointitekniikoiden avulla. Suoritin esimeriksi analysoi koodia eteenpäin ja määrittää kuinka monta käskyä voidaan suorittaa yhden kellojakson aikana tai mitkä käskyt suoritetaan missä kellojaksossa (engl. out-of-order execution), huomioiden ja pyrkien eliminoimaan riippuvuudet.
Aiemmassa materiaalissa esittelemämme liukuhihntatoteutus on in-order pipeline, koska siinä käskyt suoritetaan kääntäjältä annetussa järjestyksessä. Yleisesti moderneissa suorittimissa liukuhihnalla voi, kun otetaan usea eri optimointitekniikka käytäntöön, olla samanaikaisesti kymmeniä eri käskyjä suorituksessa!
Käskytason rinnakkaisuus¶
Kun konekielisen ohjelman käskyjä suoritetaan rinnakkain suorittimessa, puhutaan yleisesti käskytason rinnakkaisuudesta (engl. instruction-level parallelism, ILP), jossa suorittimen mikroarkkitehtuuriin toteutetaan erilaisia optimointitekniikoita.
Liukuhihnasuoritin jo osaltaan toteuttaa käskytason rinnakkaisuutta, kun useampi käsky on yhtaikaa suoritettavana eri osajärjestelmissä. Kuten aiemmin todettu, suoritustehoa kokonaisuutena voidaan kasvattaa lisäämällä vaiheita liukuhihnaan. Vaiheita saadaan lisää purkamalla suorittimen käskyt/osajärjestelmät pienempiin ja nopeampiin osiin, jolloin kellojakson pituutta voidaan lyhentää ja tuloksena yleinen suoritusteho (IPS) kasvaa.
Kuvassa alla Intelin Pentium-suorittimen eri sukupolvien liukuhihnojen pituuksia. "Uudet" vaiheet liukuhihnoissa liittyvät optimointitekniikoihin, joilla käsky jaetaan pienempiin osiin, käsitellään liukuhihnarekistereitä ja muokataan käskyjen suoritusjärjestystä. Näistä tekniikoista käytetään yleisesti nimitystä superliukuhihnatekniikat.
Haarautumisen ennustaminen¶
Tunnettu (aiemmin esitetty) ongelma liukuhihnatoteutuksissa ovat ohjelmien ehdolliset käskyt ja hyppykäskyt, joissa ohjelman suoritus voi haarautua. Pahimmillaan liukuhihnalla eri vaiheissa olevat käskyt jouduttiin hylkäämään, jos hyppykäskyssä siirryttiin suorittamaan koodia ihan muualta muistista.
Ennustamista varten on laskettu ohjelmia analysoimalla arvioita siitä mitä väärän hyppykäskyn ennusteen toteuttaminen maksaa ja miten hyppykäskyt käyttäytyvät yleisesti ottaen. Tilastollisesti konekielen koodissa joka 7-8. käsky on ehdollinen hyppykäsky. Lisäksi on arvioitu, että ohjelmassa taaksepäin suuntautuvat hypyt ovat tuplasti kalliimpia kuin eteenpäin suuntautuvat.
Rinnakkaislaskennan yhteydessä haarautumisen ennustamista (eng. branch prediction) on tullut oleellinen optimointitekniikka suoritustehon kasvattamiseksi. Näillä tekniikoilla voidaan ohjelmaa suorittaessa valita se suorituspolku, joka on todennäköisimmin oikea. PC-maailmassa hyppykäskyn hintaa voidaan pienentää ennakointilohkolla (engl. branch prediction buffer), joka pitää muistissa tallessa toteutuneiden hyppykäskyjen osoitteet ja paluuosoitteet, joita uudelleenkäytetään ennustaessa hyppykäskyn kohdetta kun liukuhihnaa täytetään.
Superskalaariprosessori¶
Toinen tapa on lisätä suorittimeen rinnakkaisia osajärjestelmiä, jolloin usea käsky voi olla liukuhihnalla samassa vaiheessa omassa osajärjestelmässään (engl. superscalar processor). Superskalaarissa prosessorissa voi olla esimerkiksi neljä ALUa, joilla jokasella oma (eri pituinen) liukuhihna, ja erityyppiset ohjelman käskyt jaetaan eri ALUille.
Tyypillisesti kokonaisluku ja liukulukulaskenta voidaan suorittaa omilla ALUillaan, jossa liukulukulaskenta vaatii pitemmän liukuhihnan. Mutta, lisäksi muistiosoitukset voidaan jakaa eri ALUille, jotka muodostavat muistiosoitteet ja suorittavat hakuoperaatiot. Esimerkiksi Pentium Pro-prosessorissa oli viisi erillistä suoritusyksikköä: datan tallennus muistiin, muistiosoitteen laskenta, muistin lukuoperaatio, kokonaislukulaskenta ja liukulukulaskenta.
Kuvassa esimerkki superskalaarista liukuhihntatoteutuksesta, jossa muistiosoitukset on eriytetty laskenta- ja hyppyoperaatioista.
VLIW-käskykanta¶
Superskalaarien suoritinarkkitehtuurien yhteydessä puhutaan VLIW-käskykannasta (engl. very long instruction word). VLIW-käskyt on tyypillisesti hyvin pitkiä (jopa 128 bittiä), koska niissä on kuvattu usean eri käskyn operaatiokoodit ja operandit.
Nyt optimointia tehdään siten, että valitaan ja järjestellään erityyppiset käskyt VLIW-suorittimelle optimaalisessa muodossa. Esimerkiksi neljä käskyä sisältävässä VLIW-käskyssä on voitu varata paikat liukulukuoperaatiolle, kokonaislukuoperaatiolle, ehdolliselle operaatiolle ja muistioperaatiolle. Tällöin usein hyödynnetään käskyjen "epäjärjestystä" ohjeman suorituksessa.
Kuvassa alla Transmetan Crusoe-suorittimen arkkitehtuurin kerrokset, jossa x86-käskyt muokataan VLIW-käskyiksi.
Käskyjen jako rinnakkaisille liukuhihnoille on toki mahdollista tehdä jo (VLIW-)kääntäjässä, jolla saadaan se hyöty, että eri suoritusosien toteutus yksinkertaistuu. Mutta, hasardien käsittely on sitten taas monimutkaisempaa. Näin ollen, VLIW-suorittimet eivät useinkaan ole yleiskäyttöisiä vaan sovelluskohtaisia, esimerkiksi DSP-prosessorit.
Epäjärjestyksessä suorittaminen¶
Kuvassa alla käskytason rinnakkaisuutta toteuttavan suorittimen arkkitehtuuri, jossa käskyjä ajetaan optimoidussa epäjärjestyksessä (out-of-order execution).
Suoritin on jaettu kahteen osaan: ohjaus- (instruction control unit) ja suoritusyksikköön (execution unit). Ohjausyksikkö''' lukee käskyt erillisestä välimuistista (instruction cache) ja toteuttaa ennustamisen Fetch control-osajärjestelmässä, joka puskuroi käskyt. Decode-komponentti taas purkaa käskyt mikro-operaatioiksi, jotta ne voidaan suorittaa pitkissä likuhihnoissa optimaalisesti. Ohjausosassa on vielä eläköitymisyksikkö (hieno suomennos eikös? engl. retirement unit), jonka tehtävänä on huolehtia, että ohjelma kokonaisuutena suoritetaan loogisesti oikeassa järjestyksessä. Ohjauksen pitää myös päivittää käskyjen tulokset rekistereihin oikeassa järjestyksessä, kun ne on saatu liukuhihnasta läpi. Jos ennustus menee pieleen, ohjausosa tyhjentää puskureista ja rekistereistä väärät tulokset.
Suoritusyksikkö jakaantuu sitten rinnakkaisiin laskentayksiköihin, joista jokainen on erikoistunut suorittamaan omalla liukuhihnallaan erityyppiset käskyt.
Moniydinprosessorit¶
Seuraava askel rinnakkaisuuden toteuttamisesta on tehtävä- tai prosessitason rinnakkaisuuden toteuttaminen. Tavoitteena on kasvattaa prosessien suoritustehoa moniajoa tukevissa tietokoneissa tai palvelimissa, joissa prosessit voidaan jakaa usealle ytimelle yhtaikaa suoritettavaksi. Tällöin puhutaan moniydin-suorittimista.
Moniydin-prosessoreissa ohjelmien suorituksen hallinta ja optimointi on sitten jo varsin haastavaa. Joudutaan huomioimaan mm. ohjelman jakaminen rinnakkaisiin osiin, niiden suoritusjärjestys (engl. scheduling), tehtävien suorituksen synkronointi, sekä datan ja suorituskuorman jakaminen ydinten kesken. Ytimet myös kommunikoivat keskenään. Tämän tason rinnakkaisuus vaatii myös ohjelmoijalta rinnakkaisuuden sisäänrakentamista ohjelmiin.
Esimerkkinä tuoreessa Intel Core i9-suoritinperheen prossuissa on jopa 18 ydintä!
Teoriaa¶
Moniydin-keskusyksikköjen toteutukset ovat jaettu konseptuaalisesti neljään ryhmään datavirtojen ja käskyvirtojen mukaan.
SISD¶
SISD (Single instruction stream, single data stream) tarkoittaa perinteistä suoritinta, jossa yksi ydin suorittaa käskyn operandeille jotka ovat peräisin yhdestä datavirrasta.
SIMD¶
SIMD (Single instruction stream, multiple data streams) toteutuksessa on yksi suoritin, jolle data tuodaan 1-ulotteisessa vektorimuodossa (ts. rivinä). Yksi SIMD-käsky suorittaa saman operaation kaikille vektorin alkiolle yhtaikaa. Näinollen, SIMD-toteutus tarvitsee paljon yleisiä rekistereitä mutta vain yhden PC-rekisterin ja suoritukseen liittyvän kontrollilogiikan. Esimerkkinä, taulukkojen käsittely voidaan toteuttaa nopeasti SIMD-käskyllä, mutta SIMD-suoritin toimisi tehottomasti ehtolauseissa.
Tehokas ohjelman suoritus edellyttää, että käytettävissä on riittävästi rekistereitä datavektorin sijoittamiseksi (kokonaisuudessaan) rekistereihin. Tehokkuutta tulee myös siitä, että vektori pyritään hakemaan muistista kokonaisuudessaan rekistereihin kerralla. Vektoriarkkitehtuureissa oletuksena on, ettei käskyjen välillä ole paljon riippuvuuksia, ja liukuhihnan hasardeja tarkistetaan vain käskyjen välillä. Johtuen rinnakkaisesta toteutuksesta silmukkarakenteiden kontrollihasardeja ei esiinny.
SIMD toteuttaa yleisesti vektoriarkkitehtuurin, jossa useampi rinnakkainen ALU tekee operaatiot 1-ulotteiselle datataulukolle yhden käskysyklin aikana. Käskyt suoritetaan sekventiaalisesti. Vektoriprosessorin käskykannassa on erilliset vektorioperaatiot. Nyt esimerkiksi voidaan lisätä numeroarvon vektorin kaikkiin alkioihin kerralla tai jokainen alkio voidaan kertoa samalla luvulla, jne.
Esimerkkinä SIMD-toteutuksesta ovat x86-perheen laajennetun käskykannan MMX- ja SSE-käskyt. Esimerkiksi MMX-käskyt hyödyntävät erillisiä MMX-rekistereitä, jotka ovat pitempiä (esim. 64-bittisiä) kuin suorittimen yleisrekisterit (GPR). Sisäisesti MMX-käskyjä varten yleisrekistereitä voidaan "lainata" MMX-käyttöön.
Tunnetusti vektoriarkkitehtuuria hyödyntävät Cray-supertietokoneet, jo 1970-luvulta alkaen.
MISD¶
MISD (Multiple instruction streams, single data stream) malli on teoreettinen. MISD-prosessori toteuttaisi yhtaikaa useita käskyjä samalle data-alkiolle. Tämä muistuttaa toki nykyisiä rinnakkaisia liukuhihnatoteutuksia, mutta MISD-arkkitehtuuria tarkalleen noudattaen liukuhihnalla olevan datan pitäisi pysyä prikulleen samana kaikkien liukuhihnojen kaikissa vaiheissa..
Käytännössä vastaava toiminnallisuus saadaan SIMD- ja MIMD-arkkitehtuureilla.
MIMD¶
MIMD (Multiple instruction streams, multiple data streams) tarkoittaa toteutusta, jossa usea ydin suorittaa operaatioita rinnakkain omassa muistissaan (väli- ja virtuaalimuistit). Data on peräisin samasta jaetusta fyysisestä muistista, joten ohjelman suorituksen ja muistioperaatioiden synkronointia ytimien kesken tarvitaan.
MIMD-toteutus mahdollistaa erillisten ohjelmien ajamisen eri ytimissä, esimerkiksi eri prosessien tai säikeiden (siellä Käyttöjärjestelmät-kurssissa sitten..) ajamisen omissa ytimissään. Kuitenkin yleensä yhtä ohjelmaa ajetaan kaikissa ytimissä yhtäaikaisesti. Tällöin ohjelma jaetaan koodatessa ehdollisilla lauseilla (jotka voivat olla lisäyksiä johonkin tunnettuun ohjelmointikieleen) ytimien kesken niin, että eri koodilohkoja ajavat eri ytimet. Jokaisessa ytimessä usein on oma kopio ohjelman koodista ja datasta, sen omassa välimuistissa.
Esimerkki MIMD-suorittimesta on Intel Core i7 vuodelta 2008.
GPU¶
Erilliset grafiikkaprosessorit (engl. Graphics Processing Unit, GPU) ovat yleistyneet. Yhdessä GPU:ssa saattaa olla satoja liukulukulaskentaan omistettuja rinnakkaisia suoritusyksikköjä, joita käytetään nopeaan laskentaan, esimerkiksi grafiikan tuottamisessa. GPU-ohjelmointi onkin nykyään myös tullut osaksi mainstream-ohjelmointia ja niitä voidaan valjastaa laskentaan muissakin tarkoituksissa, esimerkiksi massadata-analyysissä.
GPU:t eroavat yleisestä CPU:sta seuraavasti:
- GPU:t ovat laitteistokiihdyttimiä, joiden tarkoitus on nopeuttaa haluttuja operaatiota, joten niissä ei tarvitse olla samoja ominaisuuksia kuin mitä yleinen CPU vaatisi.
- GPU:ssa on jopa enemmän rekistereitä kuin vektoriprosessoreissa.
- GPU:ssa ei ole monitasoisia välimuisteja, mutta tehokkuutta saadaan, kun muistiosoituksen aikana suoritetaan muita käskyjä.
- GPU:n muistipiireissä tarvitaan isot väylänleveydet.
- Datan koko on yleensä satoja megatavuja, kun se CPU:ssa on kymmeniä / satoja kilotavuja.
Kuvassa alla yleinen NVIDIAn GPU-arkkitehtuuri:
Lopuksi¶
Tämä materiaali on vasta lyhyt yleiskatsaus modernien mikroprosessorien maailmaan. Kuten käy ilmi, laskentaa suorittava ALU on vain pieni osa suorittimen arkkitehtuurissa. Suorittimen toimintaa enemmänkin hallitsevat rinnakaiset osajärjestelmät, liukuhihnat ja niitä heijastavat käskykannat, ohjausosien moninaiset ja -mutkaiset toteutukset ennustamisiin sekä välimuistit eri tasoilla.
Anna palautetta
Kommentteja materiaalista?