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)
    • Transfer1: izazvan je prenos podatka iz keš memorije na magistralu kako bi neki drugi kontroler keš memorije mogao da ga pročita, ali sa dodatnom arbitracijom kako bi samo jedan kontroler poslao taj podatak na magistralu
    • 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).

Write-allocate

MSI

MESI

MOESI

Dragon

Firefly