Protocoale de coerență a memoriei cache (exemple)

Exemple de protocoale de consistență a memoriei cache sunt enumerate aici. Pentru simplitate, toate tranzacțiile stării „ratare” de citire și scriere, care provin evident din starea I (sau ratare a etichetei), nu sunt prezentate în diagrame. Acestea sunt afișate direct pe noul stat. Multe dintre următoarele protocoale au doar valoare istorică. În prezent, principalele protocoale utilizate sunt protocoalele de tip R-MESI / MESIF (tip MESI ) și HRT-ST-MESI (tip MOESI ) sau un subset sau extensie a acestora.

Problemă de coerență a memoriei cache

În sisteme precum multiprocesorul simetric (SMP) , multi core și cc-NUMA , unde este utilizat un cache dedicat pentru fiecare procesor , nucleu sau nod , o problemă de consistență a datelor poate apărea atunci când aceleași date sunt stocate în mai multe cache la un cache. Poate fi rezolvat în două moduri:

1. invalidarea tuturor copiilor celorlalte cache (difuzare-invalidare - invalidare difuzie);
2. actualizarea tuturor copiilor celorlalte cache (scriere-difuzare).

În ambele cazuri memoria poate fi actualizată (scriere prin) sau nu actualizată (scriere); consistența datelor se referă, în general, doar la date (ca operanzi) și nu la instrucțiuni (a se vedea codul de auto-modificare ).

Schemele pot fi clasificate în funcție de:

• Snoopy Vs Directory și schema de cache Vs Shared;
• Scrie prin protocolul de scriere (în funcție de proprietate sau de proprietate);
• Protocol Update Vs Invalidation (actualizare Vs invalidare);
• Intervention Vs non-Intervention (intervenție împotriva non-intervenției);
• Partajare murdară vs protocol non-sharing (date modificate partajate vs nepartajate - MOESI Vs MESI).

Sunt adoptate trei abordări pentru a menține coerența datelor:

1. Vizionarea autobuzului sau Snooping : utilizat în general pentru sistemele SMP sau sistemul multiprocesor simetric / multi-core bazat pe autobuz;
2. Bazat pe director - Transfer de mesaje : bazat pe director și schimb de mesaje; pot fi utilizate în toate sistemele, dar de obicei în sistemele cc-NUMA și în sistemele multi-core extinse;
3. Cache partajat : utilizat în general în sistemele multi-core .

Urmărirea sau spionarea autobuzelor

SMP - Sistem simetric multiprocesor

Protocol utilizat în sistemele de magistrală, cum ar fi sistemele SMP. Sistem care funcționează sub un singur sistem de operare cu două sau mai multe procesoare omogene și cu o memorie principală centralizată partajată. În sistemele multiprocesor cu cache separate care partajează memorie comună, aceleași date pot fi stocate în mai multe cache. O problemă de consistență a datelor apare atunci când datele sunt schimbate într-un singur cache. Protocoalele pentru menținerea coerenței între mai multe procesoare sunt numite protocoale de coerență a cache-ului. În general, în sistemele SMP, coerența se bazează pe abordarea numită Bus watching sau Snoopy. Într-un sistem bazat pe snoopy, toate cache-urile verifică tranzacțiile autobuzului pentru a intercepta date și pentru a vedea dacă are o copie în cache. Sunt folosite diverse protocoale de consistență pentru a menține consistența datelor între cache^[1] . Aceste protocoale sunt, în general, clasificate numai pe baza stărilor cache (de la 3 la 5 și 7 sau mai multe) și a tranzacțiilor dintre ele, dar acest lucru ar putea crea o anumită confuzie, deoarece definiția unui astfel de protocol este incompletă, deoarece lipsește importantă și esențială informații precum acțiunile pe care le produc; aceste acțiuni pot fi induse de procesor sau de autobuz (de ex. „intervenție”, „invalidare”, „difuzare”, „actualizare” etc.). Tipul acțiunilor depinde de implementările implementate. Protocoalele care au aceleași stări și aceleași reguli de tranzacție pot fi diferite, de ex. protocolul MESI cu „intervenție partajată” și MESI fără „intervenție”. Protocoalele cu stări diferite pot fi aproape același protocol, de exemplu protocoalele MESI Illinois cu 4 stări și protocoalele MERSI (IBM) / MESIF-Intel cu 5 stări sunt doar o implementare diferită a aceleiași funcționalități. Cele mai comune protocoale sunt protocolul cu 4 stări cunoscut de acronimul MESI și MOESI cu 5 stări. Alte protocoale utilizează aceleași stări - sau un subset al acestora - dar cu implementări diferite și adesea cu terminologie diferită, dar echivalentă. Termenul MESI sau MOESI sau un subset al acestora se referă, în general, la o clasă de protocoale, mai degrabă decât la un protocol specific.

Stări ale cache-ului

• M = Modificat (modificat) sau D = Dirty (murdar / modificat) sau DE = Dirty-Exclusive (exclusiv murdărie) sau EM = Exclusive Modified (exclusiv modificat)
  • modificat sau murdar, adică modificat numai într-un cache - scriere în caz de înlocuire; datele sunt stocate într-un singur cache, dar datele din memorie nu sunt actualizate (nevalide);
• O = Proprietar (proprietar / manager) o SD = Shared Dirty o M = Shared Modified o T = Tagged
  • modificat, potențial partajat, proprietar - retragere în caz de înlocuire; datele pot fi stocate în mai multe cache, dar datele din memorie nu sunt actualizate (nevalide). Un singur cache este „proprietar”, celelalte cache sunt marcate „partajat”. În cazul unei cereri de citire pe autobuz, datele sunt furnizate de proprietar mai degrabă decât de memorie.
• E = exclusiv sau R = rezervat sau VE = valid-exclusiv sau EC = exclusiv curat sau eu = exclusiv
  • exclusiv sau rezervat sau valid exclusiv sau exclusiv curat; datele sunt stocate numai într-un cache și curățate în memorie.
• S = Partajat (partajat) sau V = Valid (valid) sau SC = Partajat curat (partajat curat)
  • Date potențial partajate cu alte cache-uri. Datele pot fi curate sau murdare. Termenul „curat” din SC este înșelător, deoarece poate fi și murdar (vezi Protocolul Dragon )
