Välimuisti

Välimuisti (engl. cache) on pieni ja nopea tietokoneen muisti, jonka tehtävä on nopeuttaa toimintaa ja vähentää viiveitä. Välimuistissa pyritään pitämään sellaisten muistipaikkojen sisältöjä, joihin todennäköisesti pian viitataan.

Havainnekuva välimuistin ja keskusmuistin tiedoista.

Muistihierarkia

Tietokoneen muistihierarkiassa välimuisti on lähellä suoritinta, jonka jälkeen tulee keskusmuisti ja muut ratkaisut. Tietokoneen varsinaisen suorittimen lisäksi muilla piireillä kuten grafiikkasuorittimella voi olla omaa muistia sekä omaa välimuistia.

Ihannetapauksessa tietokoneessa olisi käytettävissä suuri määrä hyvin nopeaa muistia, mutta käytännössä tilanne on aina toinen: suurikapasiteettisesta muistista on vaikea tehdä nopeaa, ja nopea muisti on kallista. Tästä syystä on järkevää tehdä muistista hierarkia, jossa mahdollisimman lähellä suoritinta on pienin ja nopein muisti, vähän siitä kauempana vähän suurempi ja vähän hitaampi, ja kaikkein kauimpana suurin ja hitain. Nopeimmassa muistissa pyritään pitämään aina sitä osaa tiedosta, jota suurimmalla todennäköisyydellä tullaan pian tarvitsemaan, ja hitaimmassa muistissa on tallessa kaikki talletetut tiedot. Välimuisti voidaan toteuttaa esimerkiksi SRAM-tekniikalla ja suurempi muisti DRAM-tekniikalla. Pysyvästi tallennetut tiedot puolestaan tallennetaan suurikapasiteettiselle massamuistille.

Suorittimen rekisterit ja massamuistilaitteet kuten kiintolevyt voidaan myös ajatella osaksi muistihierarkiaa, vaikka ne toimivatkin eri tavalla: rekistereiden käyttö on määritelty jo ohjelmakoodissa ja kiintolevylle sivuttamisesta huolehtii käyttöjärjestelmä virtuaalimuistin avulla.

Tietokoneohjelmien muistinkäyttö on yleensä toistuvaa ja paikallista. Tämä tarkoittaa sitä, että jos jotain kohtaa muistista on juuri käytetty, sitä tai sen lähellä olevia muistipaikkoja tullaan suurella todennäköisyydellä käyttämään lähitulevaisuudessa.

Välimuisti perustuu näihin huomioihin. Aina kun muistista haetaan tietoa, tarkastetaan ensin löytyykö tieto välimuistista. Jos tieto löytyy jo ennestään välimuistista, se haetaan suoraan sieltä. Tätä kutsutaan välimuistin osumaksi. Jos tietoa ei löydy välimuistista, se haetaan hitaammasta muistista ja talletetaan samalla välimuistiin. Tätä kutsutaan välimuistihudiksi (engl. cache miss). Jos välimuisti on täysi, siellä ollut vanhempi tieto väistyy uuden tieltä. Jos välissä on ollut paljon muita muistioperaatiota ennen kuin samaa tietoa tarvitaan uudelleen, tieto ei enää olekaan välimuistissa, ja se pitää hakea uudestaan hitaammasta muistista.

Koska edellisten muistioperaatioiden käyttämien osoitteiden lähellä olevia osoitteita tullaan suurella todennäköisyydellä käyttämään, välimuistiin tallennetaan yleensä joitain muistipaikkoja haetun osoitteen ympäriltä. Tällöin myös näihin lähimuistiosoitteisiin viittaavat muistihaut voivat osua välimuistiin, vaikka kyseisestä osoitteesta ei olekaan haettu tietoa hiljattain.

Välimuistin osumien suhdetta kaikkien muistioperaatioiden määrään kutsutaan välimuistin osumatarkkuudeksi. Tämä luku ei ole mikään kiinteä yleispätevä luku, vaan se vaihtelee järjestelmän kuormitusasteen ja ohjelmien käyttäytymisen mukaan.

Suorittimen välimuistin toteutusteknisiä ominaisuuksia

