Objectius de la descomposició de dades

Com hem vist al tema anterior, en arquitectures amb memòria jeràrquica i NUMA cada bloc de dades pot estar a la memòria local d’un node, a la caché d’un core concret, o fins i tot en diverses cachés alhora. Quan modifiquem aquestes dades podem provocar invalidacions que donen lloc a actualitzacions de línies de caché (coherència de dades) i, per tant, a missatges entre nodes NUMA causant overheads de comunicació.

Per això, quan definim les tasques no n’hi ha prou amb tenir en compte només la càrrega de treball: cal repartir de forma estratègica les dades i qui les computa per tal d’aprofitar al màxim:

• Aprofitar al màxim la localitat de la memòria caché.
• Minimitzar el nombre de missatges de coherència i de comunicacions.
• Mantenir un load balance raonable.

Objectius de la descomposició de dades

1. Generar tasques amb càrrega similar (load balance): cada thread hauria de tenir aproximadament el mateix nombre d’iteracions o elements. Però no n’hi ha prou amb això: pot haver-hi iteracions que triguin molt més que les altres, i cal repartir bé sobretot els fragments més costosos.
2. Maximitzar la localitat de dades: volem que cada processador treballi sobre el seu tros de memòria. D’aquesta manera les dades tendeixen a estar ja carregades a la memòria caché (i, en NUMA, a memòria local) i reduïm fallades de caché i accessos remots.
3. Minimitzar dades compartides entre tasques: compartir dades entre threads implica invalidacions de caché, manteniment de coherència dins del NUMA node (bus snoopy) o entre NUMA nodes (directori MSU). Com menys dades es comparteixin de forma activa, menys tràfic de coherència generem.
4. Minimitzar volum i freqüència de transmissió de dades: com menys transmissions fem, millor. Si la transmissió és inevitable, és preferible fer-ho una sola vegada amb blocs grans i contigus que no pas moltes transferències petites i disperses (ens estalviem el temps d’start-up).
5. Solapar les transmissions de dades: si n’hi ha d’haver, intentarem fer-les de manera solapada per mitigar l’overhead de comunicació.
6. Minimitzar zones molt concurrents (hot spots): variables molt utilitzades per varis threads alhora (per exemple, sumes globals) provoquen llarga espera per sincronització i molta activitat de coherència. Sempre que sigui possible, aplicarem estratègies de reducció (cada thread acumula localment i al final es combinen els resultats).