• I = Invalid
  • Linie cache nevalidă. Dacă linia cache nu este prezentă (eticheta nu se potrivește) este echivalentă cu o linie nevalidă, prin urmare, date nevalide înseamnă date prezente, dar nevalide sau neprezente în cache

Stări speciale

• F = Forward sau R = Recent
  • stări suplimentare ale protocolului MESI . Ultimele date citite. Este o stare specială „Validă”, care este proprietarul datelor partajate nemodificate , utilizat în unele protocoale extinse MESI (MERSI sau R-MESI IBM ^{[2] [3]} , MESIF - Intel ^{[4] [5]} ). Starea R / F este utilizată pentru a permite „Intervenția” atunci când datele sunt „Valide”, dar partajate cu alte cache-uri. Acest cache este responsabil pentru intervenție (intervenție partajată). La o cerere de citire a magistralei, datele sunt furnizate din acest cache în loc de memorie. MERSI și MESIF sunt același protocol numai cu o terminologie diferită (F în loc de R). Uneori, R este denumit și „Shared Last” - ultimul partajat (S _L ) ^{[6] [7]} . Starea R (recentă) este utilizată nu numai în protocolul MERSI = R-MESI, ci și în alte câteva protocoale. Această stare poate fi utilizată împreună cu alte state. De exemplu RT-LUNI , HR-LUNI, HRT-LUNI, HRT-ST-LUNI ^{[8] [9]} . Toate protocoalele care utilizează această stare vor fi denumite tip R-MESI.
• H = Hover - H-MESI (stare suplimentară a protocolului MESI) ^[10]
  • Starea Hover (H) (suspendat) permite unui cache să păstreze o adresă în director, chiar dacă valoarea liniei cache corespunzătoare este o copie nevalidă. Dacă valoarea corespunzătoare apare pe autobuz (etichetă de adresă coincidentă) din cauza unei „Citire” sau „Scriere” valide, datele liniei cache sunt actualizate cu o copie validă și starea sa s-a schimbat în S. Această stare poate fi utilizată împreună cu alte state, de ex HR-LUNI, HT-LUNI, HRT-LUNI, HRT-ST-LUNI ^{[8] [11] [12]}

Operațiuni de consistență Snoopy

Există trei operațiuni: tranzacții cu autobuzul, caracteristici ale datelor și operațiuni de cache:

• Tranzacții cu autobuzul : principalele operațiuni sunt:
  • Write Through : linia cache este actualizată atât în ​​cache, cât și în MM sau numai în MM (scriere fără alocare); simplu de implementat, utilizare cu lățime de bandă ridicată. Foarte bine pentru scripturi simple.
  • Write-Back : datele sunt scrise numai în cache. Datele sunt redactate în MM (Write-Back) numai atunci când vor fi înlocuite (înlocuire) sau când vor fi solicitate de celelalte cache (vezi Politica de Write ); soluție intermediară: Write Through pentru prima scriere, Write-Back pentru următoarele ( protocoale Write-once și Bull HN ISI Protocol ^[13] )
  • Scrie Alocare : în caz de ratare, datele sunt citite de „proprietar” sau de MM, atunci datele sunt scrise în cache (actualizate - scriere parțială) (vezi Politica de scriere )
  • Scrieți fără alocare : în caz de ratare, datele sunt scrise în MM fără implicarea cache-ului sau, la fel ca în protocolul Bull HN ISI , este scris în „proprietar”, adică în cache-ul D sau SD (actualizarea proprietarului) - actualizarea „Proprietarului”, dacă este prezent, altfel în MM; Write-no-Allocate este în mod normal asociat cu Write Through.
  • Intervenție în cache (sau în scurt timp „intervenție”)
    • Intervenție partajată: intervenție partajată-curată (intervenție pe date neschimbate); în cazul Read Miss (lipsa de citire) datele sunt furnizate de „proprietar” - E sau R / F sau chiar S în loc de MM (a se vedea Illinois , tipul IBM R-MESI și protocoalele Intel MESIF ):
    • Intervenție murdară (intervenție asupra datelor modificate): în cazul citirii ratate, datele sunt furnizate de „proprietarii” M (D) sau O (SD) sau E (R) (Nu pentru E (R) în propunerea originală a Protocol MOESI ^[14] și în alte implementări de tip MOESI) în loc de MM (de ex. Protocol MOESI, RT-MESI, ...)
    • „Intervenția” este o soluție mai bună decât „neintervenția”, deoarece tranzacțiile cache-to-cache sunt mult mai rapide decât accesarea MM, plus că reduce traficul de memorie (creșterea benzii). MESI extins Illinois și tipul R-MESI / MESIF sunt, prin urmare, mult mai eficiente decât protocolul MOESI (vezi MESI vs MOESI )
  • Invalidare : în cazul Scrierii cu starea S (V) sau O (SD) (partajată) se trimite o tranzacție cu autobuzul pentru a invalida toate copiile celorlalte cache (Scriere-invalidare)
  • Scriere-difuzare (Scriere-actualizare) : (scriere distribuită), în cazul "Scriere Hit" cu starea S (V) sau O (SD) (partajată) o scriere de actualizare este trimisă tuturor celorlalte cache pentru a-și actualiza copiile (de ex. Intel Nehalem ^[15] , protocolul Dragon (Xerox), Firefly (DEC). Actualizarea altor cache-uri se numește uneori și Snarfing. Cache-urile scotocesc autobuzul și dacă există o lovitură, cache-ul intră în posesia datelor care tranzitează pe autobuz și își actualizează memoria cache. Chiar și actualizarea stării H în ( H-MESI ) poate fi definită ca snarfing. În primul caz apare doar într-o operație de scriere distribuită, în al doilea caz atât pentru citire, cât și pentru scriere.
  • Intervenție-difuzare : (Intervenție cu actualizare distribuită): în cazul unei tranzacții de intervenție, un cache cu starea H ( H-MESI ) își actualizează copia nevalidă cu valoarea trimisă pe autobuz și starea sa este schimbată în S ^[11]
  • Scrie Invalidate vs broadcast: w rite Invalidate este cel mai bun pentru mai multe scrieri, de obicei scrise parțiale, realizate de un procesor înainte ca linia cache să fie citită de un alt procesor. Scrierea-difuzarea (actualizarea) este mai bună atunci când aveți un singur producător pentru mulți consumatori de date, dar este mai rău atunci când un cache este actualizat cu date care nu vor fi utilizate ulterior (creștere inutilă a traficului de autobuz și creștere a interferenței cache-ului ). Invalidarea este soluția obișnuită.
• Caracteristicile datelor : Există trei caracteristici ale datelor cache:
  • Valabilitate : orice linii cache nevalide, adică stări MOES / D-SD-RV
  • Exclusivitate : datele sunt valabile numai pe un cache (date nepartajate) în starea M (D) sau E (R), cu MM-ul nu actualizat (murdar) în cazul lui M (D) și actualizat (curat) în cazul de E (R);
  • Proprietate - Proprietate ^[16] : cache-ul care este responsabil pentru furnizarea datelor solicitate în locul MM (Intervenție). - În funcție de protocol, memoria cache care trebuie efectuată poate fi S - E - M în MESI Illinois sau R / F - E - M în tipul R-MESI / MESIF sau M (D) sau O (SD) sau, de asemenea, E (R) (depinde de implementare) în tipul MOESI, (de ex. AMD64 , ^[14] , Bull HN ISI ^[13] - vezi mai jos operația „Read Miss”).
• Operațiuni cache : Operațiunile cache sunt:
  • Read Hit: datele sunt citite din cache. Statul rămâne neschimbat; deoarece aceasta este o operațiune evidentă, nu va mai fi luată în considerare mai târziu, chiar și în diagramele tranzacțiilor de stat
  • Read Miss : cererea de citire a datelor este trimisă în autobuz; există mai multe situații:
    • Date stocate numai în MM : datele sunt citite din MM; cache-ul este setat E (R) sau S (V); E (R) dacă se utilizează o linie specială de autobuz ( Linie partajată ) pentru a indica „ nu există date partajate ”. Folosit în toate protocoalele cu starea E (R), cu excepția protocoalelor Write-once și Bull HN ISI (a se vedea „Write Hit” de mai jos).
    • Date stocate în MM și în unul sau mai multe cache-uri în starea S (V) sau în R / F în tipul R-MESI / protocol MESIF : Există trei situații:
      • Protocolul Illinois - O rețea prioritară este utilizată pentru a atribui în mod arbitrar și temporar proprietatea unei copii S. Datele sunt furnizate de memoria cache selectată. Memoria cache solicitantă este setată la S ( intervenție partajată - intervenție între datele partajate cu MM clean);
      • Tip R-MESI / protocol MESIF cu o memorie cache în starea R / F - proprietar partajat („proprietar” de cache partajate); datele sunt furnizate de cache-ul R / F. Cache-ul care furnizează datele este schimbat în S, iar cache-ul solicitant este setat R / F (în citirea lipsa proprietății este întotdeauna preluată din cache-ul solicitant) - intervenție partajată ;
      • În toate celelalte cazuri, datele sunt furnizate de MM și memoria cache solicitată este setată S (V).
    • Date stocate în MM și într-un singur cache în stare E (R): datele sunt furnizate de cache-ul E (R) sau de MM, în funcție de protocol; furnizat de E (R) în MESI extins (de exemplu, Illinois , Pentium (R) II ^[17] ), tip R-MESI / MESIF și în unele implementări ale MOESI (de exemplu AMD64 ); cache-ul solicitant este setat la S (V) sau R / F în protocolul R-MESI tip / MESIF și cache-ul E (R) este schimbat în S (V) sau I în protocolul MEI. În toate celelalte cazuri, datele sunt furnizate de MM

• Datele s-au modificat într-unul sau mai multe cache-uri cu MM depășite :

• Protocol de tip MOESI - Date stocate în M (D) sau în O (SD) și celelalte cache-uri din starea S (V): datele sunt trimise în cache-ul solicitant de către „proprietarul” M (D) sau O (SD) ). Memoria cache solicitantă este setată la S (V) în timp ce M (D) este schimbat la O (SD); MM rămâne învechit.
• Tip protocol MESI sau MEI - Date stocate în M (D) și celelalte cache-uri în starea S (V); există două soluții:

