Estratègies geomètriques

Les estratègies geomètriques particionen l’espai d’iteracions (o dades) de forma regular. Totes s’implementen amb tasques implícites (omp parallel) usant la id i nt (omp_get_thread_num() i omp_get_num_threads()) per decidir quin tros processa cada thread.

▣Les tres estratègies sobre el mateix vector amb quatre processadors: block (un tros contigu per processador), cyclic (P0 P1 P2 P3 P0 P1…) i block-cyclic amb BS = 2. (figura al dossier, p. 21)

Block

Dividim el rang d’iteracions en blocs contigus de mida similar (idealment un bloc per processador). Cada tasca executa totes les iteracions del seu bloc.

#pragma omp parallel
{
    int id = omp_get_thread_num();
    int nt = omp_get_num_threads();
    int BS = N / nt;
    int start = id * BS;
    int end = start + BS;
    if (id == nt - 1) end = N; // ultim thread agafa el residu

    for (int i = start; i < end; i++) {
        ...
    }
}

Quan $N$ no és divisible per nt, la divisió entera N/nt deixa un residu de N % nt iteracions. En el codi anterior, la condició if (id == nt-1) end = N fa que l’últim thread s’emporti tot el sobrant, provocant un desbalanceig que pot arribar a nt-1 iteracions extra:

▣$N = 14$, $nt = 5$ ⇒ $BS = \lfloor 14/5 \rfloor = 2$, $res = 14 \bmod 5 = 4$: P0…P3 fan 2 iteracions i P4 en fa 6. L’últim thread acumula tot el residu: BS (2) + N mod nt (4) extres; desbalanceig = 4. (figura al dossier, p. 21)

Block amb el residu repartit

Per evitar-ho, podem repartir el residu entre els primers res threads, de manera que cadascun d’ells fa BS+1 iteracions en lloc de BS. Així el desbalanceig màxim és sempre d’1 sola iteració:

int id  = omp_get_thread_num();
int nt  = omp_get_num_threads();
int BS  = N / nt;
int res = N % nt;

// Els primers 'res' threads fan BS+1 iteracions, la resta fan BS
int start = BS * id + ((id < res) ? id : res);
int end   = start + BS + ((id < res) ? 1 : 0);

for (int i = start; i < end; i++) {
    ...
}

▣Els res (4) primers threads fan BS + 1 (3) iteracions i la resta fa BS (2), aconseguint desbalanceig = 1. (figura al dossier, p. 22)

Propietats de l’estratègia Block:

• Localitat: cada thread recorre un rang contigu ⇒ maximitza la localitat espacial de caché.
• Coherència / false sharing: baix en general, perquè els threads treballen sobre línies de caché diferents. Pot aparèixer només a les fronteres entre blocs si diversos threads escriuen a elements que cauen dins la mateixa línia de caché.
• Load balance:
  • En elements: amb el residu repartit, el desbalanceig és com a màxim d’1 iteració.
  • En temps de còmput: si el cost per iteració no és uniforme, els processadors amb les iteracions més costoses acumulen molta més feina que els altres, provocant que alguns treballin molt més que d’altres.

▣Temps de còmput creixent amb l’element $i$ repartit en blocs: la feina total és P0: 6, P1: 15, P2: 24 i P3: 33. (figura al dossier, p. 22)

En casos com un espai triangular o el Mandelbrot, l’estratègia block pot deixar processadors inactius mentre d’altres acumulen la major part del treball.

Cyclic

Dividim el rang d’iteracions assignant-les de manera saltejada: cada thread executa les iteracions id, id+nt, id+2*nt, … fins a sobrepassar $N$.

#pragma omp parallel
{
    int id = omp_get_thread_num();
    int nt = omp_get_num_threads();

    for (int i = id; i < N; i += nt) {
        ...
    }
}

▣Amb nt = 4, cada thread executa i = id, id+4, id+2·4… sobre 14 elements (0–13): cada thread salta de nt en nt elements, fins a sobrepassar N. (figura al dossier, p. 23)

Propietats de l’estratègia Cyclic:

• Localitat: molt dolenta. Cada thread salta de nt en nt elements, destruint la localitat espacial i gairebé mai reutilitzant una línia de caché ja carregada.
• Coherència / false sharing: molt alt. Els elements consecutius pertanyen a threads diferents, de manera que dins de cada línia de caché hi escriuen múltiples processadors, provocant invalidacions constants.
• Load balance:
  • En elements: diferència ≤ 1 iteració sense cap correcció de residu.
  • En temps de còmput: les iteracions es reparteixen intercalades, barrejant les cares amb les barates i equilibrant la càrrega total.