Jotta välimuistista olisi mahdollisimman paljon hyötyä, pitäisi mahdollisimman suuren osan muistihauista osua dataan, joka on välimuistissa. Muita välimuistin suorituskykyyn vaikuttavia tekijöitä ovat välimuistin hakuaika osuman sattuessa sekä hudista seuraava viive. Välimuistin suorituskykyyn vaikuttavat mm. seuraavat seikat

• koko
• assosiatiivisuus
• lohkokoko
• korvauspolitiikka
• kirjoituspolitiikka

Koko

Suurempaan välimuistiin mahtuu luonnollisesti enemmän dataa, jolloin välimuistihuteja tapahtuu harvemmin. Suuren välimuistin huonona puolena on se, että sieltä hakeminen vaatii monimutkaisempaa logiikkaa, joka saattaa hidastaa jokaisen lukuoperaation suoritusta ja siten koko välimuistia. Suuri välimuisti vaatii myös paljon pinta-alaa piiriltä, ja hakunopeuden parantaminen rinnakkaisuutta lisäämällä kasvattaa pinta-alaa edelleen.

Assosiatiivisuus

Keskusmuistiin tehdään viittaus muistipaikan osoitteella. Osoite kertoo, missä muistipaikassa haluttu tieto on. Koska välimuisti on pienempi kuin varsinainen muisti, ei jokaisella keskusmuistin alkiolla voi olla omaa kopiota välimuistissa. Tämän takia käytetään assosiatiivista muistia. Assosiatiivisessa muistissa on kaksi eri tietoa: osoite eli mikä keskusmuistin muistipaikka on kyseessä ja kopio varsinaisen muistipaikan sisällöstä. Kun assosiatiivisesta muistista haetaan tietoa, ei tiedetä, missä assosiatiivisen muistin muistipaikassa tieto on, vaan muistissa olevasta osoitetiedosta päätellään oikea muistipaikka.

Erilaiset assosiatiiviset muistit eroavat toisistaan siinä, kuinka vapaasti keskusmuistissa oleva muistipaikka voidaan sijoittaa välimuistiin: kun täysassosiatiivisessa välimuistissa mikä tahansa keskusmuistin muistipaikka voi olla missä välimuistin muistipaikassa tahansa, suorasijoittavan välimuistin tapauksessa jokaista keskusmuistin osoitetta kohden on olemassa vain yksi mahdollinen välimuistipaikka, jossa data voi olla. Yleensä käytetään näiden välimuotoa eli joukkoassosiatiivista välimuistia, jolloin jokaisella keskusmuistiosoitteella on esimerkiksi 4 tai 8 mahdollista paikkaa välimuistissa.

Assosiatiivisuutta kasvattamalla pystytään vähentämään huteja (eli tilanteita, joissa tieto ei löydy välimuistista), mutta toisaalta tällöin vaadittava monimutkaisempi hakulogiikka hidastaa välimuistin toimintaa. Suorasijoittava välimuisti on kaikkein yksinkertaisin toteuttaa, ja siksi sellaisen kanssa voidaan käyttää erittäin suuria kellotaajuuksia. Täysassosiatiivinen välimuisti tarjoaa parhaan osumatarkkuuden, mutta on hitain. Välimuistin koko vaikuttaa myös siihen, saavutetaanko suurella assosiatiivisuudella etua. Pienissä välimuisteissa suuresta assosiatiivisuudesta on suurin etu, suurissa välimuisteissa taas pienen assosiatiivisuuden mahdollistama nopea toiminta tarjoaa paremman kokonaissuorituskyvyn.

Lohkokoko

Välimuistilohko on pala dataa, joka haetaan aina kerrallaan välimuistiin. Suuresta lohkokoosta on hyötyä, kun dataa luetaan esimerkiksi peräkkäisistä osoitteista. Jo ensimmäisestä osoitteesta lukeminen aiheuttaa myös seuraavassa osoitteessa olevan datan lukemisen välimuistiin, jolloin seuraavasta lukuoperaatiosta seuraa osuma eikä huti. Mitä isompi lohko on, sitä useampi data-alkio on alun perin ladattu välimuistiin, ja sitä pidempään menee, ennen kuin dataa tarvitaan seuraavasta lohkosta, jota ei ole vielä ladattu muistista. Suuren lohkokoon haittapuoli on kasvanut muistikaistan tarve; vaikka muistista haluttaisiin lukea vain yksi tavu, sieltä pitää silti ladata aina kokonainen välimuistilohko. Tämän takia välimuistihudit myös aiheuttavat suuremman viiveen. Nykyisillä prosessoreilla välimuistilinjan koko on luokkaa 32–128 tavua.

