🥇 OpenMP: melhore as técnicas de redução

Introdução

A reductionpalavra-chave é uma das muitas cláusulas na programação do paradigma OpenMP, muitas vezes é fonte de degradações em vez de acelerações . Este tutorial descreve como evitar o erro comum e como e quando usá-lo.

Qual é o problema ?

Cada um reductioné colocado pelo compilador em uma atomicseção, o que causa uma pequena sobrecarga. O problema começa quando essa pequena sobrecarga começa a crescer dramaticamente.

Exemplo de uso padrão

O uso padrão se parece com este código:

void standard_reduction() {
    <type> my_global_sum = 0;
    /* The parallel part of your Algorithm: k-threads works here */
 #pragma omp parallel for reduction(+: my_global_sum)
     for(int i = 0; i < N; ++i) {
         <type> formula = f(i);
         my_global_sum += formula;
    }
    /* The serial part of your Algorithm: 1-thread works here */
     my_final_result = g(my_global_sum);
}

Isso standard_reduction()pode ser a fonte da degradação geral de seu aplicativo. 
Se Nfor ‘grande’, a cláusula atômica interna produzirá resultados inesperados: cada cláusula atômica tem um custo que não compensa se o mecanismo usado para sincronizar todas as etapas do algoritmo tiver uma ordem de alta complexidade .

Nota sobre ‘Grande’ : O conceito de ‘grande’ é absolutamente relativo à arquitetura e algoritmos envolvidos, mas você pode facilmente ter a ideia de que ‘grande’ é uma ordem de alta magnitude. 
Nota sobre ‘Pequeno’ : Tudo é relativo , de modo que a atomicoperação tem uma ‘pequena’ sobrecarga em relação ao mecanismo de travar / destravar que pode ser usado para substituir a atomicoperação.

Melhoria da Proposta

Usar a variável local em cada thread resolve toda a sobrecarga interna do algoritmo.
A versão aprimorada de é:standard_reduction()

void improve_reduction() {
    <type> my_global_sum = 0;
    /* The parallel part of your Algorithm: k-threads works here */
#pragma omp parallel
{
    <type> my_local_sum = 0;
#pragma omp for nowait
    for(int i = 0; i < N; ++i) {
        <type> formula = f(i);
        my_local_sum += formula;
    }          
#pragma omp atomic
    my_global_sum += my_local_sum;
} 
    /* The serial part of your Algorithm: 1-thread works here */
    my_final_result = g(my_global_sum);
}

Fator de melhoria

Vamos chamar de H a complexidade de sobrecarga média para uma única operação atômica. 
No, a complexidade de sobrecarga total é: O (H * N * número_threads) . Em vez disso, na fórmula torna-se: O (H * número_threads) . Isso é desprezível porque, por exemplo, você não pode definir number_threads ~ O (10 ^ 6). Portanto, o fator de melhoria é exatamente O (N) e isso é relevante.standard_reduction()
improve_reduction()

Um exemplo real

Suponha que você escreva uma biblioteca com suporte a OpenMP habilitado pela opção de configuração.
Portanto, seu código pode ter a seguinte aparência:

sum = 0;
#ifdef OPENMP_ENABLE
#pragma omp parallel for reduction(+:sum)
#endif
for(i = 0; i < N; ++i) {
   int formula = f(i);
   sum += formula;
}

É por isso que o OpenMP é legal, porque não é intrusivo! 
Em duas linhas , adicionamos a opção de suporte para o recurso OpenMP e em uma linha criamos o paralelismo. Suponha agora que você deseja melhorar a versão acima removendo a redução e introduzindo uma variável local, o código se parece com isto :#ifdef,#endif#pragma omp for reduction(+:sum)

sum = 0;
#ifdef OPENMP_ENABLE
#pragma omp parallel
{ 
    <type> my_local_sum = 0;
#pragma omp for nowait
#endif
    for(i = 0; i < N; ++i) {
        int formula = f(i);

#ifdef OPENMP_ENABLE
        my_local_sum += formula;
#else
        sum += formula;
#endif
}

#ifdef OPENMP_ENABLE
#pragma omp atomic
    sum += my_local_sum;
} 
#endif

O código acima não é legível, difícil de mudar, não é elegante …

Mudança de estratégia

Há uma maneira alternativa de remover totalmente a sobrecarga devido a cláusulas reductionou atomic. Aqui está o código:

void advanced_reduction() {
    <type> my_global_sum = 0;
    <type> *vectorization;
    int threads;

#pragma omp parallel
    #pragma omp master    
        threads = omp_get_num_threads();

    vectorization = (<type>*) _mm_malloc(threads*sizeof(<type>), 64);
    assert(vectorization != NULL);

    /* The parallel part of your Algorithm: k-threads works here */
#pragma omp parallel
{
    <type> my_local_sum = 0;
#pragma omp for nowait
    for(int i = 0; i < N; ++i) {
        <type> formula = f(i);
        my_local_sum += formula;
    }          

    *(vectorization + omp_get_thread_num()) = my_local_sum;
} 

    /* Serial part of your Algorithm: 1-thread works here */
    for (int i = 0; i < threads; ++i)
        my_global_sum += *(vectorization + i);

    my_final_result = g(my_global_sum);
}

Lembre-se: o código acima mostra uma forma alternativa de , mas nem sempre oferece um melhor desempenho, isso porque:improve_reduction()

a atomiccláusula tem uma pequena sobrecarga
a atomiccláusula está fora do loop interno
como mencionado antes, O (H * number_threads) é insignificante

Threads Overhead

Cada vez que um grupo de threads é criado por , etc … Haverá sempre um overhead devido à criação de threads pela biblioteca OpenMP. Por isso é importante conhecer a ordem de complexidade dos algoritmos, muitas vezes uma versão serial pode ser mais eficiente do que a implementação paralela do mesmo algoritmo devido à falta de overhead de threads.#pragma omp parallel#pragma omp parallel for

Conclusão

Use a reductioncláusula apenas quando precisar de legibilidade do código e seu problema tiver uma ordem de baixa magnitude, caso contrário, gaste alguns minutos e melhore seu algoritmo.