1. datele sunt trimise din memoria cache M (D) către memoria cache solicitantă și simultan în MM (de exemplu, Illinois )
2. operațiunea se face în doi pași: tranzacția solicitantă este suspendată temporar. Aveți „Copierea înapoi” a datelor M (D) în MM, apoi tranzacția în așteptare continuă să citească datele din MM (de exemplu, protocoalele MESI și MSI Synapse )

Toate cache-urile sunt setate S (V)

• • Write Hit : datele sunt scrise în cache; există mai multe situații:
    • Cache în stare S (V) sau R / F sau O (SD) (cache-uri partajate)
      • Scrie invalid
        • Copiere înapoi: datele sunt scrise în cache și o tranzacție nevalidă este trimisă pe autobuz pentru a invalida celelalte cache; cache-ul este setat M (D)
        • Write Through ( Write-once , Bull HN ISI ): datele sunt scrise în cache și în MM invalidând toate celelalte cache. Memoria cache este setată la R (E)
      • Scrieți difuzarea (de exemplu, Firefly , Dragon ); datele sunt scrise în cache și o tranzacție de „difuzare” este trimisă pe autobuz pentru a actualiza toate celelalte cache cu o copie; memoria cache este setată M (D) dacă „linia partajată” nu este activă, altfel este setată O (SD). Toate celelalte cache sunt setate S (V)
    • Cache cu starea E (R) sau M (D) (exclusivitate): scrierea se poate face local, fără nicio altă acțiune. Starea este setată (sau rămâne) M (D)
  • Scrie-o pe domnișoară
    • Scrie Alocați
      • Operațiunea de citire cu operație Intent to Modified ( RWITM ): În ceea ce privește o operație de citire plus o comandă nevalidă, ulterior cache-ul este scris (actualizat); memoria cache solicitantă este setată la M (D) și toate celelalte cache sunt invalidate
      • Scrierea difuzării (de ex. Firefly , Dragon ): la fel ca o Miss Read; dacă „linia partajată” nu este activă, datele sunt scrise în cache și setate M (D), altfel ca pentru un hit de scriere - transmisie de scriere
    • Write-no-Allocate : datele sunt trimise către MM sau ca în protocolul Bull HN ISI , numai către cache-urile D (M) sau SD (O), dacă sunt prezente, ocolind cache-ul.

Diverse protocoale de consistență

                                                                                Protocoale

