Logo Eitas Logo Eitas

Resolvendo Condições de Disputa em OpenMP

Luís Fabrício Wanderley Góes

você vai aprender

Como medir o tempo de aplicações e calcular o ganho (speedup).

Como permitir que várias threads utilizem uma mesma variável compartilhada.

Como usar o padrão REDUCE em OpenMP.

pré-requisitos

Introdução a Programação Paralela com OpenMP

calculando o valor de PI

O cálculo de Pi por meio de integração numérica é uma aplicação que consome muito tempo de execução. Este tempo é proporcional ao aumento da precisão (número de casas decimais). Vamos então medir este tempo na prática.

#include <stdio.h>

long long num_passos = 1000000000;
double passo;

int main(){
   int i;
   double x, pi, soma=0.0;
   passo = 1.0/(double)num_passos;
	
   for(i=0; i < num_passos; i++){
      x = (i + 0.5)*passo;
      soma = soma + 4.0/(1.0 + x*x);
   }

   pi = soma*passo;
	
   printf("O valor de PI é: %f\n", pi);
   return 0;
}

Primeiro copie o código acima para um arquivo chamado pi.c. 
Vamos então compilar o programa com o seguinte comando:

$ gcc pi.c -o pi


Para medir o tempo de execução da aplicação, utilize o seguinte comando:

$ time ./pi


Uma saída esperada para esse programa é a seguinte:

O valor de PI é: 3.141593

real   0m20.805s
user   0m20.783s
sys    0m0.024s

Os valores real, user e sys são respectivamente o tempo de execução total que a aplicação gastou (real),
o tempo de execução em modo usuário (user) e em modo kernel (sys).

Note que o tempo em modo kernel é bem pequeno, pois neste programa não são realizadas muitas chamadas ao sistema operacional.

paralelizando o laço de repetição

Geralmente, a primeira ideia que temos é paralelizar a laço de repetição usando a diretiva #pragma omp parallel for {...}.
Vamos fazer isso e ver o que acontecerá.

#include <stdio.h>

long long num_passos = 1000000000;
double passo;

int main(){
   int i;
   double x, pi, soma=0.0;
   passo = 1.0/(double)num_passos;
	
   #pragma omp parallel for	
   for(i=0; i < num_passos; i++){
      x = (i + 0.5)*passo;
      soma = soma + 4.0/(1.0 + x*x);
   }

   pi = soma*passo;
	
   printf("O valor de PI é: %f\n", pi);
   return 0;
}

Vamos compilar e executar o programa com os seguintes comandos:

$ gcc pi.c -o pi -fopenmp


$ time ./pi


Uma saída possível seria a seguinte em um processador com dois núcleos:

O valor de PI é: 2.003199

real  0m17.788s
user  0m35.100s
sys   0m0.160s


Neste resultado existem três pontos interessantes. Tente identificá-los.

Agora pense nas possíveis causas.


Regra 4 do Paralelismo: Resultados incorretos geralmente indicam a existência 

de conflitos por variáveis compartilhadas não resolvidos.


identificando os conflitos

Para localizar conflitos ou condições de disputa por variáveis compartilhadas, basta localizar qualquer variável dentro da região paralela que esteja sendo modificada. Localize-as no código abaixo.

 #pragma omp parallel for	
 for(i=0; i < num_passos; i++){
    x = (i + 0.5)*passo;
    soma = soma + 4.0/(1.0 + x*x);
 }

No código acima, podemos identificar 5 variáveis (i, num_passos, x, passo e soma).
As variáveis num_passos e passo são apenas de leitura, ou seja nunca são modificadas, logo não geram nenhum conflito.

A variável i apesar de ser modificada (i=0, i++), ela é contador do laço de repetição, então ela é privatizada automaticamente pelo
#pragma omp parallel for {...}., ou seja, cada thread tem uma cópia local de i.

Restam então as variáveis x e soma que são modificadas. Vamos avaliar a variável x.
Substitua as variáveis x pela expressão atribuída a ela e veja se o seu programa continua correto como no exemplo abaixo.

 #pragma omp parallel for	
 for(i=0; i < num_passos; i++){
   soma = soma + 4.0/(1.0 + ((i + 0.5)*passo)*((i + 0.5)*passo));
 }

 #pragma omp parallel for private(x)
 for(i=0; i < num_passos; i++){
   x = (i + 0.5)*passo;
   soma = soma + 4.0/(1.0 + x*x);
 }

