Aproximação do pelo Método de Monte Carlo

Disponível comercialmente há aproximadamente duas décadas, o paralelismo vem sendo utilizado com sucesso em diversos ramos da atividade humana. Vem prestando relevantes serviços à área de pesquisa e desenvolvimento, onde historicamente tem se destacado as soluções que oferece para o processamento numericamente intensivo.

Uma linha de pesquisa que vem se destacando nos últimos anos é a pesquisa em grid computing, tendo como motivação central o melhor aproveitamento do poder computacional de equipamentos ociosos. A maioria das estações de trabalho pessoais, tanto em áreas acadêmicas, como em áreas comerciais e industriais, passam a maior parte do tempo com seus processadores ociosos. O uso destes processadores, em momentos de ociosidade, e por processos de baixa prioridade, pode oferecer um poder computacional bastante elevado, sem onerar o usuário do computador.

Por outro lado, o uso eficiente deste tipo de arquitetura é um problema bastante complexo, e vem sendo estudado por diversos grupos de pesquisa, em diversos lugares do mundo.

Diversos esforços têm sido empreendidos para tentar organizar o contexto de grid computing, e facilitar a obtenção de soluções para os variados problemas apresentados por este tipo de arquitetura. [2] classifica as aplicações de Grid em cinco categorias: supercomputação distribuída, high-throughput computing, sob demanda, computação intensiva de dados, computação colaborativa.

Muitos grupos de pesquisa, especialmente de áreas aplicadas vêm obtendo bons resultados com aplicações distribuídas, resolvendo questões matemáticas [8,4,7], de engenharia [6], de saúde [3,1], e ainda outras aplicações científicas específicas, tais como o Projeto Seti@Home [9].

O Algoritmo para Cálculo

O número $\pi$ pode ser estimado através do método de Monte Carlo. Esta aplicação foi construída para determinar um valor estimado do número $\pi$ . Foi utilizado o método de Monte Carlo [5] para cálculo da área de $\frac{1}{4}$ de círculo. A partir deste valor estimado, pode-se estimar o valor do $\pi$ . O número de iterações do algoritmo determina a precisão do cálculo.

**Figura:** Área de $\frac{1}{4}$ círculo
$\includegraphics[scale=1]{figuras/pi_area.eps}$

Considerando A a área de $\frac{1}{4}$ de círculo parcialmente representado na figura 1, tem-se que:

$\begin{displaymath} A = \frac{1}{4} * \pi * r^2 \end{displaymath}$

(1)

$\begin{displaymath} A = l^2 * \frac{P_{in}}{P_{total}} \end{displaymath}$

(2)

sendo $P_{in}$ os pontos lançados aleatoriamente que ficaram dentro da área em cinza, e $P_{total}$ o número total de pontos gerados.

$\begin{displaymath} \begin{array}{c} \frac{1}{4} * \pi * r^2 = l^2 * \frac{P_in}... ...2 * \frac{P_{in}}{P_{total}}}{\frac{1}{4} * r^2}\\ \end{array}\end{displaymath}$

$\begin{displaymath} \pi = 4*\frac{P_{in}}{P_{total}} \end{displaymath}$

(3)

O algoritmo de cálculo consiste em gerar pontos

sendo $0 \leq x \leq 1$ e $0 \leq y \leq 1$ (vide figura 2). Identificar e contar os pontos $P_{in}$ e $P_{total}$ , e aplicar a equação 3.

**Figura:** Algoritmo de Cálculo do $\pi$
$\begin{figure}\centering\par\begin{boxedminipage}{12cm} \textbf{Entrada:} número... ... 4*\frac{P_{in}}{P_{total}}$\end{algorithmic}\end{boxedminipage}\par\end{figure}$

Paralelização do Processamento

Considerando que o processamento de cada uma das iterações pode ocorrer de forma independente, a forma mais simples de se pensar em particionar o problema é dividindo igualmente o numero de iterações pelo número de processadores disponíveis. No caso em que se pretende executar o problema sobre uma arquitetura homogênea, e de uso exclusivo, essa abordagem deverá apresentar bons resultados. Considerando uma arquitetura com máquinas heterogêneas, e de uso não exclusivo, a simples partição em tarefas de exigência semelhante não garante um bom desempenho. Nestes casos é necessário o emprego de alguma estratégia de distribuição de carga que leve em consideração o poder computacional corrente disponibilizado para a aplicação.

A medição do poder computacional disponibilizado é realizada com base no tempo de execução de cada tarefa. O ajuste do tamanho da tarefa é feito com base em uma meta de tempo estabelecida como parâmetro no disparo da aplicação.

Neste trabalho serão apresentados resultados comparando uma estratégia de particionamento uniforme e estático do problema com uma estratégia de particionamento não uniforme e dinâmico do mesmo problema.

No particionamento estático tem-se uma simplicidade maior no gerenciamento das tarefas, não sendo necessário também realizar um monitoramento nos tempos de execução das tarefas. Em contrapartida, a definição de um tamanho de tarefa é algo bastante difícil e dependente tanto da aplicação como dos equipamentos disponíveis. Considerando um ambiente de equipamentos heterogêneos e que variam dinamicamente esta tarefa torna-se ainda mais difícil, senão impossível.

