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). Mitä lähempänä prosessoria muisti on, sitä nopeampaa se on, mutta sitä on vähemmän ja se on kalliimpaa (per bitti). Pyrkimyksenä on siis säilyttää dataa mahdollisimman lähellä prosessoria suoritustehon maksimoiseksi.
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 (laitteiden välimuistit) | 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) Eri tasojen välimuistien koko vaihtelee (kymmenistä) kilotavuista muutaman megatavuun (L3). Tyypillisesti sulautetuissa järjestelmissä jäädään alle 1KB kokoisiin välimuisteihin (jolla saadaan mikrokontrollerin hintaa alas).
Paikallisuusperiaate¶
Kurssilla tähän asti muistiosoitus on ollut suoraa (engl. direct access) tai epäsuoraa (engl. indirect), jossa ohjelmassa on suoraan annettu muistiosoite tai suoritin laskennallisesti muodostaa muistiosoitteen, jolla viitataan keskusmuistiin.
Nyt muistiosoituksia tutkiessa on havaittu, että datan sijoittumista muisteihin hallitsee muistiviittausten paikallisuusperiaate (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 tällöin 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 ohjelma 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 lähemmäksi suoritinta. Samalla, koska hierarkian eri tasoilla on eri määrä muistia, lohkon koko pienenee ja sisältö tarkentuu paikallisuusperiaateiden mukaisesti. Lohkon siirto lähemmäksi suoritinta toteuttaa molemmat ajallisuusperiatteen (tuorein data lähinnä) ja lohkona siirtäminen avaruudellisuusperiaatteen (lähekkäiset osoitteet).
Esimerkki. Silmukkarakenteiden koodi ja data olisi hyödyllistä olla läheisessä välimuistissa kokonaisuudessaan!
Osumasuhde¶
Muistin organisoimisessa hierarkiaan apuna voidaan käyttää laskennallisia parametreja. Yleinen mittari on osumasuhde (merkitään
h
), joka tarkoitaa välimuistiin osuneiden muistiosoitusten suhdetta kaikkiin muistiosoituksiin. Esimerkiksi, osumasuhde
h=95%
tarkoittaa, että 95% osoituksista haluttu data oli jo välimuistissa ja 5% pitää hakea alemmilta hierarkian tasoilta. Eli mitä isompi osumasuhde, sen vähemmän hitaita muistiosoituksia on ja sitä nopeampaa ohjelma voidaan suorittaa. Osumasuhteesta
h
voidaan laskea keskimääräinen muistioperaation aika (engl. Average Memory Access Time):Tässä
Tcycle
on kellojakson aika ja Tmiss
(maksimi)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). Ideana on, että sivuttamalla voidaan osoittaa suurempaa muistialuetta, kuin mihin muistiväylän osoitteen leveys antaisi myöten. Muisti pitää siis jakaa tietyn kokoisiin sivuihin (esim. osoiteväylän leveys tai sitä pienempi). Käyttämättä jääneet tai lisätyt osoitebitit sitten kertovat mistä sivulta dataa haetaan. Nämä bitit saadaan esim. rekisterien ja erityisten osoitemuistipaikkojen avulla ja ne esitetään sivutaulussa (engl. page table). Sivutauluista lisää hetken päästä..
Esimerkki. x86-pohjaisissa tietokoneissa muisti on segmentoitu lohkoihin, joille on annettu tietty käyttötarkoitus. Joukko rekistereitä (CS-GS, kts. kuva johdanto-materiaalissa) varataan muistiosoitteille, jotka kertovat mistä kukin lohko alkaa. Näistä esimerkiksi segmenttiin CS (engl. code segment) sijoitetaan ohjelmakoodi ja segmenttiin DS (engl. data segment) viedään ohjelman data.
Nyt sivutusta hyödyntävä muistiosoite rakentuu kolmesta osasta:
- sivutaulujen sisällysluettelo (sijainti muistissa)
- sivutaulun numero/osoite
- sanan osoite sivulla.
Tässä muistiosoitus menisi niin, että ensin sisällysluettelosta saadaan sivutaulujen osoitteet, sitten haetaan sivutaulu, josta saadaan sivun osoite ja lopuksi sivulta yksittäinen muistipaikka. Kaikki nämä lohkot voivat siis sijaita sikinsokin fyysisessä muistissa.
Kuvassa 32-bittinen (lineaarinen) 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 = 1048576
kappaletta ja yhden sivun koko 2^12 = 4096B
. (Nyt suorittimen ohjauslogiikassa voitaisiin jo nähdä muistiosoitteen osista suoraviivaisesti onko data valmiina välimuistissa, joskun välimuistiin esimerkiksi mahtuu kokonaisia tauluja/lohkoja.)
Välimuistin organisointi¶
Muistinkäsittelyssä pyrimme siis optimoimaan paikallisuusperiaatteita noudattaen, joka heijastuu muistihierarkian organisointiin, ottaen myös huomioon muistien koko, hakuajat, väylänleveydet, ym.
Kuvassa muistiosoitteen osat kuvattuna välimuistin organisoinnin näkökulmasta (=oppikirjassa käytetyllä yleisellä esityksellä). Sääntö on että välimuisti organisoidaan joukkoihin (engl. set), 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.
Esimerkki. ylläkuvatussa 32-bittisessä muistiosoitteessa Set + Tag voisivat olla 10 + 10 bittiä ja Block offset 12 bittiä.
Tälläinen 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 jokaisessa on vain yksi lohko kerrallaan. Idea on, että joukon ainoa muistipaikka jaetaan useiden lohkojen kesken. Tällöin 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. Kun päivitämme välimuistia, Tag-bitit muuttuvat sen mukaan mihin joukkoon osoitamme. Välimuistipaikka pysyy kokoajan samana.
Tag Set Block --- --- --- 00 000 110 01 000 101 10 000 000 11 000 001
Etuna suorassa kuvauksessa on, ettei joukkoa tarvitse erikseen etsiä lohkon löytämiseksi (kts. alla), vaan se saadaan laskettua osoitteesta suoraan. Haittapuolena taas, että muistipaikkoja jataan 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.
Täysin assosiatiivinen välimuisti¶
Nythän 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 yksi joukko sisältää kaikki lohkot. Tälläisessa muistiosoitteessa ei ole Set-bittejä ollenkaan, vaan ne ovat osa Tag-bittejä. Muistiosoitteen haussa sitten joudutaan pahimmillaan vertailemaan kaikki välimuistin tagit lohkon löytämiseksi.
Yksi syy miksi tämä ratkaisu on nykyään olemassa, on että hakua välimuistiin voidaan nykyään ohjelmallisesti optimoida virtuaalimuistin yhteydessä hakualgoritmeilla. Tästä lisää hetken päästä.
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.. (toki tässä voidaan käyttää massamuistille puskureita.)
- 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-prosessorien yleinen välimuistin rakenne.
Intelin Xeon-prosessoriarkkitehtuureissa L2-tason välimuistille on oma rinnakkainen nopea muistiväylä järjestelmäväylän rinnalla. Nyt kun L1-taso on integroitu suorittimeen, saadaan myös 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 lisäksi muistialue voi olla isompi kuin ohjelmalle jaettu keskusmuistin osa. Tällaista muistiavaruutta kutsutaan virtuaalimuistiksi. Virtuaalimuisti koostuu fyysisestä keskusmuistista ja ulkoisesta massamuistista, esim. kovalevyllä, joka on organisoitu sivutuksella ja välimuisteina niin, että ohjelmalle muistialue näyttää yhtenäiseltä.
Virtuaalimuistin kanssa käytetään virtuaalisia muistiosoitteita, jotka ensin tulkitaan fyysisiksi muistiosoitteiksi ennen muistiosoitusta. Tässä käyttöjärjestelmän palvelut huolehtivat virtuaalimuistin osoitteiden hallinnasta ja suorittavat muistioperaatiot tai prosessorissa voi olla myös MMU-piirejä (engl. Memory Management Unit) osana väyläohjausta, huolehtien muistioperaatioista ja muistiavaruuden 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 ajettavien ohjelmien kesken niiden vaatimien resurssien suhteen.
- Tässä on avuksi, että ohjelmat yleensä tarvitsevat hetkellisesti vain pienen osan koko muistiavaruuttaan.
Muistiosoitukset¶
Virtuaalimuisti jaetaan sivuihin (engl. page), ihan kuten keskusmuistikin. Virtuaalimuistin rakenne on täysin assosiatiivinen, eli sivu voidaan asettaa minne tahansa keskusmuistissa.
Yleisesti virtuaalimuistin osoitus on hidas operaatio, koska data pitää hakea välimuistien kautta, ja pahimmassa tapauksessa massamuistista asti. Nyt välimuistin hallinta voidaan tehdä hardiksen ja laiteohjelmiston yhteistyönä, koska oletuksena 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 lähtökohtaisesti hitaisiin virtuaalimuistihakuihin saadaan siis, kun osoitettu muisti on valmiina väli/keskusmuistissa. Nyt paikallisuusperiaatteen mukaan, fyysiseksi muistiosoitteeksi käännettyä virtuaalimuistin osoitetta tarvitaan usein, joten fyysiset osoitteet olisi hyvä ottaa valmiiksi talteen välimuistin sivutauluun.
Silti ongelmana on, että huolimatta sivutaulun käyttämisestä, muistiosoituksessa tarvitaan kolme osoitusta muistiin: sivutaulujen sisällysluetteloon, sivutauluun ja fyysiseen muistiin.
Nyt virtuaalimuistin osoituksia voidaan nopeuttaa tallettamalla jo virtuaalisesta fyysiseksi muunnetut osoitteet rekisteriin tai itseasiassa välimuistiin nimeltä TLB (engl. Translation lookaside buffer). Kun muunnettu osoite löytyy TLB:stä, ei muita välimuistin osoitehakuja 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?