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 | 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ä!
Paikallisuusperiaate¶
Tähän asti kurssilla muistiosoitus on ollut suoraa (engl. direct access), jossa ohjelma käyttää (tai muodostaa laskennallisesti) muistiosoitteen virtuaalimuistiin. Virtuaalimuistista kohta lisää, mutta idea on, että ohjelman oma muistialue näyttää sille samalta riippumatta siitä missä se fyysisesti sijaitsee.
Datan sijoitusta muisteihin hallitsee muistiviittausten paikallisuuden periaate (engl. principle of locality / locality of reference), joka tarkoittaa sitä, että minä tahansa ajahetkenä ohjelma tarvitsee vain pientä osaa sille varatusta muistista. Viittausten paikallisuutta voidaan tarkastella kahdesta eri näkökulmasta:
- Ajallinen (engl. temporal locality): samoihin muistiosoitteisiin viitataan usein (säännöllisesti)
- Avaruudellinen (spatial locality): muistiosoitukset osuvat usein lähekkäisiin osoitteisiin
Nyt siis pyrkimys on pitää välimuisteissa (ja virtuaalimuistin tapauksessa) keskusmuistissa vain se eniten viitattu osa ohjelman tarvitsemasta datasta.
Kun ohjelmamme tekee muistiosoituksen, tarkistetaan ensin muistihierarkian läpi mistä haluttu data löytyy. 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 toteuttamiseksi. Tässä lohkon siirto lähemmäksi suoritinta toteuttaa ajallisuusperiatteen (tuorein data lähinnä) ja lohkona siirtäminen (lähekkäiset osoitteet) muistihakujen avaruudellisuus-periaatteen.
Katsotaan aluksi miten muistiosoite rakentuu, jotta voidaan toteuttaa erilaisia muistiratkaisuja. (Virtuaali)muistiosoite on jaettu ja muisti organisoitu kolmeen osaan. Näillä kolmella komponentilla muistihaut voidaan toteuttaa siten, että niiden komponenttien arvoilla tehdään hakuja muistiin ja voidaan nähdä suoraviivaisesti onko haun muistiosoitteen sisältö osoitetussa välimuistissa.
- Tag Identifioi muistilohkon, 2^t lohkoa
- Set: Joukko muistilohkoja, 2^s joukkoa
- Block offset (siirtymä, indeksi): Tavun tai sanan sijainti (indeksi) muistilohkossa, lohkossa on 2^b tavua.
- Jos b=3, lohkossa on 2^3 =8 tavua / sanaa.
Nyt esimerkiksi 32-bittisessä muistiosoitteessa Tag + set voisi 20 bittiä ja Block offset 12 bittiä.
Välimuisti¶
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.
Sääntö on että välimuisti organisoidaan joukkoihin, joissa kaikissa on valittu määrä lohkoja, jotka koostuvat valitusta määrästä tavuja.
Nyt datan hakeminen välimuistista on kolmivaiheinen operaatio, jossa haun muistiosoite puretaan seuraavasti:
- Valitaan s-bittien perusteella joukko
- Tarkistetaan vastaako jokin joukon muistipaikkojen Tageista muistiosoitteemme Tagia.
- Jos vastaa, haluttu data on Tagin osoittamassa lohkossa
- Jos yksikään Tag ei vastaa muistiosoitteen Tagia, joudutaan data hakemaan hierarkian läpi. (No tästä lisää kohta)
- Valitaan lohkosta indeksin osoittama sana/tavu.
Seuraavassa esitetään tapoja jakaa välimuistin muistipaikat osoitusten kesken.
Suora kuvaus¶
Yksinkertaisin osoitustapa on suora kuvaus (engl. direct mapped) jossa muistiosoite kuvataan välimuistiin sellaisenaan. Tässä osoitustavassa on n kpl joukkoja, joissa on yksi lohko. Nyt siis lohko voidaan kuvata vain yhteen välimuistin muistipaikkaan.
Kuvassa yllä on tehty kolme muistiosoitusta (esimerkin vuoksi), joiden data on haettu välimuistiin:
01 000 001
, jossa s=000, t=01 ja b=00111 010 010
, jossa s=010, t=11 ja b=01000 101 000
, jossa s=101, t=00 ja b=000
Huomataan, että 2-bittisellä tagilla voisimme osoittaa neljää lohkoa, mutta muisti on organisoitu niin että joukossa on vain yksi lohko. Tästähän nyt seuraa vain, että jokainen välimuistin muistipaikka on jaettu useamman lohkon kesken.
Nyt t-bittien määrä kertoo montako lohkoa voidaan osoittaa
lohkojen määrä = 2^t
. Esimerkissä t-bittejä on 2, jolloin seuraavat muistilohkot (8-bittinen muistiosoite) jakavat välimuistin tämän muistipaikan.Tag Set Block --- --- ----- 00 000 xxx 01 000 xxx 10 000 xxx 11 000 xxx
Tästä johtuen, haku osoitteeseen
00 000 000
päivittäisi välimuistin ensimmäisen muistipaikan (rivin) sisältöä.Välimuistin muistipaikan Valid-bitti kertoo, että välimuistin muistipaikkaan on haettu jokin arvo. Muutenhan muistipaikan osoitteessa ja datassa oletusarvot 0 voitaisiin tulkita haetuksi arvoksi..
Assosiatiivinen välimuisti¶
Suoraan kuvatussa välimuistissa jokaisella lohkolla on vain yksi paikka välimuistissa, jonne se voidaan kuvata. Tämä saattaa johtaa tehottomaan välimuistin käyttöön, jos 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ä lohko voidaan sijoittaa mihin tahansa tai rajattuun joukkoon välimuistipaikkoja.
Ääritapaus on täysin assosiatiivinen (engl. fully associative) välimuisti, jossa on yksi joukko, jossa ovat kaikki lohkot. Tämä seurauksena muistiosoite käsitellään niin, ettei siinä ole joukon s-bittejä ollenkaan, vaan ne ovat osa tagin t-bittejä. Nyt lohkon haussa joudutaan käymään läpi kaikki välimuistin tagit lohkon löytämiseksi. Syy miksi tälläinen ratkaisu on olemassa, on että hakua välimuistiin voidaan ohjelmallisesti optimoida hyvinkin monimutkaisilla algoritmeilla.
Välimuoto kahdesta esitetystä kuvauksesta on E-assosiatiivinen välimuisti (engl. E-way set-assosiative cache), jossa välimuistin joukoissa on useampi lohko. Nyt data voidaan tallettaa mihin tahansa joukon lohkoista. Nimitys välimuistille tulee joukon lohkojen lukumäärän
E
perusteella. Esimerkiksi, jos lohkoja on kaksi per joukko eli E=2
, puhutaan 2-assosiatiivisestä välimuistista.Datan hakemiseksi välimuistista joudutaan tehdä haku kaikkiin joukon lohkoihin.
Okei.. mutta mitä hyötyä assosiatiivisestä välimuistista on?
Ajatellaanpa ylläolevaa esimerkkimuistiosoitusta
00 000 000
. Suorassa kuvauksessa tämä osoitus päivitti joukon mukaista ainoasta mahdollista välimuistipaikkaa, jossa oli jo aiemman muistiosoituksen data. Nyt kuvan 2-assosiatiivisessä välimuistissa molemmat arvot mahtuvat samaan joukkoon, kun välimuistin päivitys tehdään niin, että pyritään viemään muistiosoitus joukon tyhjiin lohkoihin välimuistissa. Eli samojen s-bittien, mutta eri t-bittien osoittamat lohkot mahtuvat yhtaikaa välimuistiin. Ts. muistiosoitukset käyttömuistiin vähenee, kun päällekirjoitukset vähenee. Huomataan, että itseasiassa suora kuvaus voidaan teoriassa käsittää 1-assosiatiivisena välimuistina, jossa joukon koko on yksi lohko.
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 virtuaalimuistista.
- Suoran kuvauksen välimuistissa lohkon valinnassa ei ole vaihtoehtoja, koska indeksillä 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: Tietenkin jos joukossa on vapaita lohkoja, ne pyritään ensin täyttämään uudella datalla.
- Satunnainen: Valitaan korvattava lohko satunnaisesti.
- Least Frequently Used (LFU): Valitaan lohko, johon on viitattu vähiten. Toteutuksessa vaaditaan kirjanpitoa ja kontrollilogiikkaa.
- Least Recently Used (LRU): valitaan lohko, johon viittaamisesta on kulunut kauiten aikaa.
Tässä on huomioitava, että ennenkuin uusi data haetaan välimuistiin, täytyy muistipaikassa mahdollisesti oleva aiempi data kirjoittaa takaisin käyttömuistiin.
Datan tallentamiseen välimuistista käyttömuistiin 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 ja käyttömuistin sisältö voi hetkellisesti poiketa toisistaan!
Virtuaalimuisti¶
Moderneissa tietokoneissa ohjelmalle ei itseasiassa näy, missä sen käyttämä muisti fyysisesti sijaitsee. Käyttöjärjestelmä tarjoaa ohjelmalle sen oman muistiavaruuden virtuaalimuistin, jossa datalle on virtuaaliset muistiosoitteet, jotka sitten tulkitaan fyysisiksi muistiosoitteiksi ennen muistiosoitusta. Käyttöjärjestelmän palvelut huolehtivat virtuaalimuistin hallinnasta ja suorittavat muistioperaatiot. Prosessorissa voi olla myös MMU-piirejä (engl. Memory Management Unit) jotka huolehtivat operaatioista ja muistien hallinnasta.
Ohjelman näkemä virtuaalimuisti jakaantuu keskusmuistin ja massamuistin kesken, niin että ohjelmalle muistialue näyttää yhtenäiseltä. Voidaan sanoa, että käyttömuisti (RAM) ikäänkuin toimisi välimuistina massamuistissa olevalle datalle.
- Näin virtuaalimuistilla voidaan tarjota ohjelmille isompi muistialue kuin mitä keskusmuistissa olisi.
- Tietysti virtuaalimuisteissa noudatetaan paikallisuusperiaatteita, mutta huomattavasti isommassa mittakaavassa.
- Toiseksi voidaan jakaa keskusmuistia samanaikaisesti ajettavien ohjelmien kesken, kun yksi ohjelma vie sitä vähemmän. (Muistetaan, että ohjelmat yleensä tarvitsevat hetkellisesti vain pienen osan koko muistiavaruuttaan.)
Virtuaalimuisti jaetaan sivuihin (engl. page), ihan kuten välimuisti jaettiin lohkoihin. Tyypillisesti moderneissa tietokoneissa sivun koko on 4-64KB nykyään, tosin sulautetuissa järjestelmissä jäädään alle 1KB.
Virtuaalimuistin rakenne on täysin assosiatiivinen, eli sivu voidaan asettaa minne tahansa käyttömuistissa. Nyt sivujen hallinta yksinkertaistuu ja voidaan tehdä ohjelmallisesti, koska massamuistin haku on hidasta jona aikana ehditään tehdä monimutkaisiakin operaatiota.
Muistiosoitukset¶
Muistiosoitteen kääntäminen virtuaalisesta fyysiseksi tapahtuu seuraavasti. Virtuaalimuistiosoite voi olla hyvinkin iso, jolloin se antaa ohjelmalle illuusion isommasta muistiavaruudesta.
Oletetaan 32-bittinen virtuaalinen muistiosoite, jossa Block offset on 12 bittiä. Tällä saadaan muistisivun koko
2^12 = 4KB
. 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.Yleisesti virtuaalimuistin sivun haku on hidas operaatio, koska sivu pitää hakea RAM-muistista välimuistien sijaan. Tähänkin on esitetty hakua nopeuttavia tekniikoita, ts. esittelemällä muistinoperaatioille lisää rekistereitä ja kontrollilogiikkaa.
Paikallisuusperiaatteen mukaan, fyysiseksi muistiosoitteeksi käännettyä virtuaalimuistin osoitetta tarvitaan usein, joten ne olisi hyvä ottaa valmiiksi talteen. Tätä varten suorittimissa on uusi rekisteri (tai itseasiassa välimuisti) TLB (engl. Translation lookahead buffer), joka pitää sisällään jo käännetyt virtuaalimuistin sivuosoitteet. 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.
Uusi komponentti on Sivutaulukko (engl. Page table) eli muistissa oleva taulukko, joka pitää sisällään RAM-muistissa olevat massamuistin sivujen osoitteet. Pyrkimys on siis nopeuttaa muistiosoituksia massamuistiin ja osoitteiden haut voidaan tehdä sivutaulukkoon koko RAM-muistin läpikäymisen sijaan. Tämä voidaan ajatella niin että käyttömuisti on välimuisti massamuistille.. Jotta asia ei olisi yksinkertaista, myös sivutaulukkoja voi olla useita hierarkisesti..
Muistiosoitteen käännosoperaatio näitä komponentteja 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.
Virtuaalimuistiosoituksen huti on hidas operaatio, kun dataa massamuistista asti. Johtuen fyysisen muistin hitaudesta, virtuaalimuistin sivun koko on iso, jopa 32 / 64KB, jotta saadaan haettua kerralla paljon dataa nopeampaan muistiin.
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.
Osumasuhde¶
Muistinkäsittelyssä pyrimme siis optimoimaan hakuja paikallisuusperiaatteen mukaan, joka heijastuu välimuistien kokoon ja organisointiin. Apuna tässä voidaan käyttää laskennallisia parametreja.
Muistiosoituksille on määritelty laskennallinen mittari osumasuhde, joka tarkoittaa 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. Mitä isompi h
, 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
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?