Rinnakkaislaskenta¶
Osaamistavoitteet: Erilaisia tapoja toteuttaa rinnakkaislaskentaa moderneissa suorittimissa.
Prosessorin ja muistin sisäisen toiminnan optimoinnin ohella suoritustehoa haetaan nykyään rinnakkaislaskennan (engl. Parallel processing / computing) avulla, missä ajatus on että ohjelma tai prosessi jaetaan usean suorittimen tai ytimen (engl. core) kesken, jotka suorittavat joko samaa tai eriä ohjelmakoodin osaa yhtäaikaisesti ja synkronoidusti.
Tämä luo myös haasteita ohjelmointiin, koska ohjelmat tulisi laatia siten, että niiden suorituksessa voidaan optimaalisesti hyödyntää useita ytimiä. Ohjelma olisi voitava jakaa osiin, joissa on minimaalisesti riippuvuuksia toisiinsa jotta vältetään data- ja kontrollihasardit. Usein käytetään rinnakkaislaskentaa tukevia ohjelmointikieliä tai -laajennuksia olemassaoleviin kieliin. Esimerkkinä rinnakkaislaajennus C-kieleen.
Modernit kääntäjät osaavat jo optimoida ohjelmakoodia niin, että rinnakkainen suoritus on mahdollista:
- Kääntäjä optimoi valitulle suorittimelle, esimerkiksi käskykannan mukaan, ja muokkaa koodia niin, että havaitut data- ja kontrollihasardit eliminoidaan.
- Kääntäjä voi arvioida ohjelman käskyjen suoritusjärjestystä (engl. prediction / speculation), keinoina esimerkiksi lisätä käskyjä ohjelmaan (esim.
nop
) tai järjestellä käskyt uuteen suoritusjärjestykseen! - Kääntäjä voi toteuttaa konekieliseen koodiin 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 tietenkin myös ohjelman ajonaikana dynaamisesti optimoida suoritusta ohjausosan 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). Näin voidaan muunmuassa eliminoida riippuvuudet tai muuttaa käskyjen suoritusjärjestystä.
Aiemmassa materiaalissa esittelemämme (y86-)liukuhihnatoteutus on in-order pipeline, koska siinä käskyt suoritetaan kääntäjältä annetussa järjestyksessä.
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 lyhentämällä liukuhihnan vaiheiden suoritusaikoja, josta seuraa uusia vaiheita. 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. Tietysti rajana on liukuhihnan ohjaukseen tarvittava lisääntynyt aika.
Kuvassa alla Intelin Pentium-suorittimen eri sukupolvien liukuhihnojen pituuksia. Kuvassa "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 (engl. super pipeline).
Esimerkki. Huomatkaa keskimmäisellä rivillä Decode-vaiheen jakaminen pienempiin osiin. Tai alimalla rivillä Execute-vaihe vasta kellojaksolla 17..
Haarautumisen ennustaminen¶
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.
Aiemmin on myös laskettu, ohjelmia analysoimalla, arvioita siitä mitä väärän hyppykäskyn ennusteen toteuttaminen maksaisi ja miten hyppykäskyt käyttäytyvät yleisesti ottaen. Tilastollisesti, konekielisessä 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 voidaan uudelleenkäyttää ennustaessa hyppykäskyn kohdetta, siinä vaiheessa kun liukuhihnaa täytetään eteenpäin.
Superskalaariprosessori¶
Toinen tapa toteuttaa käskytason rinnakkaisuutta 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 ohjausosassa erityyppiset ohjelman käskyt jaetaan eri ALUille. Tyypillisesti kokonaisluku ja liukulukulaskenta voidaan suorittaa omissa erillisissä ALUissa. Tässä usein liukulukulaskenta vaatii pitemmän liukuhihnan. Lisäksi muistiosoitukset voidaan jakaa eri ALUille, jotka muodostavat muistiosoitteet ja suorittavat hakuoperaatiot.
Esimerkiksi Pentium Pro-prosessorissa on viisi erillistä suoritusyksikköä: datan tallennus muistiin, muistiosoitteen laskenta, muistin lukuoperaatio, kokonaislukulaskenta ja liukulukulaskenta.
Kuvassa esimerkki superskalaarista liukuhihntatoteutuksesta, jossa muistiosoitukset (load or sotre) 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 yhdessä usean eri käskyn operaatiokoodit ja operandit.
Nyt optimointia voidaan tehdä 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 suorituspaikat liukulukuoperaatiolle, kokonaislukuoperaatiolle, ehdolliselle operaatiolle ja muistioperaatiolle omissa ALUissaan. Tällöin usein hyödynnetään käskyjen epäjärjestystä ohjelman suorituksessa optimoinnissa, koska käskyjen suoritusaika voi vaihdella suuresti.
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, esimerkkinä DSP-prosessorit.
Epäjärjestyksessä suorittaminen¶
Kuvassa alla käskytason rinnakkaisuutta toteuttavan suorittimen arkkitehtuuri, jossa käskyjä ajetaan optimoidussa epäjärjestyksessä (engl. out-of-order execution).
Tässä suoritin on jaettu kahteen osaan: ohjaus- (instruction control unit) ja suoritusyksikköön (execution unit). Suorittimen sisäinen väylä kytkee ohjaus- ja suoritusosat yhteen.
1. Ohjausyksikkö lukee käskyt erillisestä sisäisestä käskyvä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.
2. Suoritusyksikkö jakaantuu 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 kerrallaan (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 ohjaus on sama kaikille.
Esimerkki. Taulukkojen käsittely voidaan toteuttaa nopeasti SIMD-käskyllä, mutta SIMD-suoritin toimisi tehottomasti ehtolauseissa.
Tehokas ohjelman suoritus SIMD-pohjaisesti 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 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. Rajoituksena MMX-käskykanta on toteutettu vain kokonaislukulaskentaan. MMX-laajennuksessa 3DNow! tuli mukaan liukulukuoperaatiot.
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 alunperin tietysti peräisin samasta jaetusta ohjelman fyysisestä muistista, joten 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 liukulukulaskennalle 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 yleisissä tarkoituksissa kuten 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 (ohjausosan) ominaisuuksia kuin mitä yleiskäyttöinen suoritin 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 yksinkertainen osa monimutkaisen suorittimen mikroarkkitehtuurissa.
Suorittimen toimintaa enemmänkin hallitsevat rinnakaiset osajärjestelmät, liukuhihnat ja niitä heijastavat käskykannat, ohjausosien moninaiset ja -mutkaiset toteutukset ennustamisiin sekä välimuistit optimoimassa muistiosoituksia eri tasoilla.
Anna palautetta
Kommentteja materiaalista?