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

Dijagram stanja WTI protokola.

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

Dijagram stanja WTI protokola sa 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

Dijagram stanja MSI protokola.

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 ekskluzivnost nad njim
• S (shared): kontroler ima validan podatak ali ni vlasništvo ni ekskluzivnost 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 ekskluzivnost, 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

Dijagram stanja MESI protokola.

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

Dijagram stanja MOESI protokola.

Logičan sled protokola koji uvodi stanje koje podrazumeva samo eksluzivnost jeste protokol koji dodaje stanje koji podrazumeva samo vlasništvo. Tako nastaje MOESI protokol, sa dodatnim O (owned) stanjem. Ovo je ujedno i najkomplikovaniji osluškujući protokol.

Čitanje se u ovom protokolu generalno nije menjalo. Čitanje iz O stanja, intuitivno, ne izlazi na magistralu. Detekcija čitanja dok je podatak u O stanju inicira transfer između keševa. Ono što se jeste promenilo jeste što se u S stanju više ne vrši transfer pri detekciji čitanja, samo u M, O i E stanjima. Razlog za ovo je verovatno što novouvedeno stanje vrši slične dužnosti kao F stanje u MESIF protokolu, pa nema potrebe za transferom iz S stanja, koje je i prethodno bilo nedefinisano.

Cilj MOESI protokola je da dodatno smanji broj izlazaka na magistralu (i vreme provedeno na magistrali) zbog upisa. Iz ovog razloga, novo stanje O nam služi kako bismo u njega mogli da pređemo iz M stanja kada detektujemo da još neko na magistrali koristi naš podatak. Time gubimo eksluzivnost, ali ne i vlasništvo, pa time može da postoji više kontrolera u S stanju u isto vreme kao jedan u O stanju.

Dodatna funkcionalnost uvedena ovim protokolom jeste BusUpgr uzrok i posledica na dijagramima. Naime, ukoliko se u nekom deljenom (ne-eksluzivnom, odnosno S ili O) stanju vrši upis, umesto upisa u memoriju korišćenjem BusRdX, sada se šalje signal na magistralu kako bi ostali kontroleri u svojim keševima poništili dati podatak. Ostali kontroleri reaguju na ovo tako što iz svojih deljenih stanja prelaze u I. Ovime trenutni kontroler postaje vlasnik podatka, a ne mora da čeka na memoriju za upis tog podatka.

Dragon

Dijagram stanja Dragon protokola.

Ažurirajući protokoli su drugačiji od poništavajućih uglavnom u tome što nemaju nevalidno (I) stanje. To znači da podatak može ili da ne bude u kešu (implicitno nevalidno stanje) ili da bude validan. Zbog ovog implicitnog nevalidnog stanja, na dijagramima se crtaju strelice koje nemaju ili početak ili kraj, jer je njihov početak ili kraj zapravo to implicitno nevalidno stanje.

Stanja su drugačije nazvana:

• E i M stanja odgovaraju istoimenim iz MOESI protokola
• Sm stanje odgovara O stanju iz MOESI
• Sc stanje odgovara S stanju iz MOESI

Pored čitanja, S bit se u ovom protokolu koristi i prilikom pisanja. Ukoliko se podatak koji nije u kešu upisuje (write miss), proverava se S bit i odlazi u Sm ukoliko je podatak deljen, odnosno M ukoliko nije. Takođe, ukoliko se u Sm stanju prilikom upisa detektuje da je taj kontroler jedini koji koristi taj podatak na magistrali, prelazi se u M stanje.

Umesto BusUpgr sada se koristi BusUpd koje kaže svim kontrolerima na magistrali da ažuriraju dati podatak, na šta oni reaguju sa Update. Upis podatka sada što više izbegava memoriju, tako da je korišćenje BusRdX zamenjeno sa BusUpd. Ukoliko podatak pri upisu nije ranije bio u kešu, a ostali kontroleri poseduju taj podatak, prvo mora biti poslata BusRd komanda kako bi kontroler koji je ranije držao ekskluzivnost i vlasništvo nad tim podatkom iz svog M stanja prešao u Sm, a tek zatim urađen BusUpd. Upis u memoriju se vrši tek ukoliko kontroler sa vlasništvom nad podatkom mora da izvrši zamenu tog podatka iz svog keša, prilikom čega vrši flush operaciju.

Transfer između keševa prilikom čitanja se u ovom protokolu vrši samo ukoliko je podatak u vlasništvu kontrolera, odnosno ne vrši se transfer u E stanju više.

Firefly

Dijagram stanja Firefly protokola.

Neko se nekada zapitao da li je stanje Sm u Dragon protokolu zaista neophodno, i došao je do zaključka da nije ukoliko bi BusUpd ažuriralo i memoriju. Tako je nastao Firefly protokol. Pored ove izmene u BusUpd, Flush akcija funkcioniše kao Transfer sa upisom u memoriju.

Stanja su nazvana po tome da li su deljena (shared, odnosno da li ne podrazumevaju eksluzivnost) i da li podrazumevaju vlasništvo (odnosno da li je podatak u njima prljav, dirty). Stoga su kreativna imena za ova stanja sd (nije deljeno, nije prljavo, ekvivalent E), sD (nije deljeno, jeste prljavo, ekvivalent M) i Sd (jeste deljeno, nije prljavo, ekvivalent S i Sc).

Prilikom detekcije čitanja se sada gotovo uvek radi Transfer, osim prilikom detekcije čitanja u sD stanju, kada se radi Flush. Magistrala mora da podrži više kontrolera koji iz stanja Sd rade Transfer, slično kao u MESI protokolu kad se vrši Transfer iz S.

Pisanje u Sd stanju se razlikuje od Dragon u tome što se ili ostaje u istom stanju (ukoliko je podatak i dalje deljen) ili prelazi u sd (ukoliko nije), sa sve BusUpd. U sD stanje se prelazi samo kada se u okviru sd stanja upisuje u podatak, jer ne moramo da izlazimo na magistralu ako naš podatak nije deljen. Zbog nedostatka stanja nalik Sm, iz sD se prilikom detekcije čitanja odmah prelazi u Sd, a prilikom upisa u podatak koji nije u keš memoriji a jeste deljen se sada prelazi u Sd.