Korvauspolitiikka

Jos välimuisti ei ole suorasijoittava, eli jokaiselle muistiosoitteelle on useampi paikka mihin kohtaan välimuistia sen sisältämä data voidaan tallettaa, nousee esiin kysymys, miten valitaan se paikka, mihin kohtaan välimuistia data ladataan.

Välimuistissa on tyypillisesti jotain aiemmin käytettyä dataa, joka pitää heittää pois uuden datan tieltä. Uuden datan tallennuspaikka välimuistissa pitäisi valita siten, että pois heitetään sellaista dataa, jota ei kovin suurella todennäköisyydellä tarvita kovin pian.

Yksi vaihtoehto valintaan on valita sellainen kohta välimuistia, jonka käyttämisestä on kulunut pidemmän aikaa. Tämä kuitenkin vaatii kirjanpidon kaikista välimuistihauista, mikä voi olla epäkäytännöllistä. Toinen, yllättävän toimiva tapa valintaan on yksinkertaisesti arpoa, mikä vanha data poistetaan uuden tilalta välimuistista. Välimuistin koon kasvaessa suureksi eri korvausalgoritmien väliset erot myös tasoittuvat.

Korvattavaa välimuistilohkoa ei myöskään kaikissa arkkitehtuureissa suoraan poisteta, vaan se saatetaan sijoittaa ns. uhrivälimuistiin (engl. Victim Cache), jossa säilytetään viimeksi häädettyjä lohkoja. Joissain tilanteissa tällainen rakenne saattaa vähentää välimuistihuteja huomattavasti. Suurin hyöty uhrivälimuistista saavutetaan ensisijaisen välimuistin ollessa suorasijoittava tai joukkoassosiatiivinen.

Kirjoituspolitiikka

Kun prosessori kirjoittaa dataa muistiin, välimuisti voi toimia kahdella eri tavalla.

Välimuisti voi kirjoittaa datan heti suoraan keskusmuistiin. Välimuistia kutsutaan tällöin läpikirjoittavaksi välimuistiksi (engl: write-through). Datan kirjoittaminen heti muistiin asti saattaa kuitenkin johtaa turhiin kirjoituksiin, esimerkiksi jos samaan osoitteeseen kirjoitetaan monta kertaa peräkkäin.

Jos välimuisti ei kirjoita tietoa suoraan keskusmuistiin, se merkitsee muutetun muistipaikan likainen-bitillä, jotta data osataan kirjoittaa myöhemmin keskusmuistiin. Tätä kutsutaan takaisinkirjoittavaksi välimuistiksi (engl: write-back). Takaisinkirjoittava välimuisti mahdollistaa paremman suorituskyvyn, mutta tekee välimuistikirjanpidosta monimutkaisempaa ja hankaloittaa moniprosessorijärjestelmien toteutusta, koska moniprosessorijärjestelmien pitää tällöin tietää, mitä muut prosessorit ovat omiin välimuisteihinsa kirjoittaneet.

Synkronointi ja yhtenäisyys

Pääartikkeli: Välimuistin yhtenäisyys

Usean suorittimen jaettua muistia käyttävissä tietokoneissa välimuisti on tyypillisesti yhtenäistä, joka tarjoaa yksinkertaisen ja tehokkaan abstraktion muistista ohjelmoijille. Grafiikkaprosessorien (GPU) ja suorittimien (CPU) välillä yhtenäisyyden toteuttaminen on vaikeaa: nämä voivat olla eri valmistajien tekemiä. Muun muassa valikoivaa välimuistia (selective caching) on ehdotettu ratkaisuna. Heterogeeniseen ympäristöön on myös aluekohtainen yhtenäisyys.

Yhtenäisyyden hallintaan on hakemistopohjainen ratkaisu ja väylän haistelu (bus snooping): hakemistorakenne skaalautuu paremmin kuin haistelu, joka vaatii lähetyksen jokaiselle suorittimille; väylän haistelu on yleinen pienissä järjestelmissä.