Com a adoção do particionamento dinâmico, dependendo do poder computacional oferecido, ganha-se em facilidade no particionamento do problema, pois o sistema tende a ajustar-se automaticamente em função da meta de tempo estabelecida para cada tarefa. Em compensação, é inserido um overhead no sistema, para realizar o ajuste do tamanho das tarefas, e para fazer o monitoramento dos tempos de execução. Também consegue-se um maior sincronismo entre os processadores, quando da chegada na barreira de sincronização. No particionamento estático um processador de baixo poder computacional pode elevar o tempo de execução de toda aplicação, simplesmente por demorar muito tempo para completar a execução da última tarefa antes da barreira.

Implementação

A aplicação foi implementada em Java, seguindo um modelo Bag-of-tasks. Um servidor RMI é responsável pela distribuição das tarefas. Os EPs (elementos processadores) solicitam trabalho ao servidor RMI passando como parâmetro o tempo de execução da última tarefa, o servidor processa este tempo, avaliando os tempos anteriores e retorna uma tarefa para o EP. Ao término da execução da tarefa, o EP faz uma outra chamada RMI comunicando os resultados. Ao final do processamento de todas tarefas, o servidor RMI faz o processamento final dos resultados parciais, e encerra a execução.

A adoção da linguagem Java justifica-se pela necessidade de executar a aplicação em equipamentos heterogêneos. Com a utilização de Java, os problemas de incompatibilidade de binários e disponibilidade de bibliotecas ficam minimizados.

Resultados

Os testes foram realizados em workstations de uso interativo do Instituto de Informática. Para cada execução foram realizadas

iterações. Os equipamentos utilizados foram:

Estes equipamentos foram escolhidos por possuírem poderes computacionais diferentes, e também pelas diferenças de arquitetura e sistema operacional.

Nos testes, foram avaliadas e comparadas as duas estratégias de particionamento apresentadas na seção 3.

Na tabela 1 são apresentados resultados de duas execuções com especificação de tamanho de tarefa diferentes. Observa-se claramente que a especificação incorreta de um tamanho de tarefa pode comprometer completamente o desempenho da aplicação. No primeiro caso, com tamanho de tarefa 1000 observa-se um aumento excessivo no tempo de processamento em relação aos outros resultados. Neste caso, esta perda de desempenho ocorreu pela baixa granulosidade com que ficaram divididas as tarefas, o excesso de comunicações prejudicaram profundamente em seu desempenho. No segundo caso observa-se uma melhora significativa no tempo de execução devido a um ajuste manual feito sobre o tamanho de cada tarefa. É necessário observar que este ajuste manual só pode ser feito porque não houve variação nos equipamentos empregados.

Tabela: Resultados obtidos utilizando particionamento estático

Tamanho de cada tarefa	Tempo (s)
1000	3107.465
12 775 925	316.572

A tabela 2 apresenta os resultados obtidos nas execuções utilizando a estratégia de particionamento dinâmico. Foram utilizados os mesmos parâmetros iniciais que na execução através da estratégia de particionamento estático. É importante observar que o tamanho de tarefa indicado neste caso, é utilizado apenas como ponto de partida, sendo o tamanho de tarefa ajustado automaticamente ao longo da execução. Observa-se que o tempo de execução da aplicação mantém-se bem estável, mesmo com a variação brusca do tamanho da tarefa inicial.

Tabela: Resultados obtidos utilizando particionamento dinâmico

Tamanho inicial de cada tarefa	Tempo (s)
1000	302.586
12 775 925	291.793

Os gráficos apresentados nas figuras 3 e 4 ilustram a variação nos tamanhos das tarefas de cada host ao longo da execução da aplicação. Máquinas mais poderosas recebem tarefas maiores, enquanto que as máquinas menos poderosas recebem tarefas menores. Para estes testes foi estabelecido 10s como meta de tempo para cada tarefa.

**Figura 3:** Tamanho das tarefas por *host* com tamanho inicial de tarefa igual a 1000
$\includegraphics[scale=0.7]{figuras/jobsize-formab-1000.eps}$

**Figura 4:** Tamanho das tarefas por *host* com tamanho inicial de tarefa igual a 12775925
$\includegraphics[scale=0.7]{figuras/jobsize-formab-12775925.eps}$

Por este ser um método baseado em números aleatórios, o valor de $\pi$ encontrado varia a cada execução. Observa-se porém que para o número de iterações de Monte Carlo para o qual as execuções foram feitas, obtém-se um resultado próximo a

Considerações Finais

A utilização de equipamentos de uso compartilhado para processamento de problemas computacionalmente intensivos é uma alternativa real, e pode apresentar bons resultados a um baixo custo. O bom desempenho está diretamente relacionado ao tipo de aplicação com que se está trabalhando, e com a forma como a paralelização foi feita. Programas paralelos que possuem muitos pontos de sincronização, ocasionando muitas comunicações, tendem a não gerarem bons resultados em arquiteturas de máquinas de uso compartilhado.

Em ambientes heterogêneos, e de alta dinamicidade o uso de estratégias mais elaboradas para distribuição de carga apresenta ganhos significativos, tanto em desempenho como na facilidade da parametrização da execução;

A adição de uma boa estratégia de ajuste no tamanho das tarefas oferece a possibilidade de, mesmo especificando parâmetros de inicialização não otimizados, obter bons resultados em termos de performance.

Referências Bibliográficas

About this document ...

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

The command line arguments were:
latex2html -dir ../html/ -split 0 calcpi.tex

Aproximação do $\pi$ pelo Método de Monte Carlo