• DA                                                                       Scrie prin
• MSI                                                                    Sinapsă^[1]
• MEI                                                                    IBM PowerPC 750 ^[18] , MPC7400 ^[11]
• MES                                                                   Firefly^[1]
• LUNI                                                                  Pentium II ^[17] , PowerPC, Intel Harpertown (Xeon 5400)
• MOSI                                                                 Berkeley^[1]
• MOESI                                                              AMD64 ^[19] , AMD Opteron AMD Opteron ^[20] , MOESI ^[14] , IBM T-MESI ^[12]

                                                                                Terminologia utilizată

• Illinois                                                                 D-VE-SI                      (= LUNA prelungită)^{[1] [21]}
• Scrie o singură dată sau Scrie mai întâi                                      DRVI                         (= LUNI)^{[1] [22] [23]}
• Berkeley                                                             D-SD-VI                      (= MOSI)^[1]
• Sinapsi                                                             DVI                            (= MSI)^[1]
• Licurici                                                                 D-VE-S                        (= MES) DEC^[1]
• balaur                                                               D-SD (SM?) - SC-VE (= MOES) Xerox^[1]
• Bull HN ISI                                                         D-SD-RVI                  (= MOESI) ^[13]
• Protocol MERSI (IBM) / MESIF (Intel)             R = Recent - IBM PowerPC G4 , MPC7400 ^{[2] [11]}

                                                                                F = Forward - Intel ^[4] , Intel Nehalem ^{[24] [15] [25]}

• RT-LUNI                                                           T = Etichetat - IBM ^[12]
• HRT-ST-LUNI                                                   H = Hover, R = Recent, T = Tagged, ST = Shared-Tagged - IBM ^{[8] [12]}
• Protocolul IBM POWER4                                 T-Mu-Me-MSS _L -I (L2 șapte stări) ^[6]

                                                                                Mu = Unsolicited Modified - Unsolicited Modified Exclusive - ( M ) ^[26]

                                                                                M = Exclusiv modificat - Exclusiv modificat

                                                                                T = Etichetat - Proprietar neexclusiv modificat ( O )

                                                                                Eu = Valid Exclusive - ( E )

                                                                                S = Partajat

                                                                                S _L = Shared Last - sourced local "- ( Shared Owner Local )

                                                                                I = invalid - ( I )

Protocol MESI

Protocol MESI - Diagrama tranzacției de stat

State LUNI = DRVI

- Utilizarea „liniei partajate” pentru a determina copii partajate (partajate) pe alte cache-uri

• Operațiuni ale procesorului

• Citește domnișoara

Există două implementări alternative: MESI standard (fără intervenție) și MESI extins (cu intervenție)

1. LUNI „fără intervenție” (de exemplu, PowerPC 604 ^[27] )

- Dacă aveți o copie M într-un cache, tranzacția este oprită și așteaptă până când cache-ul M actualizează MM, atunci tranzacția va continua citirea datelor din MM. Starea ambelor cache este setată la S

- în caz contrar, datele sunt citite de MM. Dacă „linia partajată” este „pe” cache-ul este setat la S altfel E

2. LUNI "Intervenție" din M și E (de exemplu, Pentium (R) II ^[17] )

- Dacă aveți o copie a lui M sau E într-un cache (exclusivitate), datele sunt furnizate cache-ului solicitant de către M sau E (intervenție). Dacă este trimis de M, datele sunt, de asemenea, scrise în MM în același timp (copiați înapoi). Toate cache-urile sunt setate la S

- în caz contrar, datele sunt citite de MM. Dacă „linia partajată” este „pe” cache-ul este setat la S altfel E

• Scrie Hit

- Dacă cache-ul este M sau E (exclusivitate), scrierea se poate face local, fără nicio altă acțiune

- în caz contrar, datele sunt scrise în cache și o tranzacție nevalidă este trimisă pe autobuz pentru a invalida toate celelalte cache

- Memoria cache este setată la M

• Scrie-o pe domnișoară

- O instrucțiune RWITM este trimisă pe autobuz. Operațiunea se face în doi pași: „Citiți Miss” cu o comandă „invalid” pentru a invalida toate celelalte cache-uri, apoi ca într-un „Write Hit” cu cache în starea M (consultați Operațiuni Cache-Write Miss ).

• Tranzacții cu autobuzul

• Citire autobuz

- dacă M este „fără intervenție”, datele sunt trimise către MM (Copiere înapoi)

- dacă M și „Intervenție”, datele sunt trimise la memoria cache solicitantă și către MM (Copiere înapoi)

- dacă E (*) și „Intervenție”, datele sunt trimise în memoria cache solicitantă

- Starea s-a schimbat (sau rămâne) în S

• Scriere autobuz - ( RWITM )

- Ca și în cazul „Citit autobuz”

- Memoria cache este setată la „Invalid” ( I )

• Tranzacție autobuz de invalidare

- Memoria cache este setată la „Invalid” ( I )

• Operațiuni

- Scrie Alocați

- Intervenție : de la M la E (*)

- Scrieți invalid

- Copiere înapoi : Înlocuirea lui M

(*) - LUNA prelungită

Protocolul MOESI - Diagrama tranzacției de stat

Protocol MOESI

Stări MEOSI = DR-SD-VI = IBM T-MESI ^[12]

- Utilizarea „liniei partajate” pentru a determina copii partajate (partajate) pe alte cache-uri

• Operațiuni ale procesorului

• Citește domnișoara

- Dacă există o copie într-un alt cache în starea M sau O sau E (*), datele sunt furnizate de acest cache (Intervenție). Memoria cache solicitantă este setată la S , M se schimbă la O și E la S

- în caz contrar, datele sunt citite de MM

- Dacă „linia partajată” este „pe” cache-ul solicitant este setat S altfel E

• Scrie Hit

- Dacă cache-ul este M sau E (exclusivitate), scrierea se poate face local, fără nicio altă acțiune

- în caz contrar, O sau S (partajare) se trimite o tranzacție nevalidă pe autobuz pentru a invalida celelalte cache.

- Starea sa schimbat (sau rămâne) în M

• Scrie-o pe domnișoară

- O operațiune RWITM este trimisă pe autobuz

- Datele sunt furnizate de „proprietar” sau de MM ca în Read Miss, apoi datele sunt scrise în cache (actualizat = scriere parțială)

- Cache-ul este setat la M, iar celelalte cache-uri sunt setate la I

• Tranzacții cu autobuzul

