Koherentnost keša

U informatici, koherencija keša se odnosi na doslednost podataka sačuvanih u lokalnim keš memorijama deljenog resursa.

Više keš memorija deljenih resursa

Kada klijenti održavaju keš memorije zajedničkog memorijskog resursa, mogu se pojaviti problemi sa nedoslednim podacima. Ovo je posebno tačno za procesore u vešeprocesorskom sistemu. Ako gornji klijent ima kopiju meorije iz prethodnog čitanja a donji klijent promeni taj memorijski blok, gornji klijent može ostati sa pogrešnim kešom memorije bez obaveštenja o promeni. Koherencija keša je namenjena da upravlja takvim konfliktima i održava doslednost između keša i memorije.

Pregled

U višeprocesorskom sistemu sa deljenom memorijom za svaki procesor, moguće je imati više kopija jednog instrukcijskog operanda: jedna kopija u glavnu memoriju i jedna u svaku keš memoriju. Kad se promeni jedna kopija u kešu, ostale kopije operanda se takođe moraju promeniti. Koherencija keša je disciplina koja osigurava da se promene u vrednostima deljenih operanada takođe moraju promeniti u celom sistemu brzo.

Postoje tri nivoa koherencije keša:

• Svaka operacija pisanja izgleda kao da se desila trenutno
• Svi procesori vide istu sekvencu promena vrednosti za svaki odvojeni operand
• Različiti procesori mogu videti operaciju i pretpostaviti drugačije sekvence vrednosti. Ovo je nekoherentno ponašanje.

I u drugoj i trećoj stavci program može da posmatra zastarele podatke. Od skoro, računarski dizajneri su realizovali disciplinu koja omogućava da su programi koji su sposobni za rad sa drugom stavkom automatski sposobni za rad i sa trećom. Zbog toga će u nekom trenutku samo prva i treća stavka biti viđena u mašinama.

Definicija

Koherencija definiše ponašanje čitanja i pisanja na istu memorijsku lokaciju. Koherencija keša je dobijena ako se sledeći uslovi ispune:

1. U čitanju koje čita procesor P na lokaciju IKS koja prati pisanje istog procesora P na IKS, bez pisanja IKS-a od drugog procesora koje se dešava između instrukcija za pisanje i čitanje koje je napravio P, IKS mora uvek vraćati vrednost koju je napisao P. Ovaj uslov se odnosi na čuvanje reda programa, i ovo se mora ispuniti čak i u jednoprocesorskim arhitekturama.
2. Čitanje koje je obavio procesor P1 na lokaciju IKS koju prati pisanje drugog procesora P2 na IKS mora vratiti napisanu vrednost koju je napravio P2 ako se ne pojave nikakva druga pisanja na IKS između dve adrese i čitanje i pisanje je uspešno razdvovjeno. Ovaj uslov definiše koncept koherentnog pogleda na memroiju. Ako procesori mogu da čitaju iste stare vrednosti nakon pisanja koje je napravio P2, možemo reći da je memorija nekoherentna.
3. Pisanje na istu lokaciju mora biti sekvencirano. Drugim rečima, ako lokacija IKS prima dve različite vrednosti A i B, u ovom redu, od bilo koja dva procesora, procesori nikad neće moći da pročitaju lokaciju IKS kao B i onda kao A. Lokacija IKS mora biti viđena sa vredostima A i B tim redosledom.

Ovi uslovi su definisani s pretpostavkom da se operacije čitanja i pisanja dešavaju trenutno. Ipak, ovo se ne dešava u hardveru zbog latencije memorije i ostalih aspekata arhitekture. Pisanje procesora P1 ne mora biti viđeno od strane procesora P2 ako se čitanje desi vrlo brzo nakon pisanja. Model memorijske koherencije određuje kada napisana vrednost može biti viđena sledećoj instrukciji čitanja koju su naredili drugi procesori. Snooping Retko i posebno u algoritmima, koherencija može imatei značenje lokalnost referenci.

Mehanizmi koherencije

Koherencija bazirana na direktorijumu

U ovakvom sistemu, podaci koji se dele su postavljeni na zajednički direktorijum koji održava koherenciju među kešom. Direktorijum se ponaša kao filter kroz koji procesor mora tražiti dozvolu da pročita unos iz primarne memorije na njegov keš. Kada je unos promenjen, direktorijum se ili ažurira ili poništava drugi keš sa tim unosom.

Njuškanje

Ovo je proces gde individualni keš motri adresne linije za pristup memorijskim lokacijama koje su keširane. Zove se write invalidate protocol kada se operacija pisanja nadgleda na lokaciji koju keš ima kopiranu i kontroler keša poništava sopstvenu kopiju iznjuškane memorijske lokacije.

Filter njuškanja smanjuje saobraćaj njuškanja održavajući množinu unosa, od kojih svaki reprezentuje keš liniju koju ima jedan ili više čvorova. Kada je potrebna zamena jednog ili više unosa, filter njuškanja bira unos koji predstavlja keš liniju ili linije koja ima najmanje čvorova za vlasnike, kako što je utvrđeno od vektora prisutnosti u svakom unosu. Za prerađenu selekciju se koriste vremenski algoritmi ili druga vrsta ako jedna ili veše keš linija ima najmanji broj čvorova za vlasnike.

Snarfing

To je mehanizam gde kontroler keša pazi i adresu i podatke u pokušaju da ažurira svoju kopiju memorijske lokacije kada drugi gospodar modifikuje lokaciju u glavnoj memoriji. Kada se operacija čitanja vidi na lokaciji čiju keš ima kopiju, kontroler keša ažurira svoju kopiju memorijske lokacije sa novim podacima.

Sistemi sa raspodeljenom memorijom mimikuju ove mehanizme u pokušaju da održe doslednost između blokova memorije u labavo povezanim sistemima.

Dva najčešća tipa koherencije koji se trenutno proučavaju su njuškanje i direktorijumsko. Svako ima svoje prednosti i mane. Protokoli njuškanja su brži, ali nisu skalabilni. Svaki zahtev mora biti podeljen sa svim čvorovima u sistemu, što znači da što je sistem veći, veličina busa mora da bude veća. Direktorijumi imaju veće latencije ali koriste manje bendvita pošto su poruke tačno naslovljene nekome. Zbog ovoga, mnogi veći sistemi sa više od 64 procesora koriste ovaj tip koherencije keša.

Protokol koherencije

Protokl koherencije je protokol koji zadržava doslednost između svih keševa u sistemu raspodeljene deljene memorije. Protokol zadržava koherenciju memorije po specifičnom koherencijskom modelu. Stariji multirprocesori podržavaju model sekvencijalne koherencije, dok moredni sistemi tipično podržavaju release consistency ili weak consistency modele.

Prevodi između specifičnih implementacija ovih protokola variraju. Na primer implementacije može izabrati drugačije ažuriranje i poništenje procesa kao što su ažuriranje-nakon-čitanja, ažuriranje-nakon-čitanja ili poništavanje-nakon-čitanja. Izbor tranzicije može uticati na saobraćaj unutar keša, što može uticati na bendvit. Ovo treba uzeti u obzir prilikom dizajna raspodeljenog softvera.

Različiti modeli i protokoli su napravljeni za očuvanje koherencije, kao što su MSI, MESI (Illinois), MOSI, MOESI, MERSI, MESIF, write-once, Synapse, Berkeley, Firefly i Dragon protocol.

Literatura

• Patterson, David; Hennessy, John (2009). Computer Organization and Design (4th izd.). Morgan Kaufmann. ISBN 978-0-12-374493-7.