UNIVERSIDADE FEDERAL DE SANTA MARIA
CENTRO DE TÉCNOLOGIA
CURSO DE CIÊNCIA DA COMPUTAÇÃO
ANÁLISE SOBRE UMA
APLICAÇÃO DE
MANDELBROAT
Cícero Augusto de Lara Pahins, Cristiano Reis dos Santos.
Professora: Profª Andrea Schwertner Charão.
Disciplina: Programação Paralela.
1. Escolha da Aplicação
Para realização do trabalho foi escolhida a aplicação que utiliza o conjunto de Mandelbrot, a
aplicação c_Mandelbrot. A escolha foi baseada em duas premissas. A primeira foi que essa era um das
aplicações propostas que não haviam sido escolhidas. A segunda foi o fato dos integrantes acharem
interessante a geração de fractais.
2. Conjunto de MandelBroat
O
Conjunto
de
Mandelbrot é
um fractal definido
como
o
conjunto
de
pontos c no
plano complexo para o qual uma sequência é definida iterativamente:
0 = 0
= + A expansão da sequencia é realizada da seguinte maneira:
= + 0 = 0
= 0 + == + = 1 + == ( + ) + + = 2 + ....
Se reescrevermos a sequência em termos das partes real e imaginária (coordenadas x e y do
plano complexo), a cada iteração n, substituindo pelo ponto + i e c pelo ponto a + bi, temos:
= + + = 2 + O conjunto de Mandelbrot, em sua representação gráfica, pode ser dividido em um conjunto
infinito de figuras pretas, sendo a maior delas um cardioide localizado ao centro do plano complexo.
Existe uma quantidade muito grande de quase círculos que tangenciam a cardioide e variam de
tamanho com raio tendendo assintoticamente a zero.
Realizando um “zoom” no conjunto de Mandelbrot com mais resolução encontram-se sempre
réplicas e mais réplicas do conjunto. É uma característica dos objetos fractais. Pontos mais internos ao
conjunto de Mandelbrot correspondem a formas geométricas relativamente simples, enquanto os pontos
mais externos lembram poeira rodeada por manchas de cores.
3. Análise do Código
A aplicação escolhida está escrita em linguagem c. Ela recebe o número de pontos que se
deseja gerar para o plano complexo. Um for não paralelizado é responsável pela inicialização dos pontos
através de uma função randômica.
A seguir um for aninhado paralelizado é utilizado para gerar pontos do conjunto de Mandelbrot
que são utilizados para calcular o erro e a área.
Abaixo as diretivas OpenMP utilizadas no for aninhado:
#pragma omp parallel for default(none) reduction(+:outside) \
private(i, j, ztemp, z) shared(NPOINTS, points)
4. Testes de Desempenho
Após as modificações terem sido realizadas alguns testes foram feitos para verificar a
variação de desempenho apresentado pela aplicação. Os testes foram feitos no servidor sugerido
pela professora, o servidor linux03, com 8 núcleos, disponibilizado para alunos de informática da
Universidade Federal de Santa Maria.
O número de pontos utilizados foi definido como 32.768 e 65.536. O número de threads
variou no intervalo fechado de 1 a 8.
Para os dois números de pontos escolhidos o desempenho foi semelhante para a aplicação
em sua forma original e modificada. Com o aumento do número de threads utilizando 32.768 pontos
o desempenho com 8 threads foi o melhor, aproximadamente 600% superior ao desempenho com 1
thread. Com 65.536 o melhor desempenho para a aplicação foi com 7 threads, aproximadamente
450% superior ao desempenho com 1 thread.
Mandelbrot 32768
16.000
Tempo em Segundos
14.000
12.000
10.000
8.000
Original
6.000
Modificado
4.000
2.000
0.000
1
2
3
4
5
Número de Threads
6
7
8
Mandelbrot 65536
35.000
Tempo em Segundos
30.000
25.000
20.000
15.000
Original
10.000
Modificado
5.000
0.000
1
2
3
4
5
6
7
8
Número de Threads
SPEEDUP
O speedup refere-se ao quanto mais rápido é a aplicação paralelizada em relação ao algoritmo
sequencial.
= Onde:
P é o número de processadores.
T1 é o tempo de execução com o algoritmo sequencial.
Tp é o tempo de execução com o algoritmo paralelo com p processadores.
Mandelbrot 32768
8.000
7.000
speedup
6.000
5.000
4.000
Original
3.000
Modificado
2.000
1.000
0.000
1
2
3
4
5
Número de Threads
6
7
8
Mandelbrot 65536
7.000
6.000
speedup
5.000
4.000
Original
3.000
Modificado
2.000
1.000
0.000
1
2
3
4
5
6
7
8
Número de Threads
EFICIÊNCIA
A eficiência estima o quão bem estão sendo utilizados os processadores para resolver o
problema.
= Mandelbrot 32768
1.050
1.000
Eficiência
0.950
0.900
Original
Modificado
0.850
0.800
0.750
1
2
3
4
5
Número de Threads
6
7
8
Mandelbrot 65536
1.200
1.000
Eficieência
0.800
0.600
Original
Modificado
0.400
0.200
0.000
1
2
3
4
5
6
7
8
Número de Threads
5. Reflexão
A aplicação escolhida foi paralelização do algoritmo do Conjunto de Mandelbrot, um fractal
definido como o conjunto de pontos c no plano complexo para qual a sequência não tende ao infinito. A
solução proposta na distribuição do OmpSCR consiste nos seguintes passos:
I.
Geração de um vetor de pontos 're' e 'im' inicializados com valores randômicos
distribuídos pelo plano complexo (retângulo).
II.
Aplicação do Algoritmo de Monte Carlo, método estatístico utilizado em simulações
estocásticas como forma de obter aproximações numéricas de funções complexas.
III.
Cálculo da área e erro, sendo a área proporcional a duas vezes a área do retângulo
vezes o número de pontos dentro dele, e o erro sendo o inversamente proporcional a
raiz quadrada do número de testes de caso.
Para isto o código proposto é:
Nesta solução o algoritmo de Monte Carlo é paralelizado pelo for mais externo, dividindo
igualmente a carga entre as threads. Nos testes realizados a escabilidade se mostrou eficiente, de
maneira que o tempo total de execução diminui proporcionalmente ao aumento de número de threads.
O algoritmo paralelizado apresenta dependência de dados, de modo que para o cálculo i é
necessário o cálculo i-1:
Isto impossibilita a paralelização do for mais interno correspondete a etapa dois (Monte Carlo
sampling). Uma proposta de alteração no código original da aplicação é a paralelização do processo de
geração de pontos randômicos no plano complexo, entretando está modificação não trás ganhos
expressivos, já que são realizados cálculos simples para esta etapa. Isto se repete mesmo para vetores
com tamanhos muito grandes, como os utilizados nos testes presentes no relatório.
6. Código Modificado
7. Referência
http://en.wikipedia.org/wiki/Mandelbrot_set
http://pt.wikipedia.org/wiki/Conjunto_de_Mandelbrot
http://www.compunity.org/training/tutorials/3%20Overview_OpenMP.pdf
http://www.openmp.org/mp-documents/OpenMP3.0-SummarySpec.pdf