• Citire autobuz

- Dacă cache-ul este M sau O sau E (*) datele sunt trimise către cache (intervenție). Dacă memoria cache este E , starea sa schimbat în S , altfel este setată (sau rămâne) O

- altfel statul s-a schimbat în S

• Scriere autobuz - ( RWITM )

- Dacă cache-ul este M sau O sau E (*) datele sunt trimise către cache (intervenție)

- Memoria cache este setată la „Invalid” ( I )

• Tranzacția autobuzului de invalidare

- Memoria cache este setată la „Invalid” ( I )

• Operațiuni

- Scrie Alocați

- Intervenție : de către MOE (*)

- Scrieți invalid

- Copy-Back : Înlocuirea MO

- (*) în funcție de tipul de implementare pentru E

Diagrama tranzacției statului Illinois

Protocolul Illinois

State LUNI = DRVI ^[1]

- Caracteristici:

- Este o extensie a protocolului MESI

- Utilizarea unei rețele prioritare pentru intervenție partajată (intervenție pe date partajate)

- Diferențe față de MESI: intervenție nu numai de la E și M și de la S (a se vedea Cache-Read Miss Operations - punctul 1 )

• Operațiuni

- Scrie Alocați

- Intervenție : de la MES

- Scrieți invalid

- Copiere înapoi : Înlocuirea lui M

Protocolul Write-Once - Diagrama tranzacției de stat

Protocolul Write-Once (sau Write-First)

State DRVI (LUNI) ^{[1] [22] [23]}

- Caracteristici:

- Neutilizarea „liniei partajate” (protocol pentru magistrala standard sau autobuzul nemodificabil)

- Scrieți prin prima lovire de scriere în starea V , apoi Copiați înapoi

• Operațiuni ale procesorului

• Citește domnișoara

- Dacă există o copie D într-un alt cache, datele sunt furnizate de acest cache (intervenție) și în același timp sunt scrise și în MM (Copy-Back).

- în caz contrar, datele sunt citite de MM

- toate cache-urile sunt setate V

• Wiite Hit

- Dacă memoria cache este D sau R (exclusivitate), scrierea se face local fără nicio altă acțiune și starea este setată (sau rămâne) D

- în caz contrar, V (primul Write Hit) datele sunt scrise în cache și în MM (Write Through) invalidând toate celelalte cache (Write-Invalidate). Cache-ul este setat la R

• Wiite domnișoară

- În ceea ce privește Read Miss cu o comandă „invalidă” ( RWITM ) plus un hit de scriere în starea D (actualizare). Cache-ul este setat D și toate celelalte cache-uri sunt „nevalide” ( I )

- Notă - Write Through se face numai în „Write Miss”. Trebuie remarcat faptul că, în acest caz, este încă necesară o tranzacție cu autobuzul pentru a invalida celelalte cache-uri și, prin urmare, este posibil să profitați de acest fapt pentru a actualiza și MM. În „Write Miss”, pe de altă parte, nu mai sunt necesare tranzacții, astfel încât Write Through ar deveni o operațiune inutilă dacă memoria cache ar fi actualizată din nou.

• Tranzacții cu autobuzul

• Citire autobuz

- Dacă cache-ul este D , datele sunt trimise din acest cache către cache-ul solicitant (intervenție) și, de asemenea, către MM (copiere). Cache-ul este setat V

- altfel starea s-a schimbat (sau rămâne) în V

• Scriere autobuz - ( RWITM )

- Dacă memoria cache este D , datele sunt trimise către memoria cache solicitantă (intervenție)

- Memoria cache este setată la „Invalid” ( I )

• Tranzacție autobuz de invalidare

- Memoria cache este setată la „Invalid” ( I )

• Operațiuni

- Scrie Alocați

- Intervenție : de D

- Write Through : primul Write Hit în starea V

- Scrieți invalid

- Copy-Back : Înlocuirea lui D

Bull HN ISI Protocol - Diagrama tranzacției de stat

Protocolul Bull HN ISI

Stări D-SD-RVI (MOESI) Protocol brevetat (F. Zulian) ^[13]

- Caracteristici:

- MOESI - extensie a protocolului Write-once

- Scrieți-nu-alocați la ratări cu actualizare D sau SD

- Nu folosesc RWITM

- Nu se folosește „linia partajată”

• Operațiuni ale procesorului

• Citește domnișoara

- În ceea ce privește MOESI cu „linie partajată” „activată” și intervenție numai de „proprietar” D sau SD și nu de R

• Wiite Hit

- Dacă cache-ul este D sau R , ca și pentru MOESI, scrierea se face local, fără nicio altă acțiune. Cache-ul este setat (sau rămâne) D

- Dacă SD sau V (prima scriere), la fel ca la Write-Once, datele sunt scrise în cache și în MM (Write Through), invalidând toate celelalte cache (Write-Invalidate). Cache-ul este setat la R

• Scrie-o pe domnișoară

- Datele sunt trimise pe autobuz ocolind cache-ul (Write-no-allocate)

- Dacă există o copie „proprietar” D sau SD , „proprietarul” este actualizat (vezi Scrie-fără-alocare ) în timp ce celelalte cache sunt invalidate. „Proprietarul” este setat (sau rămâne) D. MM rămâne „murdar” (nu este actualizat)

- în caz contrar, datele sunt trimise către MM invalidând celelalte cache (Write-Invalidate)

• Tranzacții cu autobuzul

• Citire autobuz

- În ceea ce privește MOESI cu intervenție numai de către „proprietarul” D sau SD

• Scriere autobuz (Scriere actualizare / Invalidare scriere)

- Dacă memoria cache este D sau SD , memoria cache este actualizată, altfel este setată „Invalid” ( I )

• Operațiuni

- Scrieți-nu-alocați : în lipsă

- Scrieți actualizarea : la dor

- Write Through : pentru prima scriere, apoi copiați înapoi

- Actualizare scriere / Invalidare scriere

- Intervenție : din SD-D

- Copy-Back : înlocuirea D sau SD cu invalid

Obs. - Acesta este singurul protocol care are tranzacții OE (SD-R), dar singurul care nu are tranzacții MI (DI) și este, de asemenea, singurul care folosește Write-no-allocate on miss.

Protocolul sinapsă - Diagrama tranzacției de stat

Protocol sinapsă

Statele DVI (MSI) ^[1]

- Caracteristici:

- Caracteristica acestui protocol este de a avea, pentru fiecare linie cache, o etichetă cu un singur bit în MM, indicând că o linie cache este în starea D.

- Acest bit previne o posibilă condiție Race dacă cache-ul D nu răspunde suficient de rapid pentru a împiedica MM să răspundă imediat înainte de a fi actualizat.

- Datele provin întotdeauna de la MM

- Nu se folosește „linia partajată”

• Operațiuni ale procesorului

• Citește domnișoara

- Dacă există o copie D într-un alt cache, tranzacția citită este respinsă. Copia D este scrisă înapoi în MM și își schimbă starea în V , apoi memoria cache solicitantă trimite înapoi o nouă tranzacție de citire și datele sunt citite din MM.

- în caz contrar, datele sunt citite de MM.

- Cache-ul este setat V

• Scrie Hit

- Dacă memoria cache este D , scrierea se poate face local fără nicio altă acțiune.

- altfel V , ca în cazul Read Miss, incluzând și un transfer de date din memorie plus o comandă nevalidă ( RWITM ). Acest lucru se face numai pentru a invalida celelalte copii V, deoarece acest protocol nu acceptă o tranzacție nevalidă.

- Cache-ul este setat D. Toate celelalte cache-uri sunt setate „Invalid” ( I )

• Scrie Miss ( RWITM )

- În ceea ce privește Read Miss, dar cu o comandă invalidă. Linia cache este citită din MM, apoi cache-ul este scris (actualizat). Cache-ul este setat D. Toate celelalte cache-uri sunt setate „Invalid” ( I ).

• Tranzacții cu autobuzul

• Citire autobuz

- Dacă memoria cache este D , datele sunt trimise înapoi la MM (Copy Back). Cache-ul este setat V

- altfel statul rămâne în V.

• Scriere autobuz ( RWITM )

- Dacă memoria cache este D , datele sunt trimise înapoi la MM (Copiere înapoi)

- Memoria cache ( D sau V ) este setată la „Invalid” ( I )

• Operațiuni

- Scrie Alocați

- Intervenție : fără intervenție

- Scrieți invalid : RWITM

- Nicio tranzacție invalidă

- Copy-Back : înlocuitor pentru D

Protocolul Berkeley - Diagrama tranzacțiilor de stat

Protocolul Berkeley

Statele D-SD-VI (MOSI) ^[1]

- Caracteristici:

- În ceea ce privește MOESI fără statutul E

- Nu se folosește „linia partajată”

• Operațiuni ale procesorului

• Citește domnișoara

- Datele sunt furnizate de „proprietar”, adică de D sau de SD în caz contrar de MM. D s-a schimbat în SD

- Cache-ul este setat V

• Wiite Hit

- Dacă cache-ul este D (exclusivitate), scrierea se face local, fără nicio altă acțiune

- altfel ( SD sau V ), o tranzacție nevalidă este trimisă pe autobuz pentru a invalida celelalte cache.

- Cache-ul este setat (sau rămâne) D

• Scrie-o pe domnișoară

- O operațiune RWITM este trimisă pe autobuz

- În ceea ce privește Read Miss, datele sunt furnizate de „proprietar”, adică de D sau SD sau de MM, apoi cache-ul este actualizat

- Cache-ul este setat D. Toate celelalte cache sunt setate I

• Tranzacții cu autobuzul

• Citire autobuz

- Dacă memoria cache este D sau SD , datele sunt trimise către memoria cache solicitantă (intervenție). Cache-ul este setat (sau rămâne) în SD

- altfel cache-ul rămâne în V

• Scriere autobuz ( RWITM )

- Dacă memoria cache este D sau SD , datele sunt trimise pe autobuz (intervenție)

- Memoria cache este setată la „Invalid” ( I )

• Tranzacție autobuz de invalidare

- Memoria cache este setată la „Invalid” ( I )

• Operațiuni

- Scrie Alocați

- Intervenție : de la D-SD

- Scrieți invalid

- Copy-Back : înlocuirea D și SD

Firefly Protocol - Diagrama tranzacției de stat

Firefly Protocol (DEC)

State D-VE-S (MES) ^[1]

- Caracteristici:

- Nu utilizați starea „Invalid”

- Scriere-difuzare + Scriere prin

- Utilizarea „liniei partajate”

- Scrierea-difuzarea evită necesitatea statutului „Invalid”

- Intervenție simultană din toate cache-urile (intervenție comună și murdară - pe date nemodificate și modificate)

- Acest protocol necesită o magistrală sincronă

• Operațiuni ale procesorului

• Citește domnișoara

- Ogni cache è l' "owner", cioè tutte le altre cache con una copia inviano simultaneamente il dato sul bus (intervento simultaneo - la temporizzazione del bus è fissa cosicché le cache rispondono nello stesso ciclo), altrimenti il dato è fornito dalla MM.

- Se c'è una cache D , il dato è inviato simultaneamente anche in MM (Copy Back)

- Se c'è una copia nelle altre cache la "Shared line" è settata "on"

- Se la "Shared line" è "off" tutte le altre cache sono settate S altrimenti la cache richiedente è settata VE .

• Write Hit

- Se la cache è D o VE (esclusività), la scrittura è fatta localmente senza nessun'altra azione e la cache è settata D

- altrimenti S , una Write-broadcasting è inviata sul bus per aggiornare tutte le altre cache e la MM (Write Through)

- Se c'è una copia in un'altra cache, la "Shared line" è settata "on". Se la "Shared line" is "off" la cache è settata VE altrimenti tutte le cache sono settate S

• White Miss

- L'operazione è fatta in due step. Read Miss seguita da una Write Hit.

- Se il dato proviene da una cache (Shared Line "on") una Write-broadcasting è inviata sul bus per aggiornate tutte le altre cache e la MM (Write Through). Tutte le cache sono settate S

- altrimenti la cache è settata D

• Transazioni di Bus

• Bus Read

- Se hit ( D o VE o S ) il dato è inviato sul bus (intervento) e in caso di D il dato è scritto anche in MM. La cache è settata S

• Bus Write

- Se hit ( D o VE o S ) il dato è inviato sul bus (Intervento).

- Tutte le cache sono settate S

• Write Broadcasting

- La cache è aggiornata con il nuovo dato. Lo stato rimane S

• Operazioni

- Write Allocate

- Intervention : da D-VE-S (da tutte le cache "valide")

