Välimuisti
Wikipedia
Välimuisti eli cache on tietokoneen muistia, johon puskuroidaan dataa.
Välimuistin tehtävänä on olla pieni nopea muisti, jossa pyritään pitämään koneen muistin datasta sellaista osaa, jota tullaan pian tarvitsemaan, ja siten nopeuttamaan tietokoneen toimintaa koska tämä data pystytään lukemaan välimuistista nopeammin kuin hitaammasta varsinaisesta muistista.
Sisällysluettelo |
[muokkaa] 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ä muistiin hierarkia, jossa mahdollisimman nopeassa muistissa mahdollisimman lähellä prosessoria 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ä kohtaa datasta, jota suurimmalla todennäköisyydellä tullaan pian tarvitsemaan, ja hitaimmassa muistissa niitä kohtia datasta, joita käytetään harvemmin.
Suorittimen rekisterit sekä kiintolevyn voi myös ajatella osaksi muistihierarkiaa, vaikka ne toimivatkin eri tavalla; rekistereiden käyttö on määritelty jo ohjelmakoodissa ja kiintolevylle sivutetaan käyttöjärjestelmän toimesta virtuaalimuistin avulla.
Tietokoneohjelmien muistinkäyttö on yleensä toistuvaa ja paikallista, eli jos jotain kohtaa muistista on viime aikoina käytetty, sitä tullaan suurella todennäköisyydellä käyttämään myös uudestaan melko pian. Samoin jos jotain kohtaa muistista on viime aikoina käytetty, myös sen lähellä olevia kohtia muistia käytetään melko suurella todennäköisyydellä melko pian.
Välimuisti perustuu näihin huomioihin. Aina kun muistista ladataan dataa, tarkastetaan ensin löytyykö data välimuistista. Jos data löytyy jo ennestään välimuistista, se ladataan suoraan sieltä. Tätä kutsutaan välimuistin osumaksi. Jos dataa ei löydy välimuistista, se ladataan hitaammasta muistista ja talletetaan samalla välimuistiin. Tätä kutsutaan välimuistihutiksi. Jos välimuisti on täysi, siellä ollut vanhempi data väistyy uuden tieltä. Jos välissä on ollut paljon muita muistioperaatiota, ennen kuin samaa dataa tarvitaan uudelleen, data ei enää olekaan välimuistissa ja pitää taas uudestaan ladata hitaammasta muistista.
Koska myös lähellä edellisten muistioperaatioiden käyttämiä osoitteita tullaan suurella todennäköisyydellä uudelleen, välimuistiin tallennetaan yleensä hiukan suurempi alue ladatun osoitteen ympäriltä. Tällöin myös lähellä oleviin muistiosoitteisiin viittaavat muistihaut voivat osua välimuistiin, vaikka kyseisestä osoitteesta ei dataa lähiaikoina olekaan ladattu.
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 aina sen mukaan, millaista koodia ajetaan.
[muokkaa] 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
[muokkaa] Koko
Suurempaan välimuistiin mahtuu luonnollisesti enemmän dataa, jolloin välimuistihuteja tapahtuu harvemmin. Suuren välimuistin huonona puolena on, 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.
[muokkaa] Assosiatiivisuus
Assosiatiivisuudella tarkoitetaan sitä, kuinka vapaasti muistissa olevaa dataa voidan sijoittaa välimuistiin; suorasijoittavan välimuistin tapauksessa jokaista fyysistä osoitetta kohden on olemassa vain yksi mahdollinen välimuistin kohta, jossa data voi olla, täysassosiatiivisessa välimuistissa mikä tahansa fyysinen kohta muistia voi olla missäpäin tahansa välimuistia. Yleensä käytetään näiden välimuotoa joukkoassiatiivista välimuistia, jolloin jokaiselle fyysiselle osoitteelle on esim. 4 tai 8 mahdollista paikkaa välimuistissa.
Assosiatiivisuutta kasvattamalla pystytään vähentämään huteja, mutta toisaalta tällöin vaadittava monimutkaisempi hakulogiikka hidastaa välimuistin toimintaa. Suorasijoittava välimuistin 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.
[muokkaa] 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. Ja 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.
[muokkaa] Korvauspolitiikka
Jos välimuisti ei ole suorasijoittava, eli jokaisella 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.
Eräs 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.
[muokkaa] 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.
Välimuisti voi myös olla kirjoittamatta dataa heti keskusmuistiin, vaan säilöä sen itseensä ja merkitä likainen-bitillä, että data pitää joskus kirjoittaa 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.
[muokkaa] Tyypillinen välimuistirakenne nykytietokoneessa
Välimuisti on tyypillisesti toteutettu SRAM-tyyppisellä muistilla, keskusmuistin ollessa hitaampaa DRAMia.
Nykyaikaisilla prosessoreilla on tyypillisesti keskusmuistin ja prosessorin rekisterien lisäksi kaksi tasoa välimuistia; L1 ja L2. L1-välimuisti on jaettu erikseen data- ja ohjelmavälimuistiin, ja molemmat ovat tyypillisesti 16–64 kibitavua. Tämän välimuistin viive on tyypillisesti 2–4 kellojaksoa ja se on hyvin tiukasti integroitu prosessorin ytimeen; prosessorin käskyn dekoodausyksikkö sekä lataus- ja talletusyksiköt on suoraan pultattu kiinni välimuistiin ja välimuistin väylät suunniteltu täysin näitä silmällä pitäen. L1-välimuistin kirjoituspolitiikkana on useimmiten läpikirjoitus ja lohkon koko on 32–128 kibitavun luokkaa.
Prosessorin kanssa samalla piirillä on yleensä myös L2-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 näille yhteinen. 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 tietokoneissa 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ä.
[muokkaa] 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.
[muokkaa] Muut välimuistit
[muokkaa] Levyvälimuistit
[muokkaa] 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 dataa luetaan levyltä, se luetaan myös tähän kohtaan koneen keskusmuistia. Levyvälimuistin hallinnasta huolehtii koneen käyttöjärjestelmä ja se on toteutettu täysin ohjelmallisesti.
[muokkaa] 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älimuistille ei ole kovin paljon vaikutusta, sillä sen koko on tyypillisesti melko pieni ja käyttöjärjestelmän välimuisti toimii melko hyvin.
[muokkaa] 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.
[muokkaa] DNS-välimuisti
Internetin nimipalvelun eli DNSn 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.
