Multiprocesorski sistemi/Osluškujući protokoli

Osluškujući (snoopy) protokoli keš koherencije se predaju u drugom bloku nastave na predavanjima i delom na vežbama. Ovaj vodič navodi njihove glavne karakteristike i objašnjava njihove dijagrame funkcionisanja, kako bi studenti mogli da razumeju njihove sličnosti i razlike i na osnovu više intuicije a manje bubanja dijagrama reše zadatak koji će se iz ovih protokola neizbežno pojaviti na kolokvijumu.

Dijagrami

Dijagrami ispod biće izloženi na isti način kao na vežbama i predavanjima. Najteži deo razumevanja ovih protokola jeste razumevanje dijagrama na kojima se zasnivaju.

Elementi dijagrama jesu:

• Kružići: predstavljaju stanja u kojima se jedan podatak u kešu može naći. Unutar kružića nalazi se oznaka stanja.
• Pune strelice: predstavljaju prelaze između stanja kao rezultat akcija tog procesora čiji je keš.
• Isprekidane strelice: predstvljaju prelaze između stanja kao rezultat akcija na magistrali koje kontroler keš memorije osluškuje. Obojene su crvenom bojom kako bi bilo jasnije da su ove akcije drugačije od onih izvršenih od strane procesora.
• Oznake iznad strelica: opisuju uzroke i posledice prelaska iz jednog u drugo stanje.
  • Mogući formati ovih oznaka su:
    • Узрок/Последица
    • Узрок/Последица(Услов)
    • Узрок/Последица1; Последица2
    • Узрок/Последица1; Последица2(Услов).
  • Uzroci mogu biti:
    • PrRd: naš procesor je zatražio čitanje datog podatka.
    • PrWr: naš procesor je zatražio upis u dati podatak.
    • BusRd: kontroler keš memorije je primetio da neki drugi procesor na magistrali pokušava da pročita dati podatak.
    • BusWr: kontroler keš memorije je primetio da neki drugi procesor na magistrali pokušava da upiše u dati podatak.
    • BusRdX: kontroler keš memorije je primetio da neki drugi procesor na magistrali pokušava da pročita dati podatak sa namerom da posle toga piše u njega. Ovaj uzrok se koristi umesto BusWr u svim protokolima osim WTI.
    • BusUpgr: kontroler keš memorije je primetio da neki drugi procesor na magistrali invalidira dati podatak.
    • Replace: podatak je zamenjen u keš memoriji nekim drugim podatkom.
    • PrRdMiss: desio se promašaj pri čitanju datog podatka od strane procesora (podatak nije bio u kešu prethodno). Ovaj uzrok je prisutan samo na dijagramima ažurirajućih protokola, jer oni nemaju specijalno stanje kojim predstavljaju da podatak nije u kešu.
    • PrWrMiss: desio se promašaj pri pisanju u dati podatak od strane procesora (podatak nije bio u kešu prethodno). Ovaj uzrok je prisutan samo na dijagramima ažurirajućih protokola, jer oni nemaju specijalno stanje kojim predstavljaju da podatak nije u kešu.
    • BusUpd: kontroler keš memorije je primetio da neki drugi procesor na magistrali pokušava da svim ostalim kontrolerima kaže da ažuriraju taj podatak kod sebe. Ovaj uzrok je prisutan samo na dijagramima ažurirajućih protokola.
  • Posledice mogu biti:
    • --: bez posledice
    • BusRd: izazvano je čitanje podatka iz memorije
    • BusWr: izazvan je upis podatka u memoriju
    • BusRdX: izazvano je čitanje podatka iz memorije sa namerom za upis
    • Flush: izazvan je upis sačuvanog podatka u memoriju, jer podatak u memoriji do tog trenutka nije bio ažuran
    • Transfer: izazvan je prenos podatka iz keš memorije na magistralu kako bi neki drugi kontroler keš memorije mogao da ga pročita (koristi se kada je trenutna keš memorija jedini ažuran izvor podatka)
    • BusUpgr: izazvano je poništenje svih kopija datog podatka u ostalim keš memorijama
    • Update: izazvano je ažuriranje datog podatka u trenutnoj keš memoriji na osnovu podatka sa magistrale poslatog od nekog drugog keš kontrolera
    • BusUpd: izazvano je ažuriranje datog podataka u svim ostalim keš kontrolerima na magistrali
  • Ukoliko Услов nije ispunjen, taj prelaz se ne dešava. U svim dijagramima ispod uslovi će biti S (shared bit je postavljen na magistrali od barem jednog kontrolera keš memorije) ili ¬S (shared bit nije postavljen na magistrali).

WTI

WTI protokol je najjednostavniji protokol za keš koherenciju, jer ima samo dva stanja:

• V (valid): podatak u keš memoriji je važeći
• I (invalid): podatak u keš memoriji nije važeći (ili nije u keš memoriji uopšte)

Pri čitanju podatka, procesor proverava da li je taj podatak validan u keš memoriji. Ukoliko jeste, nema potrebe za dodatnim akcijama. Ukoliko nije, čita ga iz memorije i zatim taj podatak postaje validan.

Upis podatka odmah izdaje komandu za upis u memoriju (write-through tehnika) i svoj podatak u keš memoriji ažurira samo ukoliko je validan (write-no-allocate tehnika). Kada ostali keš kontroleri primete upis podatka, prebacuju podatak u nevalidno stanje. U ovom protokolu, kada kontroleri primete čitanje podatka na magistrali oni ga jednostavno ignorišu.

Write-allocate

