Vahemälu sidusus (cache coherence): mälu ja vahemälu järjepidevus

Vahemälu sidusus (cache coherence): kuidas tagada mälu ja vahemälude järjepidevus mitme protsessoriga süsteemides — probleemid, lähenemised ja jõudluse optimeerimine.

Vahemälu sidusus (cache coherence) tähendab meetmete ja reeglite kogumit, mis tagavad, et sama füüsilise mäluadressi koopiad eri vahemäludes sisaldavad kooskõlalisi ja mõistlikke andmeid. Vahemälu kasutatakse selleks, et parandada juurdepääsu kiirust mäluressurssidele, kuid kui samale ressursile on mitu vahemälu (näiteks mitme tuumaga protsessoris või jaotatud süsteemis), võivad tekkida olukorrad, kus ühe koopia muutmine ei peegellu teistes koopiates. See võib viia programmi vale käitumiseni, kui tuumad/klientprogrammid loevad vananenud andmeid.

Probleeme võib tekkida, kui ühise mäluressursi vahemälu on palju: vahemälus olevad andmed ei pruugi enam olla ajakohased või eri vahemälud võivad sisaldada erinevaid väärtusi samal mälublokil. Tavaline näide on protsessorite vahemälu mitme protsessoriga süsteemis. Kui ühel kliendil (tuumal) on mälubloki koopia eelmise lugemise tulemusel ja teine klient muudab seda sama mälublokki, võib esimene klient jääda kasutama kehtetut (stale) andmekoopia, ilma et ta muutusest teaks. Vahemälu sidusus on täpselt selle probleemi haldamiseks ja järjepidevuse säilitamiseks vahemälu ning peamise mälu vahel mõeldud mehhanismide üldnimetus.

Miks see on oluline

Ilma sidususeta võivad mitme lõime või tuuma programmid lugeda vananenud väärtusi, mis viib ränki loogikavigadeni. Samuti põhjustab vahemälukoopiate erinevus täiendavat sünkroniseerimist tarkvaras (näiteks tihedad lukuoperatsioonid), mis omakorda vähendab süsteemi jõudlust. Sidus süsteem võimaldab arvutitel töötada paralleelselt, säilitades samal ajal õiged ja prognoositavad andmete väärtused.

Levinud lahendused ja protokollid

Peamised lähenemised vahemälu sidususe lahendamiseks on:

Snooping-põhised protokollid – igas protsessori vahemälus jälgitakse (snoop) bussil toimuvat liiklust; kui üks vahemälu kirjutab mäluaadressi, teised kuulajad teavad seda ja kas uuendavad või tühistavad oma koopiad. See töötab hästi väiksema tuumade arvuga süsteemides ja jagatud bussiga arhitektuurides.
Directory-põhised süsteemid – keskselt või jaotatud kataloog hoiab kirjet selle kohta, millised sõlmed/vahemälud omavad konkreetse mälubloki koopiat; uuendusi koordineeritakse kataloogi abil, mis vähendab kogu süsteemi liiklust ja on skaleeritavam suure hulga sõlmedega süsteemides.
Write-invalidate vs write-update – kahe põhistrateegia erinevus: write-invalidate kustutab teiste koopiad, kui toimub kirjutus (nii et kirjutaja saab eksklusiivse õiguse), write-update aga levitab uut väärtust teistele koopiatele. Write-invalidate on enamlevinud, sest see vähendab suurt kirjutuskoormuse korral edastatava andmemahu.

Staatused ja MESI

Paljud protokollid töötlevad vahemäluregistreid olekute kaudu. Üks tuntumaid on MESI-mudel, kus iga mälublokk võib olla ühes järgmistest olekutest:

Modified (M) – plokk on vahemälus muudetud ja erineb peamisest mälust; ainult sellel vahemälul on värske koopia.
Exclusive (E) – vahemälal on eksklusiivne ja ühtne koopia, mis vastab peamise mälu väärtusele; teised vahemälud koopiat ei oma.
Shared (S) – koopiad võivad eksisteerida mitmes vahemälus ja need vastavad peamise mälu väärtusele.
Invalid (I) – vahemälus olev koopia on kehtetu.