Vamos modificar o código conforme o código acima e executar os comandos abaixo.

$ gcc pi.c -o pi -fopenmp


$ time ./pi


Uma saída possível seria a seguinte:

O valor de PI é: 2.108069

real  0m17.977s
user  0m31.341s
sys   0m0.136s

O resultado mudou pouco, pois apesar de termos resolvido o conflito pela variável x, ao criar uma cópia privada de x para cada uma das threads, ainda não resolvemos o conflito pela variável soma.

Regra 5 do Paralelismo: Variáveis que são utilizadas em uma mesma iteração não são dependências de dados reais, 


portanto devem ser privatizadas.


criando seções críticas

Então porque também não privatizamos a variável soma? Por que não? Pense um pouco sobre isso.

Pense ... ela é o resultado de um somatório. Imagine que estivéssemos somando 1 + 2 + 3 + 4. Se a soma fosse privatizada e cada thread ficasse responsável por somar metade dos elementos, a thread 0 somaria 1 + 2 = 3 e a thread 1 somaria 3 + 4 = 7.

Qual seria a resposta certa do somatório?

Então como resolver este problema?

No OpenMP existe um comando chamado #pragma omp critical. Ele cria uma seção crítica ao redor de um comando. Uma seção crítica impede que duas threads executem um mesmo código ao mesmo tempo. Ou seja, se colocarmos uma seção crítica ao redor da linha que modifica a variável soma, a soma continua compartilhada, mas não existe a possibilidade de duas ou mais threads modificarem o seu valor ao mesmo tempo. Isso elimina a condição de disputa.

 #pragma omp parallel for private(x) 
 for(i=0; i < num_passos; i++){
   x = (i + 0.5)*passo;
   #pragma omp critical
   soma = soma + 4.0/(1.0 + x*x);
 }

Vamos compilar e executar o programa acima com o chamado #pragma omp critical.

Uma saída possível seria a seguinte:

O valor de PI é: 3.141593

real  0m51.101s
user  1m39.295s
sys   0m0.527s

Você vai notar dois resultados interessantes. Tente pensar quais são eles.

Regra 6 do Paralelismo: Variáveis que são realmente compartilhadas devem ser protegidas por seções críticas.


realizando uma redução

Por que o programa ficou tão lento? Pense um pouco antes de conferir a resposta.

Mas existe uma solução melhor pra este problema?

No OpenMP, o padrão REDUCE é implementado por meio do chamado reduction(op:var), onde var é a variável onde a operação op é aplicada. Uma redução consiste em somar os resultados parciais de cada thread até gerar um único valor. Imagine a situação descrita anteriormente onde a soma foi privatizada. O único problema foi não somar o 3 + 7, ou seja, somar os resultados parciais de cada thread.

É exatamnete isso que a redução faz, ela cria uma variável privada para cada thread, mas no final ela agrupa todas elas em apenas uma variável, como no exemplo abaixo.

 #pragma omp parallel for private(x) reduction(+:soma)
 for(i=0; i < num_passos; i++){
   x = (i + 0.5)*passo;
   soma = soma + 4.0/(1.0 + x*x);
 }

Vamos compilar e executar o programa.

Uma saída possível seria a seguinte:

O valor de PI é: 3.141593

real  0m10.620s
user  0m20.732s
sys   0m0.056s

Você pode notar que neste resultado, o valor de PI está correto e além disso o tempo caiu pela metade.
Ou seja, a aplicação teve um speedup de aproximadamente 2.

O speedup é a métrica utilizada para avaliar o ganho de desempenho, dividindo-se o tempo da versão sequencial pelo tempo da versão paralela, no nosso exemplo: 20.8/10.6 = 1.96, ou aproximadamente 2 de speedup, próximo ao speedup linear.

Com a redução, a seção crítica é eliminada e as threads não perdem mais tempo dormindo. Apenas ao final da região paralela, existe a sincronização das threads para realizar a redução. 

Pílula Entenda a diferença entre shared, private, critical e reduction.

Regra 7 do Paralelismo: Variáveis compartilhadas que acumulam resultados 

podem ser mapeadas no padrão REDUCE, evitando a inserção de seções críticas.


links úteis

Tutorial OpenMP​​​​​​​

Voltar