Descomposició de dades · 5.5

Padding en matrius

Si el nombre de columnes no és múltiple de la línia de caché, el final d'una fila i l'inici de la següent comparteixen línia. Amb columnes de padding, cada fila comença alineada.

Conceptes clau

False sharing entre files adjacents
Columnes de padding (COLS + PAD)
Padding combinat amb l'estratègia de descomposició

Quan el nombre de columnes no és múltiple de la línia de caché, el final d’una fila i l’inici de la següent comparteixen línia de caché en memòria (row-major), provocant false sharing entre threads que treballen sobre files adjacents. La solució és afegir columnes extra de padding perquè cada fila ocupi un nombre enter de línies de caché:

#define CL      <cache_line_size_bytes>
#define ELEM_CL (CL / sizeof(type)) // elements per linia de cache
#define PAD     ((COLS % ELEM_CL == 0) ? 0 : (ELEM_CL - COLS % ELEM_CL))

type M[ROWS][COLS + PAD]; // cada fila = multiple de CL bytes
// Acces: nomes columnes [0..COLS-1], ignorar el padding

Matriu de 6 columnes amb CL = 4. Sense padding, el final d’una fila i l’inici de la següent comparteixen línia (P0 i P1 comparteixen CL1!). Amb 2 columnes de padding, cada fila comença alineada amb una nova línia de caché. (figura al dossier, p. 28)

El padding en matrius es combina amb qualsevol estratègia de descomposició. Per exemple, amb block-cyclic per columnes, BS pot servir alhora com a mida del bloc i com a unitat de padding, alineant cada bloc a una línia de caché sencera. El padding augmenta l’ús de memòria però pot millorar dràsticament el rendiment.