- Write-broadcasting - Write through

- Copy-Back : rimpiazzo di D e su qualsiasi transazione con una cache D

Dragon Protocol - State Transaction Diagram

Protocollo Dragon (Xerox)

Stati D-SD-VE-SC (MOES) ^[1] Nota - lo stato SC , nonostante il termine "clean", può essere "clean" o "dirty" come lo stato S degli altri protocolli. SC e S sono equivalenti.

- Caratteristiche:

- Non uso di stato "Invalido"

- Write-broadcasting (non Write Through)

- Uso della "shared line"

- Write-broadcasting evita la necessità dello stato "Invalido"

• Operazioni del Processor

• Read Miss

- Ii dato è fornito dall' "owner", vale a dire da D o da SD altrimenti dalla MM. D è cambiato in SD

- Se la "shared line" è "on" la cache è settata SC altrimenti VE

• Wiite Hit

- Se la cache è D o VE (esclusività), la scrittura è fatta localmente senza nessun'altra azione. La cache è settata (o rimane) D

- altrimenti SD o SC (sharing) il dato è scritto in cache e una Write-broadcasting è inviata sul bus per aggiornare tutte le altre cache - La MM non è aggiornata (non Write through)

- Se c'è una copia in un'altra cache, la "Shared line" è settata "on"

- Se la "Shared Line" è "on" la cache è settata SD , altrimenti D . Tutte le altre eventuali copie sono settate SC

• Wiite Miss

- Come per la Read Miss, il dato è inviato dall' "owner", D o SD o MM, poi la cache viene aggiornata.

- Se c'è una copia in un'altra cache, la "Shared line" è settata "on"

- Se la "Shared Line" è "on" il dato aggiornato è distribuito alle altre cache e lo stato è settato SD . Tutte le altre cache sono settate SC

- altrimenti la cache è settata D

• Transazioni di Bus

• Bus Read

- SE la cache è D o SD il dato è inviato alla cache richiedente (intervention). La cache è settata (o rimane) SD

- altrimenti la cache rimane SC

• Bus Write

- Se la cache è D o SD il dato è inviato sul bus (Intervention)

- La cache è settata SC

• Write Broadcasting

- La cache è aggiornata con il nuovo dato. La cache rimane SC

• Operazioni

- Write Allocate

- Intervention : da D-SD (ma non da VE)

- Write-broadcasting

- Copy-Back : rimpiazzo di D-SD

MERSI - MESIF Protocol - State Transaction Diagram

Protocollo MERSI (IBM) / MESIF (Intel)

Stati MERSI o R-MESI Stati MESIF Protocolli brevettati - IBM (1997) ^[11] - Intel (2002) ^[28]

- MERSI e MESIF sono lo stesso identico protocollo (solamente lo stato del nome è differente, F invece di R )

- Caratteristiche:

- Le stesse funzionalità del protocollo Illinois

- Un nuovo stato R (Recent) / F (Forward) è l' " owner " per i dati shared-clean" (condivisi).

