Välimuisti

Muistihierarkia

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.

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.

Tyypillinen välimuistirakenne nykytietokoneessa

Suorittimen 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 mahdotonta.
Ensimmäisen eli L1-tason välimuisti on jaettu tyypillisesti erillisiin data- ja ohjelmavälimuisteihin, joista voidaan lukea samanaikaisesti (Harvardin arkkitehtuuri), ja molemmat ovat kooltaan tyypillisesti 16–64 kibitavua. Tämän välimuistin viive on alhainen, noin 2–4 kellojaksoa, ja se on hyvin tiukasti integroitu prosessorin ytimeen. 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 ja lohkon koko on 32–128 tavun luokkaa.
Prosessorin kanssa samalla piirillä on yleensä myös L2-tason välimuisti, joka on kuitenkin löyhemmin integroitu itse prosessoriytimeen; jos prosessoripiiri on niin sanottu moniydinprosessori eli samalla piirillä on useampi suoritin, saattaa L2-välimuisti olla jaettu prosessoriytimien kesken. L2-välimuisti on tyypillisesti kooltaan  256–4 096 kibitavua ja viiveeltään 10–20 kellojaksoa. 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

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.
Välimuisti nousi tärkeäksi 1980-luvun lopulla muistien nopeuden jäätyä suorittimien nopeuskehityksestä jälkeen uusien liukuhihnoitettujen RISC-prosessoreiden alkaessa saavuttaa sekä suurempia kellotaajuuksia että selvästi aiempia prosessoreita parempaa suorituskykyä.
PC-puolella ensimmäinen välimuistin sisältänyt suoritin oli Intel 80486. Siinä oli itse piirillä 8 kiB L1-välimuistia, ja 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.

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.

WWW-selaimen välimuisti

WWW-selain tallettaa netistä ladattuja tiedostoja koneen muistiin tai kovalevylle. Kun sama www-sivu 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.