Tyypillinen välimuistirakenne nykytietokoneessa

vanhan mallinen Athlon 650 MHz Slot-A-suoritinmoduuli. Suorittimen sivuilla olevat piirit ovat ulkoista L2-välimuistia

Suorittimen sisäinen välimuisti on tyypillisesti toteutettu SRAM-tyyppisellä muistilla, keskusmuistin ollessa hitaampaa DRAMia.

Nykyaikaisilla prosessoreilla on tyypillisesti keskusmuistin ja prosessorin rekisterien lisäksi kaksi tai kolme välimuistitasoa. Syynä useampiin välimuistitasoihin on se, että suurikokoisen ja samaan aikaan erittäin nopean välimuistin toteuttaminen on nykyteknologialla erittäin kallista.

Välimuistitasot nimetään L1, L2 ja L3, joista L1 ensimmäisen tason välimuisti ja pienin. L1 on usein jaettu käskyjen ja datan välillä (L1i ja L1d). Suorittimen ytimellä on yksinoikeus L1-tason välimuistiin, kun taas seuraava L2-tason välimuisti voi olla jaettu ytimien kesken.

Ensimmäisen eli L1-tason välimuisti on jaettu tyypillisesti erillisiin data- ja ohjelmavälimuisteihin, joista voidaan lukea samanaikaisesti (Harvardin arkkitehtuuri). L1-tason välimuisti on hyvin lähellä prosessorin ydintä. Prosessorin käskyn dekoodausyksikkö sekä lataus- ja talletusyksiköt on suoraan liitetty L1-välimuistiin ja välimuistin väylät on suunniteltu täysin näitä silmällä pitäen. L1-välimuistin kirjoituspolitiikkana on useimmiten läpikirjoitus.

Prosessorin kanssa samalla piirillä on yleensä myös L2-tason välimuisti. Monta prosessoriydintä sisältävällä L2-välimuisti saattaa olla jaettu prosessoriytimien kesken. L2- ja L1-välimuistien välillä on tyypillisesti 128–256-bittinen väylä, jonka avulla koko välimuistilohko siirtyy verrattaen nopeasti L1-välimuistilinjalle. L2-välimuistin kirjoituspolitiikka on useimmiten takaisinkirjoittava ja lohkon koko on yleensä sama kuin L1-välimuistissakin. L2-välimuistin osuus koko prosessoripiirin pinta-alasta on tyypillisesti noin puolet.

Joissain arkkitehtuureissa on lisäksi vielä suurempaa ja hitaampaa L3-välimuistia, joka on yleensä eri piirillä kuin itse prosessori. L3-välimuisti saattaa myös SRAMin sijasta olla jotain eksoottisempaa DRAM-pohjaista normaalia DRAMia nopeampaa muistityyppiä.

Myös L4-tason välimuistia on joissakin prosessoreissa.

Historiaa

Suurtietokoneet käyttivät välimuistia pitkään ja konsepti tuli suosituksi 1970-luvulla, kun ferriittirengasmuistia korvattiin puolijohteisiin perustuvilla mikropiireillä. Mikropiirit vaativat vähemmän tilaa, mutta tietyt piirit olivat nopeampia, tuottivat enemmän lämpöä ja olivat kallimpia kuin toiset, jotka olivat halvempia ja hitaampia.

DRAM-muisti oli pitkään suorittimien kellotaajuuksiin nähden niin nopeaa, että juuri mitään tarvetta välimuistille ei ollut; pystyttiin tekemään suurikokoinen keskusmuisti, joka ei ollut pullonkaulana prosessorille. Joissain prosessoreissa tosin oli jonkinlaisia puskureita, joihin käskyjä luettiin muistista etukäteen ennen niiden suoritusta, ja näiden puskurien toiminta oli lähellä välimuistin toimintaa.

Varhaiset suorittimien käskykannat pyrkivät pakkaamaan käskyihin mahdollisimman paljon toimintoja, jolloin muistikapasiteetin tarve olisi pieni. RISC-suorittimien myötä syntyi ajattelu yksinkertaisesta käskykannasta, joka olisi erittäinen nopea, mutta lisäsi muistikaistan tarvetta ja riippuu siten välimuistin käytöstä.

