Välimuistin koherenssi ja suorituskyky

Nykyaikaiset suorittimet ovat erittäin nopeita, mutta päämuisti (RAM) on paljon hitaampi. Tämä nopeusero muodostaa pullonkaulan.

Suorittimen välimuistit ovat pieniä ja erittäin nopeita muistialueita, jotka sijaitsevat suoraan suoritinsirulla. Ne toimivat usein käytettyjen tietojen ja käskyjen väliaikaisena tallennuspaikkana ja kuromat umpeen suorittimen ja RAM-muistin välisen nopeuseron.

Välimuistit on järjestetty hierarkiaksi, jossa on yleensä kolme pääasiallista tasoa:

• L1-välimuisti: Pienin (kymmeniä kilotavuja), nopein ja sijaitsee suoraan kunkin suoritinytimen yhteydessä. Tallentaa tiedot ja käskyt, joita ydin tarvitsee juuri nyt.
• L2-välimuisti: Suurempi (satoja kilotavuja), L1-välimuistia hitaampi ja usein ydinkohtainen. Toimii toissijaisena puskurina.
• L3-välimuisti: Suurin (useita megatavuja) ja hitain, mutta silti RAM-muistia nopeampi. Kaikki sirun suoritinytimet käyttävät sitä yhteisesti.

Tietoa ei siirretä välimuistiin eikä sieltä pois tavu kerrallaan. Sen sijaan sitä siirretään kiinteän kokoisina lohkoina, joita kutsutaan välimuistiriveiksi. Tyypillinen välimuistirivin koko on 64 tavua.

Kun suoritin pyytää tietoa, seuraavalta muistitasolta haetaan koko välimuistirivi, joka sisältää kyseisen tiedon. Tämä on suorituskyvyn kannalta olennaista, koska se ennakoi tulevia tietotarpeita.

Kun suoritin tarvitsee tietoa:

• Välimuistiosuma: Jos tieto löytyy välimuistista, kyseessä on ”osuma”. Tämä on erittäin nopeaa, koska suoritin voi käyttää tietoa heti.
• Välimuistihuti: Jos tietoa ei ole välimuistissa, kyseessä on ”huti”. Suorittimen on haettava tieto seuraavalta hitaammalta muistitasolta (L2, L3 tai päämuisti), mikä aiheuttaa huomattavan viiveen.

Assembly-koodin optimoinnissa tavoitteemme on maksimoida välimuistiosumien määrä.

Spatiaalinen paikallisuus tarkoittaa, että jos ohjelma käyttää jotakin muistiosoitetta, se käyttää todennäköisesti pian sen jälkeen myös lähellä sijaitsevia muistiosoitteita. Voitte ajatella asian näin: ”tarvitsemanne tieto sijaitsee usein juuri käyttämänne tiedon vieressä”.

Välimuistirivit on suunniteltu hyödyntämään tätä. Kun yksi tavu ladataan, koko 64 tavun rivi tuodaan välimuistiin, jolloin viereisten tavujen myöhempi käyttö on erittäin nopeaa (välimuistiosumia).

Temporaalinen paikallisuus tarkoittaa, että jos ohjelma käyttää jotakin muistiosoitetta, se käyttää todennäköisesti samaa osoitetta uudelleen lähitulevaisuudessa. Voitte ajatella asian näin: ”äsken käyttämäänne tietoa tarvitsette todennäköisesti pian uudelleen”.

Välimuistit pitävät äskettäin käytetyt tiedot lähempänä suoritinta, mikä nopeuttaa huomattavasti samojen muuttujien tai käskyjen toistuvaa käyttöä.

Assembly-ohjelmoijana voitte jäsentää koodin ja tiedot siten, että välimuistin paikallisuus paranee:

• Tietojen sijoittelu: Sijoittakaa toisiinsa liittyvät tiedot peräkkäin muistiin (esim. struct-rakenteen jäsenet ja taulukon alkiot).
• Käyttötavat: Käyttäkää tietoja peräkkäin sen sijaan, että hyppisitte muistissa paikasta toiseen.
• Silmukoiden optimointi: Käsitelkää pienempiä tietolohkoja, jotka mahtuvat kokonaan välimuistiin.

Tämä vähentää välimuistihuteja ja pitää suorittimen kiireisenä hyödyllisen työn parissa.

Moniytimisessä suorittimessa kullakin ytimellä on omat L1- ja L2-välimuistinsa. Mitä tapahtuu, jos ydin 0 muuttaa muuttujaa, mutta ytimellä 1 on omassa välimuistissaan muuttujasta vanhempi kopio?

Välimuistin koherenssi varmistaa, että kaikilla ytimillä on yhdenmukainen näkymä muistiin. Kun yksi ydin muuttaa jaetussa muistipaikassa olevaa tietoa, muiden ytimien välimuistien kopiot on päivitettävä tai mitätöitävä vanhentuneen tiedon estämiseksi.

Välimuistin koherenssi säilytetään yleensä laitteistoprotokollien, kuten MESI-protokollan (Modified, Exclusive, Shared, Invalid), avulla.

Kun ydin kirjoittaa jaettuun välimuistiriviin, protokolla varmistaa, että muiden ytimien kyseisen rivin kopiot merkitään tilaan ”Invalid”. Jos toinen ydin yrittää tämän jälkeen lukea kyseiset tiedot, seurauksena on välimuistihuti, ja se hakee päivitetyn version muutoksen tehneeltä ytimeltä tai päämuistista.

Tämä ylimääräinen työ voi heikentää monisäikeisten ohjelmien suorituskykyä.

Moniulotteisten tietojen käyttötapa voi vaikuttaa merkittävästi välimuistin suorituskykyyn. x86:n kaltaisissa järjestelmissä 2D-taulukoiden muisti on yleensä järjestetty riviensisijaisesti (ensin ensimmäisen rivin kaikki alkiot, sitten toisen rivin kaikki alkiot ja niin edelleen).

Seuraava käsitteellinen C:n kaltainen esimerkki havainnollistaa periaatetta:

// Good: Row-major traversal (spatial locality)
// Accesses elements contiguously in memory
for (int row = 0; row < ROWS; row++) {
  for (int col = 0; col < COLS; col++) {
    data[row][col]++;
  }
}

// Bad: Column-major traversal (poor spatial locality)
// Jumps across memory for each 'row' increment
for (int col = 0; col < COLS; col++) {
  for (int row = 0; row < ROWS; row++) {
    data[row][col]++;
  }
}

Riviensisijainen lähestymistapa maksimoi välimuistiosumat hyödyntämällä ladattuja välimuistirivejä tehokkaasti.

Olemme tarkastelleet, miten suorittimen välimuistit (L1, L2 ja L3) kuromat umpeen päämuistin ja suorittimen välistä nopeuseroa. Tietoa siirretään välimuistiriveinä, ja välimuistiosumien maksimointi spatiaalisen ja temporaalisen paikallisuuden avulla on suorituskyvyn kannalta keskeistä.

Käsittelimme myös välimuistin koherenssia, joka varmistaa tietojen yhdenmukaisuuden useiden ytimien välillä, vaikka se voikin aiheuttaa synkronoinnin lisäkustannuksia. Näiden käsitteiden ymmärtäminen auttaa kirjoittamaan tehokkaampaa matalan tason koodia.