NUMA amb directoris

En una arquitectura NUMA (Non-Uniform Memory Access), també hi ha un sol espai d’adreces compartit i es programa igualment amb load/store, però la memòria física està repartida en diversos nodes. Cada node té CPUs/cachés i la seva memòria «local».

• L’accés no és uniforme: llegir una dada de memòria local és més ràpid que llegir-la de memòria remota (d’un altre node).
• La localitat (on resideixen les dades i qui les usa) passa a ser crítica per al rendiment.

Limitacions del snooping en NUMA

Amb el mecanisme de snooping, el processador que inicia un accés envia un missatge a tots els altres processadors per saber l’estat d’una línia, independentment de si en tenen una còpia o no. Tot i que això pot ser viable en sistemes NUMA petits, en arquitectures més grans amb múltiples processadors i cachés, s’acaba generant un tràfic de coherència excessiu que satura el sistema.

Per garantir l’escalabilitat, s’utilitza la coherència basada en directoris (directory-based): en lloc de fer un broadcast massiu a totes les cachés, utilitzem un directori que registra exactament quins nodes tenen una còpia de cada línia, permetent una comunicació eficient i exclusivament punt a punt.

Protocol MSU: coherència basada en directori

El protocol MSU s’utilitza en arquitectures NUMA per mantenir la coherència de les dades sense dependre del snooping. A diferència del MSI, on la responsabilitat de la coherència està distribuïda entre totes les cachés (que «escolten» el bus), en el MSU la responsabilitat recau en el directori.

Tot i que parlem de «directori» en singular, en realitat no existeix un directori únic centralitzat. El directori es divideix en porcions (slices), de manera que cada node només emmagatzema l’estat de les línies de la seva pròpia memòria física, és a dir, aquelles on ell actua com a home node. Per tant, el directori és una estructura distribuïda entre tots els nodes del sistema.

Els tres estats globals que pot tenir una línia al directori del seu home node són:

• M (Modified): el directori indica que un únic node (l’owner) té l’exclusivitat sobre la dada. Aquest node en té una còpia modificada (dirty) i, per tant, la memòria principal està desactualitzada.
• S (Shared): el directori indica que un o més nodes tenen còpies vàlides de només lectura. En aquest estat, la memòria principal està actualitzada.
• U (Uncached): el directori indica que cap caché del sistema té la línia. La memòria principal és l’única que conté la dada vàlida.

Bits de presència (sharers list)

En una arquitectura UMA, el snooping utilitza el broadcast perquè tothom vegi totes les peticions. En canvi, en NUMA necessitem els bits de presència (un vector de bits amb un bit per cada node del sistema) perquè el directori sàpiga exactament quins nodes concrets tenen una còpia de la dada.

Aquests es diferencien dels bits d’estat (MSU) per la naturalesa de la informació que guarden:

• Els bits de coherència (MSU) responen a la pregunta «En quina situació es troba la dada?» (el seu estat de validesa global).
• Els bits de presència responen a la pregunta «On és geogràficament la dada?» (el mapa de nodes afectats).

D’aquesta manera sabem a quins nodes hem d’enviar els missatges d’invalidació de forma exclusivament punt a punt. Sense els bits de presència, el directori hauria d’enviar missatges a tots els nodes del sistema cada vegada que hi hagués una escriptura, perdent així tot l’avantatge d’escalabilitat de les arquitectures NUMA.

Rols dels nodes

En una transacció de coherència basada en directori, cada node pot exercir un d’aquests rols segons la seva relació amb la línia de memòria:

• Home node (node origen): node on resideix físicament la línia de memòria. Conté el slice del directori encarregat de coordinar la coherència d’aquella línia (emmagatzemant el seu estat MSU i els bits de presència).
• Local node (node sol·licitant): node amb el processador que inicia la petició (load o store) que provoca la fallada (miss) a la caché.
• Remote nodes (nodes remots): qualsevol altre node del sistema implicat en la transacció. Poden actuar com a:
  • Owner: node remot que té la línia modificada (dirty) i ha de proveir la dada.
  • Readers / Sharers: nodes remots que tenen còpies netes i han de rebre una invalidació.

Comandes del protocol de directori (simplificat)

Comandes del node local cap al home node:

• RdReq: demana còpia de la línia sense intenció de modificar.
• WrReq: demana còpia de la línia amb intenció de modificar.
• UpgrReq: demana permís per modificar una línia ja existent a la seva caché, invalidant les altres còpies.

Comandes del home node cap a nodes remots (si cal):

• Fetch: demana al node remot (owner) una còpia de la línia (resposta: Dreply).
• Invalidate: demana al node remot (reader) que invalidi la seva còpia (resposta: Ack).

Vegem aquest escenari amb 3 nodes (N0, N1, N2) i una línia X amb home node = N0. Inicialment cap caché té la línia (directori en estat U).

▣Els quatre passos dibuixats amb els tres nodes, el directori del home node i les fletxes de petició, dades, invalidació, fetch i ack. (figura al dossier, p. 14)

Punts clau de l’exemple:

• Cap missatge és broadcast. Al pas 3, el directori consulta els PB i envia Invalidate exclusivament a N2 (l’únic node amb còpia). Amb snooping, el missatge hauria anat a tots els nodes. Aquesta és la raó per la qual els directoris escalen millor.
• Els PB determinen a qui cal contactar. Sense ells, el directori no sabria quins nodes tenen còpies i hauria de fer broadcast, perdent tot l’avantatge d’escalabilitat.
• Qui serveix les dades depèn de l’estat. Si la línia és S o U, la memòria principal (MM) serveix directament. Si és M, la memòria està desactualitzada i cal un Fetch a l’owner (pas 4).
• UpgrReq vs WrReq. Al pas 3, N1 ja té la línia en S: usa UpgrReq per demanar permís d’escriptura sense transferir dades (ja les té). WrReq s’usaria si la línia fos I.

Cost de la coherència: bits del directori

A diferència d’UMA (on cada caché manté els seus propis bits d’estat i la memòria principal no necessita informació de coherència), en NUMA el directori ha d’emmagatzemar informació per cada línia de memòria. Per cada entrada del directori cal:

• Bits d’estat MSU: $\lceil \log_2 3 \rceil = 2$ bits per indicar si la línia és M, S o U.
• Bits de presència (presence bits): 1 bit per node ($N$ bits en total), per indicar quins nodes tenen una còpia.

Per tant, cada entrada del directori ocupa $2 + N$ bits, on $N$ és el nombre de nodes del sistema.

El cost total del directori d’un node es calcula com:

$$\text{Nombre d'entrades} = \frac{\text{Mida de la memòria local (MM)}}{\text{Mida de la línia de caché}}$$ $$\text{Bits del directori} = \text{Nombre d'entrades} \times (\underbrace{2}$${\text{MSU}} + \underbrace{N}{\text{presence bits}})

A més, cal recordar que cada caché dins del node també necessita els seus bits de coherència locals (2–3 bits per línia, com a UMA). Per tant, el cost total de coherència del sistema és la suma dels bits de directori (a la MM) i els bits d’estat locals (a cada caché).