UMA/SMP amb snooping

En una UMA (Uniform Memory Access) o SMP (Symmetric MultiProcessor), tots els cores comparteixen un únic espai d’adreces i accedeixen a una memòria «central» amb un temps d’accés uniforme (idealment, la mateixa latència per a tots).

El mecanisme de snooping és el natural per a aquesta arquitectura:

• La coherència es manté a granularitat de línia de caché.
• Cada caché guarda localment l’estat de les seves línies (estat distribuït).
• El bus serveix com a medi de broadcast que fa visibles totes les transaccions i en defineix l’ordre global.
• Les cachés monitoritzen (snoop) el bus i actuen sobre els esdeveniments rellevants mitjançant controladors snoopy (SCC: Snoopy Cache Controllers).

Protocol MSI: estats d’una línia de caché

El protocol MSI és el protocol de snooping de referència. Cada línia present en una caché porta associats uns bits d’estat que indiquen la seva situació respecte a la resta del sistema:

• M (Modified): la caché té l’única còpia vàlida i aquesta és diferent del valor a memòria principal (dirty). Cap altra caché pot tenir la línia en M o S simultàniament.
• S (Shared): la còpia és idèntica a memòria principal (clean). Pot existir en diverses cachés alhora.
• I (Invalid): la línia no és vàlida (o directament no és present a la caché). Qualsevol accés a aquesta línia provocarà un miss.

Esdeveniments i transicions d’estat

Aquests estats canvien en resposta a dos tipus d’esdeveniments. D’una banda, els CPU events són les operacions que el processador local vol fer sobre la línia. De l’altra, quan el controlador de caché necessita comunicar-se amb la resta del sistema, genera accions al bus (bus events) que totes les altres cachés poden observar.

La clau per entendre el protocol és que els CPU events provoquen bus events, i els bus events observats per les altres cachés (snooped) provoquen canvis d’estat en les seves còpies.

CPU events (accions del processador local):

• PrRd (Processor Read): el processador vol llegir la línia.
• PrWr (Processor Write): el processador vol escriure a la línia.

Bus events (accions generades pel controlador de caché):

• BusRd: demana una còpia de la línia sense intenció de modificar-la (lectura).
• BusRdX: demana una còpia de la línia amb intenció de modificar-la (escriptura). En fer-ho, invalida totes les altres còpies!
• BusUpgr: només s’usa si ja es té la línia en S (hit), i la converteix a M. No es transfereixen dades, perquè el sol·licitant ja té la línia, però sí que s’invaliden les còpies.
• Flush: posa la línia al bus per servir dades a altres cachés, o per fer writeback a memòria quan s’expulsa una línia dirty.

Transicions d’estat

Amb els estats i els esdeveniments definits, podem descriure exactament com reacciona cada línia de caché davant de cada situació. Les transicions es divideixen en dos grups: les provocades per accions del processador local (PrRd, PrWr) i les provocades per observar transaccions d’altres processadors al bus (snooped events).

Des de l’estat I (Invalid):

• PrRd → genera BusRd → passa a S
• PrWr → genera BusRdX → passa a M

Des de l’estat S (Shared):

• PrRd → hit local, es queda a S
• PrWr → genera BusUpgr → passa a M
• Snoop BusRd → no cal fer res, es queda a S
• Snoop BusRdX o BusUpgr → invalida → passa a I

Des de l’estat M (Modified):

• PrRd → hit local, es queda a M
• PrWr → hit local, es queda a M
• Snoop BusRd → Flush (serveix dades) → passa a S
• Snoop BusRdX → Flush (serveix dades) → passa a I

▣Diagrama de transicions del protocol MSI. Les fletxes blaves representen transicions de lectura, les vermelles d’escriptura, i les grises invalidacions provocades per altres cores. Sempre que es fa un write es va cap a M, mentre que sempre que es fa un Rd es va cap a S. (figura al dossier, p. 9)

Provisió de la línia

Un aspecte fonamental és qui serveix les dades quan una caché les demana. Si alguna altra caché té la línia en estat M, ella és l’única que té el valor correcte (la memòria principal està desactualitzada), de manera que ha de fer un Flush per posar la línia al bus.

En canvi, si cap caché té la línia en M (totes estan en S o totes en I), la memòria principal la proporciona directament.

L’exemple següent il·lustra com interactuen tots aquests elements en un escenari concret amb dos cores que accedeixen a la mateixa línia de caché:

▣Els tres passos de l’exemple dibuixats amb els cores, el bus i la memòria, amb les fletxes de CPU event, bus event, snoop, dades i flush/wb. (figura al dossier, p. 10)

Optimitzacions del MSI: MESI, MOSI, MSIF

MSI és funcional però té casos comuns on fa massa trànsit. Per això apareixen extensions amb estats addicionals:

• MESI (+E, Exclusive): una línia neta que només existeix en una caché. Com que ningú més la té, es pot passar de E → M sense cap transacció de bus (s’estalvia el BusUpgr). Si un altre core la demana, E passa a S.
• MOSI (+O, Owned): una línia dirty que es pot compartir sense actualitzar memòria. La caché en estat O actua com a «propietària»: serveix les dades quan altres les demanen. Memòria principal s’actualitza només quan la línia O s’expulsa.
• MSIF (+F, Forward): quan hi ha diverses còpies netes (S), una es designa com a forwarder perquè sigui ella (i no la memòria) qui respongui peticions. Típicament, la darrera caché que va demanar la línia pren el rol F (explotant localitat temporal), mentre la resta queden en S.

Aquestes extensions es poden combinar: MESIF, MOESI, MOESIF, segons la implementació.

Cost de la coherència: bits d’estat per línia

Mantenir la coherència no surt gratis: cada línia de caché necessita uns bits d’estat addicionals perquè el hardware pugui saber en quina situació es troba cada línia. Aquests bits no contenen dades útils per al programa, però són imprescindibles perquè el protocol de coherència funcioni.

El nombre de bits que utilitzarem per línia depèn del protocol: amb MSI (3 estats) calen $\lceil \log_2 3 \rceil = 2$ bits per línia. Amb MESI o MOSI passa igual (4 estats, $\lceil \log_2 4 \rceil = 2$). A partir de 5 estats (MOESI, MOESIF…) ja en calen 3.

▣Sistema UMA: cada línia de caché porta 2–3 bits de coherència que indiquen el seu estat (M/S/I o variants). En UMA amb snooping, la memòria no necessita bits de coherència: cada caché gestiona els seus propis bits (estat distribuït). (figura al dossier, p. 11)

El cost total de coherència d’una caché es calcula com:

$$\text{Nombre de línies} = \frac{\text{Mida de la caché}}{\text{Mida de la línia}}$$ $$\text{Bits de coherència} = \text{Nombre de línies} \times \text{bits d'estat per línia}$$