Hierarkkinen muistiEdit

Hierarkkinen muisti on laitteistooptimointi, jossa hyödynnetään spatiaalisen ja temporaalisen paikallisuuden etuja ja jota voidaan käyttää useilla muistihierarkian tasoilla. Paging hyötyy ilmeisesti ajallisesta ja alueellisesta paikallisuudesta. Välimuisti on yksinkertainen esimerkki ajallisen paikallisuuden hyödyntämisestä, koska se on erityisesti suunniteltu nopeampi mutta pienempi muistialue, jota käytetään yleensä hiljattain viitattujen tietojen ja hiljattain viitattujen tietojen lähellä olevien tietojen säilyttämiseen, mikä voi johtaa mahdolliseen suorituskyvyn kasvuun.

Välimuistissa olevat tietoelementit eivät välttämättä vastaa päämuistissa tilallisesti lähekkäin olevia tietoelementtejä, vaan tietoelementit tuodaan kuitenkin välimuistiin välimuistirivi kerrallaan. Tämä tarkoittaa, että spatiaalinen paikallisuus on jälleen tärkeää: jos yhteen elementtiin viitataan, myös muutama viereinen elementti tuodaan välimuistiin. Lopuksi ajallisella paikallisuudella on merkitystä alimmalla tasolla, koska hyvin lähekkäin viitattuja tuloksia voidaan pitää koneen rekistereissä. Joissakin ohjelmointikielissä (kuten C:ssä) ohjelmoija voi ehdottaa, että tietyt muuttujat säilytetään rekistereissä.

Datan paikallisuus on tyypillinen muistiviittauksen piirre tavallisissa ohjelmissa (vaikka monia epäsäännöllisiä muistin käyttötapoja on olemassa). Se tekee hierarkkisesta muistiasettelusta kannattavaa. Tietokoneissa muisti on jaettu hierarkkisesti, jotta tiedonhakuja voidaan nopeuttaa. Muistihierarkian alemmat tasot ovat yleensä hitaampia, mutta suurempia. Näin ollen ohjelma saavuttaa paremman suorituskyvyn, jos se käyttää muistia sen ollessa välimuistissa muistihierarkian ylemmillä tasoilla ja välttää tuomasta hierarkian ylemmille tasoille muuta dataa, joka syrjäyttää pian tulevaisuudessa käytettävän datan. Tämä on ihanne, eikä sitä joskus voida saavuttaa.

Tyypillinen muistihierarkia (käyttöajat ja välimuistien koot ovat likiarvoja tyypillisistä arvoista, joita on käytetty vuodesta 2013 lähtien keskustelua varten; todelliset arvot ja hierarkian todelliset tasojen lukumäärät vaihtelevat):

• CPU-rekisterit (8-256 rekisteriä) – välitön pääsy, prosessorin sisimmän ytimen nopeudella
• L1 CPU-välimuistit (32 KiB – 512 KiB) – nopea pääsy, kunkin ytimen yksinoikeudella omistaman sisimmän muistiväylän nopeudella
• L2 CPU-välimuistit (128 KiB – 24 MiB) – hiukan hitaampi pääsy, kun muistiväylän nopeus on jaettu kahden ytimen kesken
• L3 CPU-välimuistit (2 MiB – 32 MiB) – vielä hitaampi pääsy, kun muistiväylän nopeus on jaettu vielä useampien saman prosessorin ytimien kesken
• Fyysinen päämuisti (RAM) (256 MiB – 64 GiB) – hidas pääsy, jonka nopeutta rajoittavat prosessorin ja emolevyn muistimoduulien väliset tilalliset etäisyydet ja yleiset laitteistorajapinnat
• Kiekkolevy (virtuaalimuisti, tiedostojärjestelmä) (1 GiB – 256 TiB) – erittäin hidas, johtuen tietokoneen emolevyn ja levylaitteiden välisestä kapeammasta (bitin leveydellä mitattuna), fysikaalisesti paljon pidemmästä datakanavasta, ja hitaan laitteistorajapinnan päälle tarvittavan ylimääräisen ohjelmistoprotokollan vuoksi
• Kaukomuisti (muut tietokoneet tai pilvi) (käytännöllisesti katsoen rajoittamaton) – nopeus vaihtelee hyvin hitaasta erittäin hitaaseen

