Descomposició iterativa de bucles

En paral·lelitzar un bucle, repartim les iteracions entre diversos threads perquè s’executin de manera concurrent. L’objectiu és distribuir la càrrega de treball tot minimitzant la sincronització i els overheads.

Amb tasques implícites

Quan utilitzem #pragma omp parallel, OpenMP crea una tasca implícita per cada thread del team. Tots executen el mateix codi, i cada thread calcula quin rang d’iteracions li correspon a partir del seu identificador i del nombre total de threads.

Versió bàsica: una operació atòmica per iteració. La forma més directa de protegir una variable compartida és aplicar atomic a cada actualització. Això evita data races, però introdueix un cost de sincronització per iteració.

int sum = 0;
#pragma omp parallel shared(sum)
{
    int id    = omp_get_thread_num();
    int nt    = omp_get_num_threads();
    int BS    = N / nt;
    int start = id * BS;
    int end   = start + BS; // o (id + 1) * BS;

    for (int i = start; i < end; i++) {
        #pragma omp atomic // o critical en cas de no poder fer atomic
        sum += v[i];       // una operacio atomica per CADA iteracio
    }
}

Versió eficient: reducció manual. Podem reduir dràsticament el nombre d’operacions atòmiques acumulant el resultat primer en una variable local i combinant el resultat parcial al final. Així, el bucle és independent entre threads i només es sincronitza un cop per thread:

int sum = 0;
#pragma omp parallel shared(sum)
{
    ...

    int local_sum = 0;
    for (int i = start; i < end; i++)
        local_sum += v[i];

    #pragma omp atomic // o critical en cas de no poder fer atomic
    sum += local_sum;  // reduccio manual: una operacio atomica per thread
}

Això passa de $N$ operacions atòmiques a $P$ (una per thread).

Amb tasques explícites

En el model de tasques explícites, un thread (el master) crea tasques que s’insereixen en una pool de tasques. La resta de threads del team van agafant tasques de la pool i les van executant a mesura que queden lliures. Un cop el thread creador acaba de generar totes les tasques, també passa a executar-ne de la pool.

Creació manual (#pragma omp task). En aquesta versió, un thread (dins d’un single) crea explícitament una tasca per cada bloc d’iteracions. Cada tasca acumula el seu resultat parcial en una variable local i el combina amb un atomic, de manera anàloga a la reducció manual vista anteriorment:

int sum = 0;
#pragma omp parallel
#pragma omp single
{
    int nt = omp_get_num_threads();
    int BS = N / nt;
    for (int t = 0; t < nt; t++) {
        int start = t * BS;
        int end   = start + BS; // o (t + 1) * BS;
        #pragma omp task firstprivate(start, end) shared(sum)
        {
            int local_sum = 0;
            for (int i = start; i < end; i++)
                local_sum += v[i];
            #pragma omp atomic
            sum += local_sum;
        }
    }
} // barrera implicita del single, espera que finalitzin totes les tasques

Versió amb reducció automàtica (taskloop). Una altra forma més neta és delegar tant el repartiment d’iteracions com la gestió de la reducció a l’entorn d’execució d’OpenMP. Quan el bucle és comptable, podem usar la instrucció taskloop:

int sum = 0;
#pragma omp parallel
#pragma omp single
{
    int nt = omp_get_num_threads();
    #pragma omp taskloop reduction(+: sum) num_tasks(nt)
    for (int i = 0; i < N; i++) {
        sum += v[i];
    } // taskgroup implicit: espera totes les tasques del taskloop
}

• num_tasks(nt) indica quantes tasques es crearan. També podríem usar grainsize(m) per indicar la mida de cada tasca, i que se’n creïn tantes com calgui.
• reduction(+:sum) manté còpies privades de la variable i les combina al final, sense que el programador hagi de gestionar cap operació atòmica.

Aquesta és la forma recomanada per a bucles regulars amb operacions associatives simples, perquè és més llegible. Ara bé, taskloop només es pot aplicar a bucles comptables amb operacions de reducció estàndard (+, *, max, min…). Quan el bucle no és comptable o la combinació de resultats requereix una lògica més complexa, caldrà recórrer a la reducció manual amb atomic.