Lisaks on laiendusi nagu MOESI, mis lisab täiendava "Owned" oleku, et vähendada kopeerimist kirjutuste ja lugemiste ajal.

False sharing (valed jagamised)

False sharing tekib siis, kui kaks eri lõime või protsessorit kirjutavad erinevatele mälavaldkondadele, mis asuvad samas vahemälujoones (cache line). Kuigi loogiliselt neid andmeid ei jagata, põhjustab ühise vahemälujoone muutumine sidususe tõttu pidevaid invalideerimisi ja ülekandeid, mis tugevalt halvendab jõudlust. Selle vältimiseks tuleks andmete paiknemist mäluplokis planeerida (näiteks struktuuride täitmine või pustalised joondused).

Vahemälu sidusus vs mälu järjepidevus (consistency)

Oluline on eristada mõisteid: sidusus tagab, et iga üksiku mäluaadressi koopiad on kooskõlas; järjepidevus (memory consistency) aga määrab reeglid, kuidas mitme aadressi operatsioonide nähtavus ja järjekord rakendustele avalduvad. Sidusus on seega järjepidevuse erijuht, kuid järjepidevusmudelid (nagu sequential consistency, release consistency jt) määravad rangemaid või leebemaid nähtavuse ja järjestuse nõudeid.

Jõudlus ja skaleeruvus

Vahemälu sidusus lisab süsteemile ülepea ja liiklust (invalideerimised, uuendused, päringud kataloogile), mis võib mõjutada latentsust ja läbilaskevõimet. Snooping töötab hästi väikese või keskmise suurusega süsteemide puhul, kuid suures mastaabis on directory-põhised lahendused tõhusamad. Tarkvara ja algoritmide kujundamisel tuleb arvestada sidususe tegevust mõjutavaid tegureid (nt false sharing, sünkroniseerimiskulud).

Praktilised soovitused arendajale

Katilda andmete paiknemine: väldi selliseid andmestruktuure, mis panevad tihti kirjutatavad väljad samasse vahemälujoone.
Kasutage sobivaid sünkroniseerimismehhanisme (lukud, atomaaroperatsioonid, barjäärid) ning vähendage liigset sünkroonimist.
Testa ja profiileeri rakendust mitmetuumalises keskkonnas, et tuvastada false sharingut ja koormuse tippe.

Kokkuvõttes on vahemälu sidusus kriitiline osa kaasaegsete mitmetuumaliste ja jaotatud süsteemide arhitektuurist: see tagab andmete õigsuse, kuid nõuab hoolikat protokollide ja tarkvaralise disaini valikut, et säilitada head jõudlusnäitajad.

Mitu jagatud ressursi vahemälu

Määratlus

Koherentsus määratleb lugemise ja kirjutamise käitumist samasse mälupunkti. Vahemälu on sidus, kui kõik järgmised tingimused on täidetud:

Kui protsessor P loeb asukohta X, peab P pärast sellesse asukohta kirjutamist saama selle väärtuse, mille ta kirjutas, kui ükski teine protsessor ei ole sellesse asukohta teist väärtust kirjutanud. See kehtib ka monoprotsessorsüsteemide puhul, see tähendab, et mälu suudab hoida kirjutatud väärtust.
Oletame, et on kaks protsessorit, P ₁ja P₂, ja P ₁kirjutas väärtuse X₁ ja seejärel P ₂kirjutas väärtuse X₂, kui P ₁loeb seda väärtust, peab ta saama P₂ poolt kirjutatud väärtuse X₂, mitte selle väärtuse, mille ta kirjutas, X₁, kui nende kahe vahel ei ole teisi kirjutusi. See tähendab, et mälu vaade on sidus. Kui protsessorid saavad lugeda sama vana väärtust pärast P₂ poolt tehtud kirjutamist, ei oleks mälu sidus.
Korraga saab mälus olla ainult üks kirjutamine teatavasse kohta. Kui kirjutamisi on mitu, peavad need toimuma üksteise järel. Teisisõnu, kui asukoht X sai kaks erinevat väärtust A ja B, selles järjekorras, mis tahes kahe protsessori poolt, ei saa protsessorid kunagi lugeda asukohta X kui B ja seejärel lugeda seda kui A. Asukohta X tuleb näha väärtustega A ja B selles järjekorras.

