El problema de la coherència de cache

Quan parlem de paral·lelisme a nivell de hardware, el primer que cal entendre és com estan organitzats els processadors i la memòria, perquè això determina com es comparteixen les dades i quin cost té accedir-hi. Els nostres objectius seran descobrir:

• Com es comuniquen els threads quan comparteixen memòria o necessiten una mateixa dada.
• Quin overhead introdueix el fet que cada core tingui cachés pròpies (coherència).

El problema: coherència de caché

En arquitectures de memòria compartida (tant UMA com NUMA), tots els cores veuen el mateix espai d’adreces i es comuniquen simplement llegint i escrivint dades compartides amb instruccions load/store.

Per qüestions de rendiment, cada core té la seva pròpia caché. Això vol dir que una mateixa dada (o, més exactament, una mateixa línia de caché) pot estar copiada simultàniament a diverses cachés.

El problema apareix quan dues (o més) cachés tenen una còpia de la mateixa línia i un core hi escriu: les altres còpies poden quedar obsoletes (amb un valor antic). Per evitar que un core llegeixi dades «velles» mentre un altre ja ha escrit el valor nou, el sistema ha de garantir coherència: un conjunt de regles perquè totes les còpies mantinguin una visió consistent del valor.

Abans que B pugui llegir una còpia obsoleta (pas 4), hem d’idear un mecanisme perquè quan A modifiqui la línia invalidi o actualitzi la còpia de B. D’aquesta manera podem garantir que tots els cores sempre veuen el valor més recent. Necessitem un protocol de coherència!

True sharing vs false sharing

La coherència no es gestiona a nivell de variable individual, sinó a nivell de línia de caché (cache line). És a dir, el hardware tracta tota la línia com a unitat: si s’ha de fer invalidació o transferència, afecta tota la línia, no només el camp o element que ha canviat.

Si el hardware hagués de rastrejar l’estat de cada byte de memòria, el nombre de bits de control seria enorme: caldria mantenir informació d’estat i de compartició per cadascuna de les milions de posicions que poden estar a les cachés.

Treballar amb una granularitat de línia de caché simplifica enormement el hardware, però té una conseqüència directa: pot generar tràfic de coherència innecessari quan threads diferents modifiquen variables que, tot i ser independents, comparteixen línia.

Això dona lloc a dos tipus de tràfic de coherència amb causes molt diferents.

True sharing (compartició real). Parlem de true sharing quan diversos threads accedeixen a la mateixa adreça (la mateixa variable o element) i, per tant, realment necessiten compartir la mateixa dada. En aquest cas, és normal i inevitable que hi hagi comunicació de coherència entre processadors, perquè tots han d’estar «al dia» del valor correcte.

// Thread A i Thread B escriuen AMBDOS sobre result -> true sharing
#pragma omp atomic
result += parcial; // coherencia inevitable (mateixa variable)

Tot i que és inevitable, el tràfic de coherència es pot minimitzar mitjançant una reducció: cada thread acumula en una variable local i fa un sol atomic al final, en lloc d’un per iteració.

False sharing (compartició falsa). El false sharing passa quan diferents threads treballen amb variables diferents, però aquestes variables estan ubicades tan a prop a memòria que acaben caient dins la mateixa línia de caché. Com que la coherència es manté per línia i no per variable, una escriptura sobre un camp pot provocar invalidacions o transferències sobre tota la línia, afectant l’altre thread encara que no hi hagi cap conflicte real de dades.

int v[100]; // elements contigus en memoria
Thread A: v[0]++; // (escriu v[0])
Thread B: v[1]++; // (escriu v[1])
// Tot i ser VARIABLES DIFERENTS, escriuen a la MATEIXA LINIA!

Si v[0] i v[1] cauen dins la mateixa línia de caché (p. ex. línia de 16 bytes, int de 4 bytes):

És a dir: no s’està compartint «la mateixa variable», però el hardware ha d’actuar com si hi hagués compartició perquè la línia és comuna, i això introdueix overheads i pèrdua de rendiment.

Més endavant (secció 5.3) veurem com evitar-ho amb padding (afegir espai entre camps) i amb alineació/reorganització de dades perquè les variables modificades per threads diferents quedin en línies de caché separades.