Muistihierarkia¶
"We are ... forced to recognize the possibility of constructing a hierarchy of memories, each of which has greater capacity than the preceding but which is less quickly accessible."
- Burks, Goldstine & von Neumann (1946)
- Burks, Goldstine & von Neumann (1946)
Ensimmäisellä luennolla esittelimme yleisen tietokoneen muistihierarkian. Hierarkian ylimmällä tasolla ovat suorittimen sisäiset muistialueet kuten rekisterit ja välimuistit (ja pino). Pyrkimyksenä on säilyttää dataa mahdollisimman lähellä prosessoria suoritustehon maksimoiseksi. Mitä lähempänä prosessoria muisti on, sitä nopeampaa se on, mutta sitä on vähemmän ja se on kalliimpaa (per bitti).
Moderneissa prosessoreissa hierarkian eri tasoilla viiveet jakaantuvat (suunnilleen) seuraavasti:
Muistin tyyppi | Sijaitsee | Viive (~kellojaksoa) |
1. CPUn rekisterit | CPU | 0 |
2. TLB-rekisteri | CPU | 0 |
3. L1-välimuisti: muistilohkoja (64-bit) | CPU | 4 |
4. L2-välimuisti: muistilohkoja (64-bit) | CPU | 10 |
5. L3-välimuisti: muistilohkoja (64-bit) | CPU/ulkoinen | 50 |
6. Virtuaalimuisti | RAM | 200 |
7. I/O-puskurit | RAM | 200 |
8. Kiintolevy | Levy-ohjain | 100.000 |
Huomataan, että jopa välimuisteissa on kymmenkertaisia eroja viiveessä. Tämä johtuu siitä, että moderneissa suorittimissa tasojen L1 ja L2 välimuistit ovat yleensä integroitu suorittimeen ja L3 on suorittimesta ulkoinen. Tämä heijastuu myös välimuistien kokoon eli (hieman vanhahtavasti) L1- ja L2-tasojen välimuistien koko on ollut luokkaa kiloja - kymmeniä kilotavuja, kun taas L3-tason välimuistit ovat (olleet) muutaman megatavun kokoisia. Tyypillisesti sulautetuissa järjestelmissä jäädään alle 1KB kokoisiin välimuisteihin.
Paikallisuusperiaate¶
Kurssilla muistiosoitus on ollut suoraa (engl. direct access) tai epäsuoraa (engl. indirect), jossa ohjelmassa on suoraan annettu muistiosoite tai suoritin laskennallisesti muodostaa osoitteen keskusmuistiin. Keskusmuistista on sitten tuotu hakuja tehdessä, ei pelkästään yksittäisiä muistipaikkojen arvoja, mutta kokonaisia muistilohkoja lähemmäksi välimuisteihin.
Muistiosoituksia tutkiessa on havaittu, että datan sijoitusta muisteihin hallitsee muistiviittausten paikallisuuden periaate (engl. principle of locality / locality of reference), joka tarkoittaa sitä, että minä tahansa ajanhetkenä ohjelma tarvitsee vain pientä osaa sille varatusta muistista ja johon viittaukset kohdistuvat. Tätä paikallisuutta tarkastellaan kahdesta näkökulmasta:
- Ajallinen (engl. temporal locality): samoihin muistiosoitteisiin viitataan usein (säännöllisesti)
- Avaruudellinen (engl. spatial locality): muistiosoitukset osuvat usein lähekkäisiin osoitteisiin
-> On siis hyödyllistä on pitää välimuisteissa vain se eniten viitattu osa ohjelmalle varatusta muistista.
Kun ohjelmamme tekee muistiosoituksen, tarkistetaan siis ensin välimuistihierarkian läpi löytyykö haluttu data välimuisteista. Kun data on löydetty, siirretään muistista aina lohko dataa hierarkian läpi. Hierarkian eri tasoilla on eri määrä muistia, joten tallennettavan lohkon koko pienenee ja sisältö tarkentuu suoritinta lähestyessä paikallisuusperiaateiden mukaisesti. Lohkon siirto lähemmäksi suoritinta toteuttaa ajallisuusperiatteen (tuorein data lähinnä) ja lohkona siirtäminen (lähekkäiset osoitteet) avaruudellisuusperiaatteen.
Osumasuhde¶
Muistinkäsittelyssä pyrimme siis optimoimaan hakuja paikallisuusperiaatteen mukaan, joka heijastuu välimuistien kokoon ja organisointiin. Esimerkkinä, silmukkarakenteiden koko koodi ja data olisi hyödyllistä olla välimuistissa kokonaisuudessaan!
Välimuistin toteutuksessa apuna voidaan käyttää laskennallisia parametreja. Muistiosoituksille on määritelty mittari osumasuhde, joka tarkoitaa välimuistiin osuneiden muistiosoitusten suhdetta kaikkiin muistiosoituksiin. Esimerkiksi, osumasuhde
h=95%
tarkoittaa, että 95% osoituksista haettu data oli jo välimuistissa ja 5% piti hakea alemmilta hierarkian tasoilta. Eli mitä isompi osumasuhde, sen vähemmän hitaita muistiosoituksia on ja sitä nopeampaa ohjelma toimii. Osumasuhteesta
h
voidaan laskea keskimääräinen muistioperaation aika (engl. Average Memory Access Time) seuraavastiTässä
Tcycle
on kellojakson aika ja Tmiss
hakuaika muistista:Esimerkiksi, jos kellojakso on 1ns ja muistin lukuoperaatio 20ns osumasuhteella 95%:
Tamat = 1ns + (1 - 0.95) * 20ns = 2ns
Muistiosoitukset¶
Aiemmin kerrottiin, että suorittimelta lähtevältä osoiteväylältä luetaan muistiosoite ja sitä vastaava sana haetaan muistista. Tästä käytetään nimitystä lineaarinen muistiosoitus, jossa osoite käsitellään sellaisenaan. Moderneissa tietokoneissa kuitenkin käytetään muistiosoituksessa apuna sivutusta (engl. paging), jonka avulla voidaan osoittaa suurempaa muistialuetta, kuin mihin muistin osoiteväylän leveys antaisi myöten. Osoitteen "ylimääräiset" bitit saadaan esim. rekisterien ja erityisten osoitemuistipaikkojen avulla ja ne esitetään sivutaulussa (engl. page table).
Esimerkki. x86-pohjaisissa tietokoneissa muisti on segmentoitu osiin/lohkoihin käyttötarkoituksen mukaan. Joukko rekistereitä (CS-GS, kts. kuva johdanto-materiaalissa) varataan muistiosoitteille, jotka kertovat mistä kukin osa alkaa. Osille on sitten on määritelty "tyyppi", eli esimerkiksi segmenttiin CS (engl. code segment) sijoitetaan ohjelmakoodi ja segmenttiin DS (engl. data segment) viedään ohjelman data.
Katsotaan aluksi miten sivutuksessa muistiosoite rakentuu. Osoite on jaettu kolmeen osaan: sivutaulujen sisällysluettelo (sijainti muistissa), sivutaulu ja sanan osoite sivulla. Näillä komponentilla osoitteesta jo nähdään ohjauslogiikassa suoraviivaisesti onko data valmiina välimuistissa. Lisäksi välimuisti voidaan organisoida eri tavoin (tästä lisää alla..)
Kuvassa 32-bittinen osoite on jaettu niin, että sivutaulun osoittamiseen sisällysluettelossa on varattu 10 bittiä, sivun sijaintiin taulussa toiset 10 bittiä ja haetun sanan sijaintiin sivulla 12 bittiä. Muistin koko olisi nyt siis
2^32 = 4GB
, jossa sivuja on 2^20 = 1000000
ja yhden sivun koko 2^12 = 4KB
. Välimuistin rakenne¶
Kuvassa muistiosoitteen osat kuvattuna välimuistin organisoinnin näkökulmasta (=oppikirjassa käytetyllä esityksellä).Sääntö on että välimuisti organisoidaan joukkoihin, joissa kaikissa on valittu määrä lohkoja, jotka koostuvat valitusta määrästä sanoja.
- Tag Lohkon osoite/id, kun joukossa lohkoja on 2^t
- Set: Joukko muistilohkoja, kun joukkoja on 2^s
- Block offset (siirtymä, indeksi): Sanan sijainti lohkossa, lohkon koko 2^b sanaa.
Nyt esimerkiksi ym. kaltaisessa 32-bittisessä muistiosoitteessa Set + Tag voisi olla 10 + 10 bittiä ja Block offset 12 bittiä.
Ylläoleva muistiosoitteen rakenne osoittautuu hyödylliseksi välimuisteja käytettäessä. Koska välimuisti on kooltaan aina pienempi kuin alempi taso hierarkiassa, joudutaan välimuistin muistipaikkoja jakamaan hakujen kesken. Seuraavassa esitetään tapoja jakaa välimuistin muistipaikat osoitusten kesken.
Suora kuvaus¶
Yksinkertaisin osoitustapa on suora kuvaus (engl. direct mapped) jossa on n kpl joukkoja, joissa on vain yksi lohko. Nyt siis kaikki joukon sisältämät lohkot voidaan kuvata vain yhteen (väli)muistipaikkaan ja Tag-bitit identifioivat mikä lohko on kyseessä.
(Välimuistin muistipaikan Valid-bitti kertoo, että välimuistin muistipaikkaan on haettu jokin arvo. Muutenhan muistipaikan osoitteessa ja datassa oletusarvot 0 voitaisiin tulkita välimuistiin haetuksi arvoksi..)
Esimerkki. Kahdella tag-bitillä voisimme osoittaa neljää lohkoa, jotka menevät samaan välimuistipaikkaan. Kun päivitämme välimuistia, tag-bitit muuttuvat sen mukaan mihin joukkoon osoitamme.
Tag Set Block --- --- --- 00 000 110 01 000 101 10 000 000 11 000 001
Etuna suorassa kuvauksessa on, ettei joukkoa tarvitse etsiä lohkon löytämiseksi (kts. alla) vaan se saadaan laskettua osoitteesta suoraan. Haittapuolena taas, että ainut joukon muistipaikka jaetaan lohkojen kesken.
Assosiatiivinen välimuisti¶
Suorassa kuvauksessa jokaisella lohkolla on vain yksi paikka välimuistissa. Tämä saattaa johtaa tehottomaan välimuistin käyttöön, joskun samaa välimuistipaikkaa käytetään jatkuvasti ja muut välimuistipaikat ovat vähemmällä käytöllä.
Assosiatiivinen välimuisti ratkaisee tämän ongelman, niin että joukossa on useampi välimuistipaikka lohkoille ja osoite voidaan sijoittaa mihin tahansa joukon muistipaikoista.
Yleisesti tällainen välimuisti on E-assosiatiivinen välimuisti (engl. E-way set-assosiative cache), jossa välimuistissa on useampi muistipaikka lohkoille per joukko. Data voidaan tallettaa mihin tahansa lohkoista. Nimitys välimuistille tulee joukon lohkojen lukumäärän
E
perusteella. Kuvassa yllä lohkoja on kaksi per joukko, jolloin E=2
ja puhutaan 2-assosiatiivisestä välimuistista. Datan hakemiseksi välimuistista joudutaan tekemään haku kaikkiin joukon välimuistipaikkoihin, mutta niitä on rajattu määrä. Oikeissa muistitoteutuksissa lohkoja voi olla esimerkiksi 1024 kappaletta.
Nyt suora kuvaus voidaan käsittää 1-assosiatiivisena välimuistina, koska joukossa mahdollisia muistipaikkoja on vain yksi. Toinen ääritapaus on täysin assosiatiivinen (engl. fully associative) välimuisti, jossa on yksi joukko sisältää kaikki lohkot. Nyt muistiosoitteessa ei ole set-bittejä ollenkaan, vaan ne ovat osa tag-bittejä. Haussa sitten joudutaan vertailemaan kaikki välimuistin tagit lohkon löytämiseksi. (Syy miksi tälläinen ratkaisu on olemassa, on että tällaista hakua välimuistiin voidaan nykyään ohjelmallisesti optimoida monimutkaisilla hakualgoritmeilla.)
Välimuistin päivittäminen¶
Jos haluttua dataa ei löydy välimuistista, tapahtuu cache miss (Suomennos vaikkapa huti :-) Nyt data joudutaan hakemaan seuraavan tason välimuistista tai lopulta keskusmuistista.
Muistihausta seuraa välimuistin päivitys, joka voidaan tehdä useilla eri tavoin:
- Suoran kuvauksen välimuistissa osoitettavan lohkon päälle kirjoitetaan aina.
- Assosiatiivisen välimuistin päivitys on työläämpää. Kirjoitettavan välimuistilohkon valinnassa pyritään optimoimaan paikallisuus-periaate. Menetelmiä on seuraavia:
- Vapaa lohko: Jos joukossa on vapaita lohkoja, ne pyritään ensin täyttämään uudella datalla.
- Satunnainen: Valitaan päällekirjoitettava lohko satunnaisesti.
- Least Frequently Used (LFU): Valitaan lohko, johon on viitattu vähiten. Toteutuksessa vaaditaan kirjanpitoa.
- Least Recently Used (LRU): valitaan lohko, johon viittaamisesta on kulunut kauiten aikaa. Vaatii myös kirjanpitoa.
Mutta, ennenkuin uusi data haetaan välimuistiin, täytyy muistipaikassa (mahdollisesti) oleva vanha data kirjoittaa takaisin käyttömuistiin, koska ohjelma on saattanut päivittää sitä. Tätä varten välimuistipaikoissa on useita bittejä, jotka kertovat välimuistipaikan tilasta. Ylläoleva valid-bitti on yksi, mutta bitti voivat kertoa esimerkiksi sisällön muuttumisesta ja datan tuoreudesta. jne.
Datan tallentamiseen välimuistista hierarkiassa alaspäin ja keskusmuistiin on kaksi tapaa:
- Läpikirjoitus (engl. write-through): Välimuistiin siirrettävä data kirjoitetaan samalla läpi hierarkian kaikkien tasojen.
- Etuna on yksinkertainen toteutus.
- Haittana on merkittävästi pitempi kirjoitusaika. Massamuistiin (esim. kovalevylle) kirjoitus voi olla jopa 100.000 kertaa hitaampaa..
- Voidaan myös tallentaa läpikirjoitettava data puskuriin, joka myöhemmin kirjoitetaan kerralla muistiin.
- Takaisinkirjoitus (engl. write-back): Data kirjoitetaan muistiin vain kun sitä vastaava välimuistin lohko päivitetään.
- Etuna on, että datan kirjoitus välimuistiin on nopeaa ja usean eri muuttuneen datan päivitys lohkossa vaatii yhden kirjoitusoperaation muistiin.
- Mutta, nyt välimuistin hierarkioiden ja keskusmuistin sisältö voi hetkellisesti poiketa toisistaan!
Toteutuksia¶
Moderneissa PC-koneissa välimuistin kaksi ylintä tasoa L1- ja L2 ovat yleisesti integroitu suorittimeen ja L3-tason välimuisti taas rakennettu erillisistä piireistä. L3-välimuistin koko on merkittävästi suurempi kuin ylempien tasojen.
Kuvassa Intelin Itanium-prosessorin välimuistin rakenne.
Intelin Xeon-prosessorin arkkitehtuurissa L2-tason välimuistille on oma rinnakkainen nopea muistiväylä kuin mitä järjestelmäväylä on. Kun L1-taso on integroitu suorittimeen, saadaan toisen tason välimuistin toiminta näinollen nopeammaksi.
Virtuaalimuisti¶
Moderneissa tietokoneissa ohjelmalle ei itseasiassa näy, missä sen käyttämä muisti fyysisesti sijaitsee ja muistialue voi olla isompi kuin ohjelmalle jaettu keskusmuistin osa. Nyt käyttöjärjestelmä tarjoaa ohjelmalle sen oman muistiavaruuden virtuaalimuistin, joka koostuu fyysisestä keskusmuistista ja ulkoisesta massamuistista, esim. kovalevyllä, niin että ohjelmalle muistialue näyttää yhtenäiseltä.
Virtuaalimuistin datalle on virtuaaliset muistiosoitteet, jotka sitten tulkitaan fyysisiksi muistiosoitteiksi ennen muistiosoitusta. Käyttöjärjestelmän palvelut huolehtivat virtuaalimuistin osoitteiden hallinnasta ja suorittavat muistioperaatiot. Prosessorissa voi olla myös MMU-piirejä (engl. Memory Management Unit) jotka huolehtivat operaatioista ja muistien hallinnasta.
Etuina saadaan siis:
- Virtuaalimuistilla voidaan tarjota ohjelmille isompi muistialue kuin mitä keskusmuistissa olisi.
- Tietysti virtuaalimuisteissa noudatetaan paikallisuusperiaatteita, mutta huomattavasti isommassa mittakaavassa.
- Keskusmuistia voidaan jakaa samanaikaisesti ajettavien ohjelmien kesken sopivassa suhteessa.
- Muistetaan, että ohjelmat yleensä tarvitsevat hetkellisesti vain pienen osan koko muistiavaruuttaan.
Muistiosoitukset¶
Yleisesti virtuaalimuistin osoitus on hidas operaatio, koska data pitää hakea välimuistien kautta pahimmassa tapauksessa massamuistista asti.
Virtuaalimuisti jaetaan sivuihin (engl. page), ihan kuten keskusmuistikin. Virtuaalimuistin rakenne on täysin assosiatiivinen, eli sivu voidaan asettaa minne tahansa keskusmuistissa. Nyt sivujen hallinta voidaan tehdä hardiksen ja laiteohjelmiston yhteistyönä, koska oletuksena massamuistin haku on hidasta, jona aikana ehditään tehdä monimutkaisiakin optimointioperaatiota!
Muistiosoitteen kääntäminen virtuaalisesta fyysiseksi tapahtuu osoitemuunnoslogiikan avulla. Oletetaan 32-bittinen virtuaalinen muistiosoite, jossa Block offset on 12 bittiä. Loput 20 bittiä osoittavat sivun osoitteen (ts. set + tag). Nyt saadaan virtuaalimuistin koko
2^20 * 4KB = 4GB
. Fyysisen muistin koko esimerkissä on kaksi bittiä vähemmän, jolloin fyysisen muistipiirin koko taas olisi 2^18 * 4KB = 1GB
. Virtuaalimuistin ylemmillä biteillä voidaan siis osoittaa valittuun fyysiseen muistiin.Nopea muistiosoitus¶
Nopeutta virtuaalimuistin hakuihin saadaan siis, kun osoitettu muisti on valmiina väli/keskusmuistissa. Nyt paikallisuusperiaatteen mukaan, fyysiseksi muistiosoitteeksi käännettyä virtuaalimuistin osoitetta tarvitaan usein, joten ne olisi hyvä ottaa valmiiksi talteen sivutauluun. Ongelmana on, että huolimatta sivutaulun käyttämisestä, muistiosoituksessa tarvitaan kolme osoitusta muistiin: sivutaulujen sisällysluetteloon, sivutauluun ja fyysiseen muistiin.
Osoituksia voidaan nopeuttaa tallettamalla jo muunnetut osoitteet rekisteriin tai itseasiassa välimuistiin nimeltä TLB (engl. Translation lookahead buffer). Nyt kun muunnettu osoite löytyy TLB:stä, ei muita hakuja tarvitse tehdä. Koska TLB on välimuisti, täytyy siinäkin olla Valid-bitti kertomassa muistipaikassa olevan datan tila. Lisäksi D-bitti (engl. dirty bit) kertoo onko kyseistä virtuaalimuistin sivua ohjelmassa päivitetty, jolloin se pitäisi päivittää takaisin fyysiseen muistiin, ennenkuin tilalle luetaan uusi sivu.
Muistiosoitteen käännosoperaatio TLB:tä hyväksikäyttäen on seuraava:
- Tarkistetaan löytyykö virtuaalimuistin sivun käännös TLB-rekisteristä
- Jos käännös löytyi, haetaan data annetusta fyysisen muistin osoitteesta
- Jos käännöstä ei löydy TLB:stä, mutta se löytyi sivutaulukosta, riittää että päivitetään TLB haun yhteydessä.
- Jos sivua ei löydy sivutaulukostakaan, joudutaan sivu hakemaan poikkeuksen (page fault) kautta massamuistista.
Osoitteita päivitetään perustuen LRU:hun, jolloin TLB-rekisterissä ja sivutaulukoissa on tilabittejä (engl. reference bit) kirjanpitoa varten kertomassa onko ja milloin sivua on viimeksi luettu.
Virtuaalimuistin takaisinkirjoituksessa käytetään massamuistin hitauden takia write-back-menetelmää, eli kirjoittetava data pidetään puskurissa, joka sitten kirjoitetaan fyysiseen muistiin kerrallaan.
Muistiteknologiat¶
Nykyisin käytössä on muutama erilainen muistiteknologia, joilla muistihierarkian eri tasot voidaan toteuttaa.
- SRAM (Static random access memory)
- Muistin hakuaika on vakioitu ja on hyvin lähellä kellojakson aikaa.
- Muistisolut (ts. bitit) koostuvat 6-8 transistorin muodostamasta kiikkupiiristä, joka säilyttää bitin arvon niin kauan kuin laitteessa on virtaa.
- DRAM (Dynamic random access memory)
- DRAMssa muistisolun koostuu transistorista ja kondensaattorista. DRAM on siis halvempaa ja muistipiirit tiiviimpiä.
- Bitin arvo säilyy kondensaattorin varauksen avulla, mutta koska varaus purkautuu ajan myötä, pitää soluja virkistää tietyin väliajoin. Virkistys tapahtuu lukemalla bitin arvo puskuriin ja kirjoittamalla se sitten takaisin. Tämä on jokaista bittiä kohden aikaavievää isoissa muisteissa, joten virkistys tapahtuu muistisolu-riveittäin kerrallaan.
- Virkistys itseasiassa nopeuttaa DRAM-muistin käyttöä, koska nyt bitit voidaan lukea puskurista eikä tarvitse erikseen hakea dataa muistista.
- Myös paikallisuuden kannalta tämä on hyödyllistä, kun vierekkäiset bitit voidaan lukea kerralla.
- SDRAM (Syncronous DRAM): Tässä prosessori ja muistipiiri on synkronoitu erillisellä kellolla ja datansiirto voidaan tehdä purskeissa (engl. burst), eli siirtää enemmän dataa kerralla.
- Flash: perustuu EEPROM-teknologiaan
- Muistisoluille on määritelty maksimimäärä kuinka monta kirjoitusta ne kestävät, esimerkiksi 100.000.
- Käytetään usein sulautetuisa järjestelmissä ohjelmamuistina
- Kiintolevy: (ts. kovalevy)
- Hakuaika (engl. seek time): yleensä 3-13ms
- Datan luku- ja kirjoitusaika riippuu myös pyörimisnopeudesta, jne.
- Siirtonopeudet yleensä 100-200MB/s, mutta oman sisäisen välimuistin kanssa jopa 750MB/s (v.2012)
Lopuksi¶
Kuten materiaalista käy (hyvin?) ilmi, muistinhallinta on kaikenkaikkiaan monimutkainen operaatio moderneissa prosessoreissa monine eri ratkaisuineen, jotka on jaettu softan ja hardiksen kesken.
Taustalla on muistipiirien ja massamuistien osoituksen hitaus, jonka latenssit voivat olla satatuhat-kertaisia.
Anna palautetta
Kommentteja materiaalista?