OpenMP Parallel Programming: Optimization Techniques

Conceptos Básicos de OpenMP

• Flush: Ocurre cuando hay algo modificado y se escribe en la misma línea.
• Bus Upgrade: Sucede cuando tienes un dato exclusivo y lo modificas.

Versión Secuencial con Pragma Parallel For y Reduction

int minimo(int *V, int n) {
    int i, k, i_end, i_start;
    int min = V[0];
    #pragma omp parallel for private(i_end, i_start) reduction(min:min)
    for(k = 0; k < 4; k++) {
        i_end = (k + 1) * (n / 4);
        if(k == 0) i_start = 1;
        else i_start = k * (n / 4);
        for(i = i_start; i < i_end; i++) {
            if(V[i] < min) min = V[i];
        }
    }
    return min;
}

Versión Usando Pragma OMP Task

int minimo(int *V, int N) {
    int i, k, i_end, i_start;
    int min;
    int min4[4][16]; /* Para evitar false sharing */
    for(k = 0; k < 4; k++) {
        #pragma omp task private(i_start, i_end) firstprivate(k) shared(min4)
        {
            min4[k][0] = V[k * (N / 4)];
            i_end = (k + 1) * (N / 4);
            if (k == 0) i_start = 1;
            else i_start = k * (N / 4);
            for(int i = i_start; i < i_end; i++) {
                if(V[i] < min4[k][0]) min4[k][0] = V[i];
            }
        }
    }
    #pragma omp taskwait
    min = min4[0][0];
    for(k = 1; k < 4; k++) {
        if(min4[k][0] < min) min = min4[k][0];
    }
    return min;
}

Versión Recursiva con 4 Funciones

int recur_minimo(int* V, int n) {
    int i, k, min, min1, min2, min3, min4;
    if(n <= Nlim) {
        min = V[0];
        for(i = 1; i < n; i++) {
            if(V[i] < min) min = V[i];
        }
    } else {
        min1 = recur_minimo(V, n / 4);
        min2 = recur_minimo(V + n / 4, n / 4);
        min3 = recur_minimo(V + n / 2, n / 4);
        min4 = recur_minimo(V + 3 * (n / 4), n / 4);
        min = min2;
        if(min1 < min) min = min1;
        if(min3 < min) min = min3;
        if(min4 < min) min = min4;
    }
    return min;
}

Versión Paralelizada (Leafs)

int recur_minimo(int *V, int n) {
    int i, k, min, min1, min2, min3, min4;
    if(n <= Nlim) {
        #pragma omp task shared(min)
        {
            min = V[0];
            for(i = 1; i < n; i++) {
                if(V[i] < min) min = V[i];
            }
        }
        return min;
    } else {
        min1 = recur_minimo(V, n / 4);
        min2 = recur_minimo(V + n / 4, n / 4);
        min3 = recur_minimo(V + n / 2, n / 4);
        min4 = recur_minimo(V + 3 * (n / 4), n / 4);
        #pragma omp taskwait
        min = min2;
        if(min1 < min) min = min1;
        if(min3 < min) min = min3;
        if(min4 < min) min = min4;
        return min;
    }
}

Análisis de Rendimiento

Esquema de cálculo:

T_inf = 596T_rec + 256 * 1024T_it

• 596 = 4 + 4² + 4³ + 4⁴ + 4⁵ (llamadas recursivas)
• 256 = 4⁴ (funciones iterativas con 1024 datos)