Motorola 68020 sisälsi 256 tavun välimuistin käskyille. Motorola 68030 sisälsi 256 tavun datavälimuistin. Seuraavassa Motorola 68040:ssä välimuistia oli 4 kilotavua.

IBM PC -yhteensopivissa ensimmäinen välimuistin sisältänyt suoritin oli Intel 80486. 80486:n ensimmäisissä malleissa oli 8 kilotavun L1-tason välimuisti, joka myöhemmissä versioissa nousi 16 kilotavuun. Useimmilla 486-emolevyillä oli myös 64–256 kiB L2-välimuisti. Mikropiirien integrointitiheyden kasvun ansiosta on ollut mahdollista kasvattaa piirille integroitujen välimuistien kapasiteettia. Koska suorittimien ja muistin välinen nopeusero kasvaa jatkuvasti suuremmaksi, nykyään huomattava osa useiden uusien suoritinpiirien pinta-alasta onkin käytetty välimuistiin tilanteen kompensoimiseksi.

Vuonna 1996 Digital Equipment Corporationin Richard Sites kertoi tietokannan suorituskyvyn vertailusta eri suorittimilla, jossa kaksi erilaista suoritinta käytti suuren osan ajasta muistin odottamiseen. Sites myös arvioi tilanteen vaikeutumista ja muistijärjestelmien suunnittelusta tulevan merkittävin osa mikroprosessorien suunnittelua.

Vuonna 2022 L3-tason välimuistia voi olla 96 megatavua, joka järjestetään pinoksi, jotta muisti sijaitsee fyysisesti lähellä suoritinta.

Muut välimuistit

Levyvälimuistit

Käyttöjärjestelmän levyvälimuisti

Tietokoneen keskusmuistia saatetaan käyttää myös välimuistina tietokoneen levylle. Tällöin käyttöjärjestelmä varaa muistista alueen tätä varten, ja kun tiedosto luetaan levyltä, siitä tehdään samalla kopio keskusmuistiin. Kun tiedostoon viitataan seuraavan kerran, se voidaan lukea nopeammin mikäli se löytyy levyvälimuistista. Levyvälimuistin hallinnasta huolehtii koneen käyttöjärjestelmä ja se on toteutettu täysin ohjelmallisesti. Yleensä käyttöjärjestelmä hyödyntää kaiken ylimääräisen keskusmuistikapasiteetin levyvälimuistina.

Kovalevyn sisäinen välimuisti

Kovalevyillä on myös usein oma pieni kovalevyn ohjauselektroniikan yhteydessä oleva välimuisti. Tätä käytetään lähinnä kirjoituspuskurina josta kovalevyn elektroniikka voi kirjoittaa datan fyysiselle levypinnalle optimaalisemmassa järjestyksessä; lukuoperaatioiden nopeuteen kovalevyn sisäisellä välimuistilla ei ole kovin paljon vaikutusta, sillä sen koko on tyypillisesti melko pieni ja käyttöjärjestelmän välimuisti toimii melko hyvin.

Ohjelmalliset välimuistit

Verkkoselaimen välimuisti

Verkkoselain tallettaa verkosta ladattuja tiedostoja koneen muistiin tai kovalevylle. Kun sama verkkosivu ladataan uudestaan, selain voi lukea sivun ja sen sisältämät kuvat suoraan omasta välimuististaan eikä sen tarvitse hakea niitä verkon yli palvelimelta.

DNS-välimuisti

Internetin nimipalvelun eli DNS:n nimitietoja voidaan myös tallettaa välimuistiin; kun kone haluaa selvittää jonkun koneen IP-osoitteen, se tarkistaa ensin, onko sillä tämä tieto välimuistissaan: jos on, se lukee sen sieltä, jos ei, se suorittaa nimipalvelimelle kyselyn, odottaa vastausta ja vastauksen saatuaan tallettaa nimitiedon välimuistiinsa.

DNS-välimuisti voidaan toteuttaa sekä asiakaskoneella että DNS-palvelimella.

Kirjallisuutta

• Bruce Jacob & Spencer W. Ng & David T. Wang: Memory Systems: Cache, DRAM, Disk. Morgan Kaufmann, 2008. ISBN 978-0-12-379751-3 (englanniksi)

Aiheesta muualla

• Kuvia tai muita tiedostoja aiheesta Välimuisti Wikimedia Commonsissa