Välimuisti () 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.
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 (). 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 (), 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
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
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