Need tingimused on määratletud eeldusel, et lugemis- ja kirjutamisoperatsioonid toimuvad koheselt. See ei juhtu aga arvuti riistvaras mälu latentsuse ja muude arhitektuuri aspektide tõttu. Protsessori X poolt tehtud kirjutamist ei pruugi protsessor Y lugeda, kui lugemine toimub väga väikese aja jooksul pärast kirjutamist. Mälu järjepidevuse mudel määratleb, millal kirjutatud väärtus peab olema nähtav teiste protsessorite poolt tehtud järgmise lugemiskäsu poolt.

Vahemälu sidususe mehhanismid

Kataloogipõhised koherentsusmehhanismid säilitavad keskse kataloogi, mis sisaldab vahemällu salvestatud plokke.

Snooping on protsess, mille käigus iga vahemälu jälgib oma vahemälus olevatele mälukohtadele juurdepääsu aadressireale. Kui täheldatakse kirjutamist asukohale, mille koopia on vahemälus, tühistab vahemälu kontroller oma koopia nuhkitud mälukohast.

Snarfing tähendab, et vahemälu kontroller jälgib nii aadressi kui ka andmeid, püüdes uuendada oma mälukoha koopiat, kui teine master muudab asukohta põhimälus.

Jaotatud ühismälusüsteemid jäljendavad neid mehhanisme, et nad suudaksid säilitada järjepidevust mälublokkide vahel vabalt seotud süsteemides.

Kaks kõige levinumat sidususe tüüpi, mida tavaliselt uuritakse, on Snooping ja kataloogipõhine sidusus. Mõlemal on omad eelised ja puudused. Snooping-protokollid kipuvad olema kiiremad, kui on olemas piisav ribalaius, kuna kõik tehingud on kõikide protsessorite poolt vaadeldavad päringud-vastused. Puuduseks on see, et snooping ei ole skaleeritav. Iga päring tuleb edastada kõigile süsteemi sõlmedele. Kui süsteem muutub suuremaks, peab (loogilise või füüsilise) bussi suurus ja selle pakutav ribalaius kasvama. Seevastu kataloogidel on pikemad viivitused (3 hüppelise päringu/edasisaatmise/vastamise korral), kuid nad kasutavad palju vähem ribalaiust, kuna sõnumid on punktist-punkti, mitte ei ole eetrisse saadetud. Seetõttu kasutavad paljud suuremad süsteemid (>64 protsessorit) seda tüüpi vahemälu sidusust.

Küsimused ja vastused

K: Mis on vahemälu sidusus?

V: Cache coherence tähendab selle tagamist, et ressursi kõik vahemälud sisaldavad samu andmeid ja et vahemäludes olevad andmed on järjepidevad (andmete terviklikkus).

K: Mis on vahemälu sidususe eesmärk?

V: Vahemälu sidususe eesmärk on hallata konflikte ühise mäluressursi mitme vahemälu vahel ning säilitada järjepidevus vahemälu ja mälu vahel.

K: Millised võivad olla vahemälu sidususe puudumise tagajärjed?

V: Ilma vahemälu sidususeta ei pruugi andmed vahemälus enam mõtet omada või ei pruugi ühes vahemälus olla enam samu andmeid kui teistes, mis võib põhjustada ebakõlasid ja vigu.

K: Mis on tavaline juhtum, kus vahemälu sidususega tekivad probleemid?

V: Tavaline juhtum, kus esineb probleeme vahemälu sidususega, on mitme protsessoriga süsteemi protsessorite vahemälu.

K: Kuidas toimib vahemälu sidusus?

V: Vahemälu koherentsus toimib, tagades, et kõik ressursi vahemälud sisaldavad samu andmeid ja et vahemäludes olevad andmed on erinevate meetodite abil järjepidevad.

K: Mida tähendab mälu koherentsus?

V: Mälu koherentsus tähendab andmete järjepidevust jagatud mäluressursil.

K: Kuidas saab vahemälu sidusus parandada jõudlust?

V: Vahemälu sidusus võib parandada jõudlust, võimaldades kiiremat ja tõhusamat juurdepääsu konkreetsele ressursile.