Nykyaikaisilla koneilla on tapana lukea alemman muistin lohkoja muistihierarkian seuraavalle tasolle. Jos tämä syrjäyttää käytettyä muistia, käyttöjärjestelmä yrittää ennustaa, mitä tietoa käytetään vähiten (tai viimeisimpänä), ja siirtää sen muistihierarkiassa alaspäin. Ennustusalgoritmit ovat yleensä yksinkertaisia laitteiston monimutkaisuuden vähentämiseksi, vaikka ne ovatkin muuttumassa jonkin verran monimutkaisemmiksi.

MatriisikertolaskuEdit

Yleinen esimerkki on matriisikertolasku:

for i in 0..n for j in 0..m for k in 0..p C = C + A * B;

Vaihtamalla j:n ja k:n silmukkasuoritusjärjestystä nopeuslisäys suurissa matriisikertolaskennoissa nousee dramaattiseksi ainakin kielissä, jotka laittavat viimeiseen ulottuvuuteen vierekkäisiä matriisin alkiotietueita. Tämä ei muuta matemaattista tulosta, mutta parantaa tehokkuutta. Tässä tapauksessa ”suuri” tarkoittaa suunnilleen yli 100 000 elementtiä kussakin matriisissa tai niin paljon osoitteellista muistia, että matriisit eivät mahdu L1- ja L2-välimuistiin.

for i in 0..n for k in 0..p for j in 0..m C = C + A * B;

Syy tähän nopeutukseen on se, että ensimmäisessä tapauksessa A:n lukemat ovat välimuistissa (koska k:n indeksi on vierekkäisessä, viimeisessä dimensiossa), mutta B:n lukemat eivät ole sitä, joten välimuistista jää jäljelle jäämisestä aiheutuva rangaistus, joka koskee B:ää. C:llä ei ole merkitystä, koska se voidaan nostaa ulos sisäisestä silmukasta – silmukkamuuttuja siellä on k.

for i in 0..n for j in 0..m temp = C for k in 0..p temp = temp + A * B; C = temp

Toisessa tapauksessa C:n lukemat ja kirjoitukset ovat molemmat välimuistissa, B:n lukemat ovat välimuistissa ja A:n lukema voidaan nostaa ulos sisäisestä silmukasta.

for i in 0..n for k in 0..p temp = A for j in 0..m C = C + temp * B;

Siten toisessa esimerkissä ei ole välimuistitiedoston ohitusrangaistusta sisäisessä silmukassa, kun taas ensimmäisessä esimerkissä on välimuistitiedoston ohitusrangaistus.

Vuoden 2014 prosessorilla toinen tapaus on noin viisi kertaa nopeampi kuin ensimmäinen tapaus, kun se on kirjoitettu C-kielellä ja käännetty gcc -O3:lla. (Puretun koodin huolellinen tarkastelu osoittaa, että ensimmäisessä tapauksessa GCC käyttää SIMD-käskyjä ja toisessa tapauksessa ei, mutta välimuistisanktio on paljon pahempi kuin SIMD-hyöty.)

Temporaalista paikallisuutta voidaan parantaa myös edellä mainitussa esimerkissä käyttämällä tekniikkaa nimeltä blocking. Suurempi matriisi voidaan jakaa tasakokoisiin alamatriiseihin, jolloin pienempiin lohkoihin voidaan viitata (kertoa) useita kertoja, kun ne ovat muistissa.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE) for (kk = 0; kk < SIZE; kk += BLOCK_SIZE) for (jj = 0; jj < SIZE; jj += BLOCK_SIZE) maxi = min(ii + BLOCK_SIZE, SIZE); for (i = ii; i < maxi; i++) maxk = min(kk + BLOCK_SIZE, SIZE); for (k = kk; k < maxk; k++) maxj = min(jj + BLOCK_SIZE, SIZE); for (j = jj; j < maxj; j++) C = C + A * B;

Yllä olevan ratkaisun ajallinen paikallisuus saadaan aikaan, koska lohkoa voidaan käyttää useita kertoja ennen kuin se siirtyy eteenpäin, jolloin sitä siirretään muistiin ja sieltä pois harvemmin. Paikallinen paikallisuus paranee, koska elementit, joilla on peräkkäiset muistiosoitteet, vedetään yleensä yhdessä muistihierarkiassa ylöspäin.