▣El mateix cost creixent repartit cíclicament: la feina total és P0: 15, P1: 18, P2: 21 i P3: 24. Cada thread rep una barreja d’iteracions barates i cares, equilibrant la càrrega total tot i que el cost per iteració creix. (figura al dossier, p. 23)

Block-Cyclic

L’espai d’iteracions es parteix en blocs contigus de mida fixa BS i aquests blocs es reparteixen de manera cíclica entre els threads. És el punt mig entre block i cyclic, ja que:

• Si $BS = 1$ ⇒ cyclic pur (màxim balanceig, mínima localitat).
• Si $BS = N/nt$ ⇒ block pur (màxima localitat, mínim balanceig temporal).

#pragma omp parallel
{
    int id = omp_get_thread_num();
    int nt = omp_get_num_threads();
    const int BS = 3; // mida del bloc fixa (iteracions)

    // ii = inici del bloc actual
    // min(ii + BS, N) = fi del bloc (evita sobrepassar N)
    for (int ii = id * BS; ii < N; ii += nt * BS) {
        for (int i = ii; i < min(ii + BS, N); i++) {
            ...
        }
    }
}

▣Amb nt = 3 i BS = 3, cada thread comença el bloc a ii = id·BS, id·BS + nt·BS, id·BS + 2·nt·BS… sobre N = 14: cada thread processa un bloc contigu de BS elements i salta nt × BS posicions. L’últim bloc és incomplet, ja que min(ii+BS, N) evita sobrepassar N. (figura al dossier, p. 24)

Propietats de l’estratègia Block-Cyclic:

• Localitat: millor que cyclic. Dins de cada bloc, el thread recorre BS elements contigus, aprofitant la localitat espacial. Com més gran sigui BS, millor localitat (s’apropa a block).
• Coherència / false sharing: el risc depèn de BS. Si BS està alineat amb la línia de caché (per exemple, BS = múltiple d’elements per línia), cada bloc ocupa línies senceres i no hi ha false sharing a les fronteres. Un BS petit o no alineat pot provocar que el final d’un bloc i l’inici del següent (d’un altre thread) comparteixin línia.
• Load balance:
  • En elements: el desbalanceig pot arribar a BS iteracions (un processador executa un bloc més que els altres).
  • En temps de còmput: millora respecte block perquè els blocs es reparteixen cíclicament, barrejant zones de cost diferent entre els threads. Com més petit sigui BS, millor balanceig temporal (s’apropa a cyclic).

Block-Cyclic alineat a línia de caché

Un dels problemes del block-cyclic és que si BS no coincideix amb la mida de la línia de caché, la frontera entre blocs de threads diferents pot caure dins d’una mateixa línia, provocant false sharing.

▣BS = 3, CL = 2: les línies encerclades contenen elements de 2 processadors ⇒ false sharing. (figura al dossier, p. 25)

La solució és escollir BS com a múltiple del nombre d’elements que caben en una línia de caché:

$$BS = k \times \frac{\texttt{cache_line_size}}{\texttt{sizeof(element)}} \qquad (k = 1, 2, \dots)$$

▣BS = 4 (múltiple de CL = 2): cada línia de caché pertany a un sol processador. (figura al dossier, p. 25)

Amb BS alineat, cada bloc ocupa línies de caché senceres i cap línia és compartida entre threads, eliminant el false sharing.

Comparativa de les estratègies

Estratègia	Localitat	False sharing	Imbalance elements	Imbalance temps
Block	Bona	Baix (fronteres)	≤ nt−1	Alt
Block repartit	Bona	Baix (fronteres)	≤ 1	Alt
Cyclic	Dolenta	Molt alt	≤ 1	Baix
Block-Cyclic	Bona	Depèn de BS	≤ BS	Mig
Block-Cyclic alineat	Excel·lent	No n’hi ha!	≤ BS	Mig

• Si el cost per iteració és uniforme i volem màxima localitat: Block (repartit) és la millor opció, ja que combina rang contigu amb desbalanceig mínim.
• Si el cost per iteració és molt irregular i el que més importa és equilibrar la càrrega: Cyclic reparteix millor el temps, però a costa de destruir la localitat i provocar false sharing.
• Si volem un compromís entre localitat i balanceig: Block-Cyclic alineat és l’opció més versàtil. Ajustant BS controlem el balanç entre més localitat o més balanceig.