Encontro 6 - Encontrando o valor de Pi

Roteiro do Encontro

• Implementação do Algoritmo de geração de valor aproximado de pi;
• Paralelização do algoritmo de pi;
• Execução e Coleta de Dados;

Implementação do Algoritmo

O algoritmo de cálculo de pi se baseia no seguinte enunciado:

   Uma forma de se calcular o valor aproximado de π é através do seguinte método:

• Sub-escreva um círculo dentro de um quadrado;
• Gere pontos randomicamente dentro do quadrado;
• Determine o número de pontos dentro do quadrado que também estão no círculo;
• Seja r o número de pontos no círculo dividido pelo número de pontos no quadrado;
• π ~ 4.r
• Note que quanto mais pontos forem gerados, melhor será a aproximação.

npoints = 10000
circle_count = 0
do j = 1,npoints
   generate 2 random numbers between 0 and 1
xcoordinate = random1;
   ycoordinate = random2
if (xcoordinate, ycoordinate) inside circle then
circle_count = circle_count + 1
end do
PI = 4.0*circle_count/npoints

Implementação Paralela, Execução e Coleta dos Dados

 A primeira versão paralela desenvolvida foi a seguinte:

---------------------------------------------------------------------------------------------------------------------------------------
npoints = 10000
circle_count = 0
#pragma omp parallel for private(x, y, npoints) reduction(+:circle_count)
   do j = 1,npoints
       generate 2 random numbers between 0 and 1
       x = random1;
       y = random2
       if (x, y) inside circle then
             circle_count = circle_count + 1
   end do
PI = 4.0*circle_count/npoints
---------------------------------------------------------------------------------------------------------------------------------------
As aplicações foram executadas sobre o ambiente de testecontendo o SO Ubuntu (kernel 3.2.0-23) rodando sob um computador com processador Intel Core i7 2630QM, 2.0~2.9 GHz.e 8Gb memória DDR3.  Para os testes foi utilizado número de pontos/iterações igual a 1000000 na aplicação acima e 1000000000 para o teste abaixo.
Analisando a tabela de eficiência e speedup do algoritmo acima, notamos que ao invés de obter aumento de desempenho, perdemos em desempenho. Porque?

Num Threads	Tempo	Eficiência	SpeedUp
1	0,556	-	-
2	4,596	0,024	0,1209747607
3	5,72	0,029	0,0972027972
4	6,443	0,03	0,0862952041
5	6,678	0,041	0,0832584606
6	7,623	0,0043	0,0729371638
7	7,717	0,005	0,0720487236
8	7,775	0,0057	0,071511254

A resposta está no manual da função de geração de números aleatórios rand();
Baseado nisso, desenvolvemos uma nova versão paralela, que pode ser visualizada no algoritmo abaixo:
---------------------------------------------------------------------------------------------------------------------------------------
 #pragma omp parallel for private(i) reduction(+:pi)
        for(i=0; i< NUM_PONTOS; i++){
                pi += 4.0/(4.0*i+1.0);
                pi -= 4.0/(4.0*i+3.0);
        }
---------------------------------------------------------------------------------------------------------------------------------------
A tabela abaixo nos mostra os resultados obtidos para a execução da aplicação acima em nosso ambiente de teste.

Num Threads	Tempo	Eficiência	SpeedUp
1	15,825	-	-
2	8,238	0,9604879825	1,920975965
3	5,727	0,9210756068	2,7632268203
4	4,35	0,9094827586	3,6379310345
5	4,837	0,654331197	3,2716559851
6	4,504	0,5855905861	3,5135435169
7	4,594	0,4921014988	3,4447104919
8	4,436	0,4459253832	3,5674030658