- La "shared ownership" (l'owner delle cache condivise "clean" - non modificate) non è assegnata da una rete di priorità come con Illinois , ma è sempre assegnata all'ultima cache con Read Miss, settando il suo stato R / F

- La "shared ownership" è temporaneamente persa nel caso di rimpiazzo della linea R / F . La "ownership" è riassegnata alla prima successiva Read Miss con cache "shared" non modificate

- Uso della "shared line"

• Operazioni

- Write Allocate

- Intervention : da MER/F

- Write Invalidate

- Copy-Back : rimpiazzo di M

MESI vs MOESI

MESI e MOESI sono i protocolli più popolari È comune opinione che MOESI sia un'estensione del protocollo MESI e perciò più sofisticato e più performante. Questo è vero solamente se confrontato con MESI standard, cioè con MESI senza intervento tra cache condivise "clean" (dato non modificato rispetto alla MM). MESI con intervento tra cache condivise "clean", come MESI Illinois o gli equivalenti protocolli 5-stati MERSI / MESIF , sono molto più performanti del protocollo MOESI . In MOESI, le operazioni cache-cache sono fatte solamente su dati modificati. Invece nei protocolli tipo MESI Illinois e MERSI / MESIF , le operazioni cache-cache sono sempre fatte" sia su dati "clean" che su dati modificati . Nel caso di dati modificati, l'intervento è fatto dall' "owner" M, ma l'ownership non è persa perché essa migra in un'altra cache (la R/F in MERSI / MESIF o in una cache selezionata come nell caso di Illinois . L'unica differenza è che la MM deve essere aggiornata. In ogni caso anche in MOESI questa transazione dovrà più tardi comunque essere fatta in caso di rimpiazzo dell' "owner", se nessun'altra modifica avviene nel frattempo. Tuttavia questo è un limite minore rispetto a una transazione di memoria dovuta ad un non intervento, come nel caso di dati non modificati (clean) per il protocollo MOESI. (vedi per es. "Performance evaluation between MOESI (Shanghai) and MESIF Nehalem-EP" ^[24] ) I sistemi più avanzati usano solamente il protocollo MERSI / MESIF |R-MESI type / MESIF (IBM / Intel) oi più completi RT-MESI , HRT-ST-MESI e MERSI / MESIF che sono l'unione evoluta dei protocolli MESI e MOESI. Nota: Trasferimenti cache-cache sono soluzioni efficienti per sistemi multiprocessor/multicore connessi direttamente tra loro, ma meno nei sistemi con Cache remota come nei sistemi NUMA dove è preferibile MESI standard. Esempio nel Protocollo POWER4 IBM lo "shared intervention" è fatto solo "localmente" e non tra moduli remoti.

RT-MESI Protocol - State Transaction Diagram

Protocollo RT-MESI

States RT-MESI protocollo brevettato IBM ^{[8] [12]}

- Caratteristiche:

- Unione di MESI e MOESI

- Shared Intervention + Dirty Intervention (sia tra cache "clean" che tra cache con dati modificati)

- Stesse funzionalità del protocollo R-MESI con un nuovo stato T = Tagged, equivalente allo stato O

- Migrazione del "Dirty-Owner"

- L' "owner" (sia Shared che Dirty) è sempre l'ultima cache richiedente (il nuovo "owner" ( LRU ) ha meno probabilità di essere deallocato a breve rispetto a quello più vecchio)

- Gli "owner" sono T , M , E , R (tutti eccetto S )

- Uso della "shared line"

• Operazioni del Processor

• Read Miss

- Se c'è una copia M o T (dirty-ownership) in un'altra cache, il dato è fornito da questa cache (dirty-intervention). La cache richiedente è settata T ei precedenti M o T sono cambiati in S

- Se c'è una copia E o R (shared-ownership) in un'altra cache, il dato è fornito da questa cache (shared-intervention). La cache richiedente è settata R ei precedenti E o R sono cambiati in S

- altrimenti il dato è letto dalla MM e la cache è settata R .

• Write Hit

- Se la cache è M o E (esclusività), la scrittura è fatta localmente senza nessun'altra azione

- altrimenti T o R o S (sharing) una transazione di "Invalida" è inviata sul bus per invalidare tutte le altre cache.

- La cache è settata (o rimane) M e tutte le altre cache sono settate I

• Write Miss

- Un'operazione di RWITM è inviata sul bus

- Il dato è fornito dall' "owner" o dalla MM come nella Read Miss, poi il dato è scritto (aggiornato) in cache

- La cache è settata M e tutte le altre cache sono settate I

• Transazioni di Bus

• Bus Read

- Se la cache è T o M o R o E il dato è inviato alla cache richiedente (intervention).

- La cache è settata (o rimane) S

• Bus Write - ( RWITM )

- Se la cache è T o M o R o E il dato è inviato alla cache richiedente (intervention)

- La cache è settata "Invalida" ( I )

• Transazione di Bus di Invalida

- La cache è settata "Invalida" ( I )

• Operations

- Write Allocate

- Intervention : da TMRE

- Write Invalidate

- Copy-Back : rimpiazzo di TM

Protocollo RT-ST-MESI

È un miglioramento del protocollo RT-MESI ^[12] ed è un subset del protocollo HRT-ST-MESI ^[8]

S _T = Shared-Tagged

- L'uso dello stato "Shared-Tagged" permette di mantenere l' "intervention" dopo una deallocazione di una linea di cache "Tagged"

- Nel caso di rimpiazzo di T (deallocazione della linea di cache), il dato deve essere scritto indietro in MM e così perdere la "ownershisp". Per evitare ciò può essere usato un nuovo stato S _T . In caso di Read Miss il precedente T è settato S _T invece di S . S _T sarà il candidato per rimpiazzare la ownership in caso di deallocazione di T . La transazione di "Copy Back" di T è bloccata da S _T (la memoria non è aggiornata) che cambia il suo stato in T . Nel caso di una nuova Read MIss da un'altra cache, quest'ultima è settata T , il precedente T è cambiato in S _T e precedente S _T è cambiato in S .

Un miglioramento aggiuntivo può essere ottenuto usando più di uno stato S _T , S _T1 , S _T2 ,… S _Tn .

- In Read Miss, T è cambiato in S _T1 e gli indici degli altri S _Ti sono incrementati di "1"

- In caso di deallocazione di T , S _T1 blocca la transazione di "Copy Back" e cambia il suo stato in T e tutti gli indici degli S _Ti sono decrementati di "1".

- In caso di una deallocazione, per esempio di S _Tk , la catena sarà interrotta e tutti gli S _Ti con indice maggiore di "k" saranno automaticamente persi in termini di S _T , e saranno considerati de facto solamente come stati S , anche se essi manterranno lo stato S _T . Tutto ciò perché solo S _T1 interviene per bloccare e sostituirsi a T . Per es. se si ha una situazione tipo T , S _T1 , S _T3 , S _T4 con S _T2 rimpiazzato, se T sarà rimpiazzato la nuova situazione sarà T , S _T2 , S _T3 senza nessun S _T1 .

HRT-ST-MESI Protocol - State Transaction Diagram

Protocollo HRT-ST-MESI

Protocollo IBM brevettato HRT-ST-MESI completo ^{[8] [12]} - Stato I = Tag invalido (*) - Dati Invalidi - Stato H = Tag Valido - Dati Invalidi - Lo stato I è settato all'inizializzazione e il suo stato cambia solo dopo una Read o Write miss del processor. Poi non tornerà più in questo stato. - H ha le stesse funzionalità dello stato I ma con in più la capacità di catturare le transazioni del bus aventi lo stesso Tag della directory e aggiornare la cache dati. - Dopo la prima utilizzazione I viene rimpiazzato da H nelle sue funzioni

- Le principali funzioni sono:

- Write Back

- Intervento sia su dati dirty che shared-clean - da T - M - R - E

- Stati di riserva del Tagged (Shared-Tagged)

- Auto aggiornamento dello stato invalido H (Hover)

(*) - Nota: Il Tag per definizione è sempre valido, ma sino al primo aggiornamento della linea di cache è considerato invalido per non aggiornare la cache anche quando questa linea non è ancora stata richiesta e usata.

Protocollo POWER4 IBM

Stati MT-Me-SI -Mu-S _L = RT-MESI+Mu ^[6]

- Uso della "shared line"

- Usato in Sistemi multi-core/moduli - multi-cache L2 ^[6]

- Questo protocollo è equivalente al protocollo RT-MESI per sistemi con cache L2 multiple su sistemi multi moduli .

• S _L - "Shared Last" equivalente a R nel RT-MESI protocollo
• Me - "Valid Exclusive" = E (valido esclusivo)
• Mu - unsolicited modified state - stato modificato esclusivo non sollecitato

- stato speciale - richiesta di prenotazione scrittura e lettura "doubleword" (per l'implementazione a 64-bit)

- "Shared intervention" da S _L è fatto solo tra cache L2 dello stesso modulo

- "Dirty intervention" da T è fatto solo tra cache L2 dello stesso modulo

• Operations

- Write Allocate

- Intervention : da MT-VE-S _L = MOES _L

- Write Invalidate

- Copy-Back : rimpiazzo di MT

- Nota: T e S _L - Intervento solo locale al modulo

Considerazione generale sui protocolli

Sotto certe condizioni il più efficiente e completo protocollo risulta essere il protocollo HRT-ST-MESI

- Write Back

- Intervento sia su dati dirty che shared-clean - da T - M - R - E

- Stati di riserva del Tagged (Shared-Tagged)

- Auto aggiornamento dello stato invalido H (Hover)

Note

Portale Informatica : accedi alle voci di Wikipedia che trattano di informatica