Gornji protokol takođe može da koristi i write-allocate tehniku. U ovom slučaju, kada podatak nije u keš memoriji a potreban je njegov upis on se pored upisa takođe dodaje u keš memoriju, odnosno taj podatak prelazi u validno stanje.

MSI

Najveći nedostatak WTI protokola je što svaki upis ide direktno u memoriju (write-through). Zato su naredni protokoli napravljeni sa odloženim upisom (write-back) u vidu, tako da keš kontroleri upisuju podatak u memoriju samo kada je to zaista neophodno. Ovom prilikom uvode se dva nova koncepta:

• Vlasništvo: kontroler ima validnu vrednost podatka i zadužen je za njen upis u memoriju ukoliko se dešava zamena podatka iz keša i prosleđivanje podatka ostalim kontrolerima keša ukoliko ga zahtevaju BusRd ili BusRdX operacijom
• Ekskluzivnost: kontroler je jedini koji u celom sistemu drži taj podatak u kešu, pa zato može da obavlja određene operacije nad njim bez izlaska na magistralu

Prvi write-back protokol koji se obrađuje je MSI, sa sledećim stanjima:

• M (modified): kontroler ima validan podatak i vlasništvo i eksluzivnost nad njim
• S (shared): kontroler nema validan podatak ali ni vlasništvo ni eksluzivnost nad njim
• I (invalid): isto kao u WTI

Kada se pokuša čitanje podatka koji nije u kešu, ide se u shared stanje (iako podatak ne mora nužno biti deljen, što je rešeno kasnijim protokolima). Drugi kontroleri na magistrali mogu detektovati ovo čitanje, i ukoliko je neki od njih u modified stanju, on radi upis svog podatka u memoriju (flush) a zatim prelazi u shared stanje (više nema ni vlasništvo, jer je podatak već upisao, a ni eksluzivnost, jer postoji drugi keš kontroler sa tim podatkom kod sebe). Čitanje podatka koji jeste u kešu ne rezultuje nikakvim izlaskom na magistralu ili promenom stanja.

Kada se pokuša upis u podatak, bez obzira na prethodno stanje, prelazi se u modified stanje. Procesor koji upisuje izlazi na magistralu samo ukoliko nije u modified stanju (jer u tom slučaju ima vlasništvo nad podatkom). Ovom prilikom svi ostali keš kontroleri detektuju upis i prelaze u nevalidno stanje, a ukoliko je neki od njih imao vlasništvo nad podatkom pre prelaska radi flush podatka u memoriju.

MESI

Kao što je ranije pomenuto, jedan problem sa MSI protokolom je što se nakon čitanja podatka ide u shared stanje bez obzira da li ostali keš kontroleri imaju ili nemaju taj podatak kod sebe. Ovaj problem rešen sa dva mehanizma:

• Na magistralu dodat je S (shared) bit, tako da keš kontroleri mogu da puste logičku jedinicu na njega ukoliko poseduju podatak koji se čita ili upisuje. Na ovaj način drugi kontroleri mogu da primete da li imaju ekskluzivnost nad podatkom.
• U protokol dodato je E (exclusive) stanje, koje znači da kontroler ima eksluzivnost ali ne i vlasništvo nad podatkom. Razlika ovog stanja od M stanja je, dakle, u tome da li je podatak izmenjen (prljav, dirty) ili nije.

Time smo došli do MESI protokola. Prilikom čitanja podatka koji nije u kešu u tom protokolu se ide u stanje S ukoliko je S bit postavljen na magistrali, ili stanje E ukoliko nije. Kontroleri takođe moraju da detektuju čitanje od strane drugih kontrolera dok su u stanju E, kako bi prešli u stanje S (ali, za razliku od stanja M, bez upisa tog podatka nazad u memoriju).

Prilikom upisa podatka, jedina razlika od MSI protokola se tiče E stanja. Ukoliko procesor u E stanju upisuje podatak, potrebno je jedino da pređe u M stanje jer sada ima i vlasništvo nad tim podatkom (odnosno uprljao je taj podatak).

Još jedna nova stvar koju uvodi MESI protokol je keš-keš transfer podataka. Ukoliko kontroler vidi da drugi kontroler zahteva podatak koji ima u svom kešu, može da inicira transfer svog podatka drugom kontroleru, čime ubrzava čitanje. Jedan od problema koji se ovde može primetiti jeste što na prelazima iz S stanja sa BusRd ili BusRdX kao uzrokom, kontroleri će morati da rade arbitraciju kako bi odredili koji od njih će da radi transfer. Tako dolazimo do...

MESIF

Neki keš kontroleri imaju dodatno stanje F (forward) koje određuje da su oni kontroler koji treba da prosleđuje podatak ukoliko ima više kontrolera sa istim podatkom. U ovom stanju je poslednji kontroler kojem je vršen transfer tog podatka. Na primer:

• Kontroler A zahteva podatak, nijedan od keš kontrolera ga nema pa ga on zato dobija iz memorije i ulazi u stanje E
• Kontroler B zahteva podatak, kontroler A ima taj podatak, pa kontroler A ulazi u S stanje dok kontroler B ulazi u F stanje.
• Kontroler V zahteva podatak, kontroleri A i B imaju taj podatak, kontroler B vrši transfer podatka kontroleru V pa kontroler B ulazi u S stanje a kontroler V u F stanje.
• i tako dalje...

Ukoliko kontroler u F stanju zameni taj podatak za neki drugi, neće biti kontrolera koji će odgovoriti na zahtev drugog kontrolera za taj podatak (iako ostali kontroleri potencijalno imaju taj podatak) pa će taj drugi kontroler svoj podatak dobiti iz memorije.

MOESI

Dragon

Firefly