Tässä luvussa käsittelemme välimuistin koherenssiprotokollia, joiden avulla voidaan selviytyä monivälimuistin epäjohdonmukaisuusongelmista.
Välimuistin koherenssiongelma
Moniprosessorijärjestelmässä datan epäjohdonmukaisuutta voi esiintyä vierekkäisten tasojen välillä tai saman muistihierarkiatason sisällä. Esimerkiksi välimuistissa ja keskusmuistissa voi olla epäjohdonmukaisia kopioita samasta objektista.
Koska useat prosessorit toimivat rinnakkain ja useat välimuistit voivat itsenäisesti pitää hallussaan eri kopioita samasta muistilohkosta, syntyy välimuistin koherenssiongelma. Välimuistin koherenssijärjestelmät auttavat välttämään tämän ongelman ylläpitämällä yhtenäistä tilaa jokaiselle välimuistissa olevalle tietolohkolle.
Olkoon X jaetun datan elementti, johon kaksi prosessoria, P1 ja P2, on viitannut. Alussa kolme kopiota X:stä on yhdenmukaisia. Jos prosessori P1 kirjoittaa uuden datan X1 välimuistiin käyttämällä write-through-käytäntöä, sama kopio kirjoitetaan välittömästi jaettuun muistiin. Tällöin välimuistin ja keskusmuistin välille syntyy epäjohdonmukaisuus. Kun käytetään takaisinkirjoituskäytäntöä, päämuisti päivitetään, kun välimuistissa oleva muutettu tieto korvataan tai mitätöidään.
Yleisesti epäjohdonmukaisuusongelman lähteitä on kolme –
- Kirjoitettavan datan jakaminen
- Prosessien siirtyminen
- I/O-toiminta
Snoopy-väyläprotokollat
Snoopy-protokollilla saavutetaan datan johdonmukaisuus väyläpohjaisen muistijaon avulla kätkömuistin ja jaetun muistin välillä. Write-invalidate- ja write-update-käytäntöjä käytetään välimuistin johdonmukaisuuden ylläpitämiseen.
Tässä tapauksessa kolmella prosessorilla P1, P2 ja P3 on johdonmukainen kopio dataelementistä ’X’ paikallisessa välimuistissaan ja jaetussa muistissa (kuva-a). Prosessori P1 kirjoittaa X1:n välimuistiinsa käyttäen write-invalidate-protokollaa. Kaikki muut kopiot mitätöidään väylän kautta. Sitä merkitään tunnuksella ”I” (kuva-b). Mitätöityjä lohkoja kutsutaan myös likaisiksi, eli niitä ei saa käyttää. Kirjoituspäivitysprotokolla päivittää kaikki välimuistin kopiot väylän kautta. Käyttämällä kirjoitusvälimuistia päivitetään myös muistin kopio (kuva-c).
Välimuistitapahtumat ja -toiminnot
Muistinkäyttö- ja mitätöintikäskyjen suorittamisen yhteydessä tapahtuu seuraavia tapahtumia ja toimintoja –
-
Lukuhuomiot – Kun prosessori haluaa lukea lohkon eikä sitä ole välimuistissa, tapahtuu lukuhuomiotapahtuma. Tämä käynnistää bussilukutoiminnon. Jos likaista kopiota ei ole olemassa, se keskusmuisti, jolla on johdonmukainen kopio, toimittaa kopion sitä pyytävään välimuistiin. Jos etäisessä välimuistissa on likainen kopio, kyseinen välimuisti pidättää päämuistin ja lähettää kopion pyytävään välimuistiin. Molemmissa tapauksissa välimuistikopio siirtyy voimassa olevaan tilaan lukuhyökkäyksen jälkeen.
-
Write-hit – Jos kopio on likaisessa tai varatussa tilassa, kirjoitus tehdään paikallisesti ja uusi tila on likainen. Jos uusi tila on kelvollinen, write-invalidate-komento lähetetään kaikkiin välimuisteihin, jolloin niiden kopiot mitätöityvät. Kun jaettuun muistiin kirjoitetaan läpi, tuloksena oleva tila on varattu tämän ensimmäisen kirjoituksen jälkeen.
-
Write-miss – Jos prosessori ei pysty kirjoittamaan paikalliseen välimuistiin, kopion on tultava joko keskusmuistista tai etäisestä välimuistista, jonka lohko on likainen. Tämä tapahtuu lähettämällä read-invalidate-komento, joka mitätöi kaikki välimuistikopiot. Tämän jälkeen paikallinen kopio päivitetään likaiseen tilaan.
-
Lukutapahtuma – Lukutapahtuma suoritetaan aina paikallisessa välimuistissa aiheuttamatta tilasiirtymää tai käyttämättä snoopy-väylää mitätöintiin.
-
Lohkon korvaaminen – Kun kopio on likainen, se on kirjoitettava takaisin keskusmuistiin lohkon korvaamismenetelmällä. Kun kopio on kuitenkin joko kelvollisessa, varatussa tai mitättömässä tilassa, korvaamista ei tapahdu.
Hakemistopohjaiset protokollat
Käytettäessä moniportaista verkkoa suuren moniprosessorin rakentamiseen, jossa on satoja prosessoreita, snoopy-välimuistitietovälimuistitietoverkkoprotokollia on muutettava verkon ominaisuuksien mukaisiksi. Koska lähetys on erittäin kallista suorittaa moniportaisessa verkossa, johdonmukaisuuskäskyt lähetetään vain niille välimuisteille, jotka säilyttävät kopion lohkosta. Tästä syystä on kehitetty hakemistopohjaisia protokollia verkkoon kytketyille moniprosessoreille.
Hakemistopohjaisessa protokollajärjestelmässä jaettavat tiedot sijoitetaan yhteiseen hakemistoon, joka ylläpitää koherenssia välimuistien välillä. Tässä hakemisto toimii suodattimena, jossa prosessorit pyytävät lupaa ladata merkintä ensisijaisesta muistista sen välimuistiin. Jos merkintää muutetaan, hakemisto joko päivittää sen tai mitätöi muut välimuistit, joissa kyseinen merkintä on.
Hardware-synkronointimekanismit
Synkronointi on kommunikaation erityismuoto, jossa tiedonohjauksen sijaan vaihdetaan tietoa samoissa tai eri prosessoreissa sijaitsevien kommunikoivien prosessien välillä.
Moniprosessorijärjestelmissä käytetään laitteistomekanismeja matalan tason synkronointioperaatioiden toteuttamiseen. Useimmissa moniprosessoreissa on laitteistomekanismeja atomisten operaatioiden, kuten muistin luku-, kirjoitus- tai read-modify-write-operaatioiden, toteuttamiseksi joidenkin synkronointiprimitiivien toteuttamiseksi. Atomisten muistioperaatioiden lisäksi myös joitakin prosessorien välisiä keskeytyksiä käytetään synkronointitarkoituksiin.
Välimuistin koherenssi jaetun muistin koneissa
Välimuistin koherenssin ylläpitäminen on ongelma moniprosessorijärjestelmässä, kun prosessorit sisältävät paikallista välimuistia. Tässä järjestelmässä esiintyy helposti tiedon epäjohdonmukaisuutta eri välimuistien välillä.
Suurimmat huolenaiheet ovat –
- Kirjoitettavan datan jakaminen
- Prosessien siirtyminen
- I/O-aktiviteetti
Kirjoitettavan datan jakaminen
Kun kahdella prosessorilla (P1 ja P2) on sama dataelementti (X) paikallisissa välimuisteissaan ja toinen prosessi (P1) kirjoittaa dataelementtiin (X), koska välimuistit ovat P1:n paikallisen välimuistin kautta kirjoitettavia, myös keskusmuisti päivittyy. Nyt kun P2 yrittää lukea tietoelementtiä (X), se ei löydä X:ää, koska P2:n välimuistissa oleva tietoelementti on vanhentunut.
Prosessien siirtyminen
Ensimmäisessä vaiheessa P1:n välimuistissa on tietoelementti X, kun taas P2:lla ei ole mitään. Prosessi P2:lla kirjoittaa ensin X:ään ja siirtyy sitten P1:lle. Nyt prosessi alkaa lukea dataelementtiä X, mutta koska prosessorilla P1 on vanhentunutta dataa, prosessi ei voi lukea sitä. Prosessi P1:ssä kirjoittaa siis dataelementtiin X ja siirtyy sitten P2:een. Siirtymisen jälkeen P2:lla oleva prosessi alkaa lukea dataelementtiä X, mutta se löytää päämuistista vanhentuneen version X:stä.
I/O-aktiviteetti
Kuten kuvassa on esitetty, kahden prosessorin moniprosessoriarkkitehtuurissa väylään on lisätty I/O-laite. Aluksi molemmat välimuistit sisältävät dataelementin X. Kun I/O-laite saa uuden elementin X, se tallentaa uuden elementin suoraan keskusmuistiin. Kun nyt joko P1 tai P2 (oletetaan, että P1) yrittää lukea elementtiä X, se saa vanhentuneen kopion. Niinpä P1 kirjoittaa elementtiin X. Nyt, jos I/O-laite yrittää lähettää X:ää, se saa vanhentuneen kopion.
Uniform Memory Access (UMA)
Uniform Memory Access (UMA) -arkkitehtuuri tarkoittaa, että jaettu muisti on sama kaikille järjestelmän prosessoreille. Suosittuja UMA-koneluokkia, joita käytetään yleisesti (tiedosto-)palvelimissa, ovat niin sanotut symmetriset moniprosessorit (SMP). SMP:ssä kaikki järjestelmän resurssit, kuten muisti, levyt, muut I/O-laitteet jne. ovat prosessoreiden käytettävissä yhtenäisellä tavalla.
Non-Uniform Memory Access (NUMA)
NUMA-arkkitehtuurissa on useita SMP-klustereita, joilla on sisäinen epäsuora/jaettu verkko, jotka on liitetty toisiinsa skaalautuvaan viestien välitysverkkoon. NUMA-arkkitehtuuri on siis loogisesti jaettu fyysisesti hajautettu muistiarkkitehtuuri.
NUMA-koneessa prosessorin välimuistiohjain määrittää, onko muistiviittaus SMP:n muistissa paikallinen vai etäinen. Etämuistikäyttöjen määrän vähentämiseksi NUMA-arkkitehtuurissa käytetään yleensä välimuistiprosessoreita, jotka voivat tallentaa etämuistitiedot välimuistiin. Mutta kun välimuistit ovat mukana, välimuistien koherenssi on säilytettävä. Niinpä nämä järjestelmät tunnetaan myös nimellä CC-NUMA (Cache Coherent NUMA).
Cache Only Memory Architecture (COMA)
COMA-koneet ovat samankaltaisia kuin NUMA-koneet, sillä erotuksella, että COMA-koneiden päämuistit toimivat suorakartoitettuina tai joukkoassosiatiivisina välimuisteina. Tietolohkot hajautetaan DRAM-välimuistissa olevaan paikkaan niiden osoitteiden mukaan. Tieto, joka haetaan etänä, tallennetaan itse asiassa paikalliseen keskusmuistiin. Lisäksi tietolohkoilla ei ole kiinteää kotipaikkaa, vaan ne voivat liikkua vapaasti koko järjestelmässä.
COMA-arkkitehtuurissa on useimmiten hierarkkinen viestien välitysverkko. Tällaisen puun kytkin sisältää alipuuna hakemiston, jossa on dataelementtejä. Koska datalla ei ole kotipaikkaa, se on etsittävä eksplisiittisesti. Tämä tarkoittaa, että etäkäyttö edellyttää, että puun kytkimiä pitkin kuljetaan ja etsitään niiden hakemistoista tarvittavat tiedot. Jos verkon kytkin saa alipuustaan useita pyyntöjä samasta datasta, se yhdistää ne yhdeksi pyynnöksi, joka lähetetään kytkimen vanhemmalle puolelle. Kun pyydetty data palaa, kytkin lähettää siitä useita kopioita alas alipuuhunsa.
COMA vs. CC-NUMA
Seuraavaksi on lueteltu COMA:n ja CC-NUMA:n erot.
-
COMA on yleensä joustavampi kuin CC-NUMA, koska COMA tukee läpinäkyvästi datan migraatiota ja replikointia ilman käyttöjärjestelmän tarvetta.
-
COMA-koneet ovat kalliita ja monimutkaisia rakentaa, koska ne tarvitsevat epätyypillistä muistinhallintalaitteistoa ja koherenssikäytäntö on vaikeampi toteuttaa.
-
COMA:ssa etäkäynnit ovat usein hitaampia kuin CC-NUMA:ssa, koska puuverkkoa on käytävä läpi datan löytämiseksi.