Uma Ferramenta para o Desenvolvimento de Modelos de Simulaç

Uma Ferramenta para o Desenvolvimento de Modelos de
Simulação Integrado ao Ambiente Grid
G.R. Berkenbrock1 , P.J. Freitas Filho1
1
Departamento de Informática and Estatı́stica (INE)
Universidade Federal de Santa Catarina (UFSC)
88040-900, Florianópolis, Brasil
{gianr,freitas}@inf.ufsc.br
Abstract. The increase of computational capacity the study in the areas of high
performance computing has grown. Areas as grid computing and parallel and
distributed discrete simulation are a demonstration of this necessity when using
coordinate resources in network. In particular, the grid computing is having a
bigger approach for the newness that it presents. For use the grid computing new
programs have appeared to explore it. One kind of use of the grid computing
would be to process distributed or parallel discrete simulations. This paper is
considering a tool to create models of discrete simulation integrated to a grid
computing.
Resumo. Com o aumento de capacidade computacional tem crescido o estudo
nas áreas de computação de alto desempenho. Áreas como ambientes em grid
e simulação discreta paralela e distribuı́da são uma demonstração desta necessidade de se utilizar coordenadamente recursos interligados em rede. Em
particular, os ambientes em grid estão tendo um enfoque maior pela novidade
que ele apresenta. Com o surgimento desses ambientes, novos programas tem
aparecido para explorá-lo. Um tipo de utilização do ambiente grid seria a de
processar simulações discretas distribuı́das ou paralela e para isso está se propondo uma ferramenta para criar modelos de simulação discreta conectada ao
ambiente grid.
1. Introdução
Com o aumento de capacidade computacional que está ocorrendo no mercado, ambientes
de alto desempenho estão tornando-se cada vez mais populares. Um dos tipos de programas que necessitam desse poder computacional são os programas voltados a executar
modelos de simulação discreta no menor tempo possı́vel. Para atingir esse objetivo existe
a abordagem para executar os modelos de forma paralela ou distribuı́da.
Pode-se ressaltar duas das vantagens em se executar um modelo em paralelo/ distribuı́do sobre a execução em modo seqüencial: (1) tempo de execução reduzido e (2)
tolerância a falha em tempo de execução. Cabe destacar que para esse processamento
do programas em paralelo, se faz o uso de protocolos de sincronização. Esses são responsáveis em executar os eventos na ordem correta.
Contudo, esses programas precisam de um ambiente de alto desempenho para
executar. Neste estudo foram escolhidos os ambientes em cluster e os ambientes em grid,
onde a ênfase está no segundo citado. O ambiente em grid é focado em prover um alto
desempenho e no compartilhamento de recursos geograficamente distribuı́dos.
Na atualidade, se um usuário desejar construir um modelo de simulação para ser
executado no grid, ele precisaria ser conhecedor, não apenas da área em questão para a
construção do modelo, mas também de lógica e linguagem de programação.
A pouca oferta de ambientes de modelagem integrados com grid para o públicoalvo (modeladores) faz com que a execução de modelos de simulação fiquem restritos a
usuários com conhecimento muito especı́fico, o que não deixa o modelador se preocupar
com o mais importante, que é a modelagem. Neste contexto é que se insere essa proposta
de pesquisa.
Este artigo esta organizado da seguinte forma. A seção 2 apresenta a
fundamentação teórica abordando conceitos da computação de alto desempenho. Na
seção 3 são apresentados fundamentos da simulação discreta paralela e distribuı́da. A
seção 4 aborda a proposta de um ambiente integrado com grid, apresenta questões de
projeto e o que se almeja alcançar. Por fim, na seção 5 são apresentados os comentários
finais.
2. Computação de Alto Desempenho
Atualmente tem aumentado a demanda por poder computacional para os programas, que tenham a finalidade de resolver problemas crı́ticos/complexos, e obter
suas respostas no menor tempo possı́vel [Pitanga, 2003, Patterson and Hennessy, 2003,
Sulistio et al., 2003]. Em adição, temos que freqüentemente os programas necessitam de
mais poder computacional do que um computador seqüencial pode prover [Buyya, 1999].
Mas conforme [Maccabe, 1993], nem sempre é óbvio como milhares de processadores
podem resolver um dado problema.
Portanto, para tentar suprir estas necessidades, iniciou-se o desenvolvimento das
máquinas paralelas. Essa área, que já tem algumas décadas de experiência, demonstrou
claramente seus fatores crı́ticos, por exemplo, largura de banda, latência das redes e gerenciamento [Sterling, 2001, Buyya, 1999].
Segundo
os
autores
[Meredith et al., 2003,
Apon et al., 2001,
Vaughan et al., 2003, van der Steen, 2003, Buyya, 1999], o custo de máquinas paralelas é relativamente alto. Desta forma, foi desenvolvida uma opção mais barata e tão
potente quanto as máquinas paralelas, denominado cluster (agregado) de computadores. Na linha de evolução no desenvolvimento da computação de alto desempenho
surgiu, em meados dos anos de 1990, o conceito de grid, que é uma proposta de
infra-estrutura de computação distribuı́da para a ciência e a engenharia avançada
[Foster and Kesselman, 1999].
2.1. Computação em Cluster
Um cluster ou agregado é um conjunto de computadores independentes que são conectados através de uma rede de interconexão de alta/baixa latência, trabalhando cooperativamente para resolver um determinado problema/tarefa. Dessa maneira, o
usuário tem a noção de que todos esses computadores são apenas um [Pitanga, 2003,
Patterson and Hennessy, 2003, Maccabe, 1993, Buyya, 1999]. Atualmente, ele tem se
tornado uma opção de uso para as empresas, universidades e centros de pesquisa
[De Rose and Navaux, 2004].
2.2. Computação em Grid
A computação em grid, conforme mencionado em [Dantas, 2002], pode ser definida como
computação paralela geograficamente distribuı́da. Esse conceito completa a definição de
Foster[Foster and Kesselman, 1999], onde um grid computacional é definido como uma
infra-estrutura de computadores e programas que provê um acesso confiável, coerente,
difundido e econômico à um potencial computacional final. Completando, Foster em
[Foster et al., 2001] comenta que a computação em grid está preocupada com o compartilhamento de recursos coordenados e comprometida com problemas em organizações
virtuais(OV) [Foster et al., 2001].
3. Simulação Discreta Paralela e Distribuı́da
A Simulação discreta paralela e distribuı́da é uma tecnologia que possibilita a execução
de modelos em sistemas computacionais paralelos/distrbuı́dos. [Fujimoto, 2000]. Uma
simulação paralela é focada para ser executada em multiprocessadores. A simulação
distribuı́da está voltada a executar os modelos em computadores geograficamente distribuı́dos [Fujimoto, 1999]. Existem alguns fatores que influenciam a execução dos modelos em múltiplos computadores. Fujimoto [Fujimoto, 2000, Fujimoto, 1999] e Zeigler
[Zeigler et al., 2000] listam alguns deles como: redução no tempo de execução/aumento
de velocidade, aumento no tamanho do modelo, interoperabilidade e compartilhamento
de recursos, integração de simuladores que executam em computadores de diferentes fornecedores, tolerância a falhas.
Em [Fujimoto, 2000], Fujimoto menciona que atualmente duas classes de
aplicações da simulação tem ganho mais atenção: Simulações Analı́ticas e Ambientes Virtuais. As aplicação de simulações analı́ticas normalmente estão preocupadas em capturar
dados detalhados sobre o sistema que será simulado. Esse tipo de aplicação ainda requer
que o modelo reproduza com a máxima exatidão o comportamento do sistema a ser simulado para que as estatı́sticas geradas sejam válidas. É a forma clássica de simulação.Nos
ambientes virtuais, o objetivo central é o de dar a sensação aos usuários de estarem inseridos no sistema modelado. Quase sempre este tipo de aplicação incluem a participação
dos usuários como entidades dentro da simulação.
Mas cabe salientar que nem tudo é perfeito, problemas podem ser encontrados
no momento da execução tanto no modelo quanto na configuração adotada para realizar a execução. Murphy em seu artigo [Murphy and Perera, 2002] comenta alguns sucessos e falhas no desenvolvimento de simulações. Bagrodia em [Bagrodia, 1996] comenta algumas ciladas que devem ser evitadas pelo analista para conseguir projetar uma
implementação paralela eficiente como: cuidado com variáveis compartilhadas, atenção
com ponteiros para estruturas de dados, ciclos com delay zero, lookahead pobre, carga
sem equilı́brio nos nós, alto tráfico de mensagens, baixo paralelismo.
Fishwick em seu livro [Fishwick, 1995] menciona que em geral todos os tipos de
modelos seriam apropriados para executá-los em paralelo. Mas na prática os melhores
modelos para serem executados em paralelos são os modelos espaciais e os funcionais.
Para executar os modelos através dos programas, de simulação discreta, nos ambientes
paralelos/dsitribuı́dos existem duas abordagens de protocolos de sincronização quanto ao
tipo de particionamento do modelo e ao objetivos pretendidos da execução. A primeira
abordagem, denominada Single Replication In Parallel (SRIP), possibilita a execução de
um modelo em paralelo de uma única replicação. Já a segunda abordagem, denominada
Multiple Replication In Parallel (MRIP), possibilita a execução em paralelo mas de várias
replicações. Para executar usando a abordagem SRIP, o modelo é particionado em processos lógicos (PL), os quais são mapeados como processos fı́sicos. Os processos lógicos se
comunicam através de mensagens contendo o tempo e o evento deste determinado tempo
[Fujimoto, 2000, Zeigler et al., 2000, Niewiadomska-Szynkiewicz and Sikora, 2002]. Já
no sistema MRIP, todo o modelo está em um processo lógico que está mapeado à um pro-
cesso fı́sico e que troca informações sobre suas estatı́sticas obtidas com um controlador
mestre.
4. Simulador Visual
Um protótipo de uma ferramenta de edição gráfica está sendo desenvolvido para auxiliar
na geração de código-fonte de programas de simulação discreta. Esta também poderá ser
usada como auxı́lio no ensino da simulação discreta seqüencial, paralela e distribuı́da.
O código-fonte gerado por essa ferramenta gráfica será de programas que a priori
serão executados em ambientes grid. Esse ambiente está em fase de desenvolvimento no
PerformanceLab(http://www.performancelab.inf.ufsc.br). O ambiente grid do laboratório
utiliza a ferramenta Globus [University of Chicago, 2004] para o middleware grid e a
ferramenta OSCAR [Open Cluster Group, 2003, Mattson, 2001] para o gerenciamento do
cluster, o qual no momento conta com três computadores.
A ferramenta gráfica irá utilizar de algum padrão de “desenho” para a
representação do modelo que irá ser simulado. Existem as seguintes opções que possam ser adotadas: fluxograma(figura 1), Arena-like(figura 2) e diagrama de atividade da
Unified Modelling Language (UML)(figura 3). Ela também fará uso de programas ou
bibliotecas de código-fonte aberto para obter maior produtividade no desenvolvimento.
A ferramenta será de código-aberto para permitir o compartilhamento do conhecimento
com a comunidade e também para facilitar o recebimento de crı́ticas e sugestões.
Figure 1: Exemplo de um fluxograma
Figure 2: Exemplo de um fluxograma no estilo Arena
Para o desenvolvimento da interface gráfica, onde o usuário (modelador) irá trabalhar, existem três opções:
1. Desenvolver uma infra-estrutura necessária;
Figure 3: Diagrama de Atividade da UML[Borland Corporation, 2004]
Figure 4: IsaViz
2. Utilizar uma biblioteca para essa finalidade, por exemplo JHotDraw[sit, 2004];
3. Especializar o IsaViz[Pietriga, 2004] (figura 4) para ficar mais amigável de se utilizar, como apresenta a figura 5 realizado por [Veiga and Porto, 2004].
Para gerar o programa que representará o modelo, existem as seguintes possibilidades:
1. Desenvolver uma biblioteca para esse fim (Sequencial/Paralela/Distribuı́da/Grid);
2. Utilizar uma biblioteca (código-aberto) de terceiro.
A linguagem de programação do programa-alvo deverá ser C++, portanto a biblioteca
deverá ser nessa linguagem ou ter suporte para ela. A opção de se usar C++ é de se tentar
alcançar o melhor desempenho possı́vel em tempo de execução e também pelo suporte
de bibliotecas de troca de mensagens. A linguagem Java será apenas utilizada para o
desenvolvimento da interface.
A arquitetura do projeto deverá atender da melhor maneira o usuário. Portanto, o
programa funcionará de acordo com a figura 6. O usuário terá a possibilidade de modelar
tanto no portal do grid quanto em um outro computador onde estará instalado o programa.
Para executar, no ambiente grid, o usuário irá enviar as definições do modelo pro portal,
Figure 5: mIsaViz
que então gerará o programa e o executará. Será enviado apenas as definições para exigir
menos da máquina do usuário, pois dessa maneira ele precisará apenas da ferramenta e de
mais nenhum programa em especial. Caso o usuário queira executar localmente, isto é,
em sua máquina, existirá a opção de gerar o código-fonte em seu computador, mas para
executar ele precisará de um compilador C++ e um determinado conjunto de bibliotecas,
por exemplo, biblioteca de suporte estatı́stico e matemático ou bibliotecas de troca de
mensagens. O modo como o programa será executado no grid ainda precisa ser definido.
Pois para executar o programa precisa definir os protocolos de sincronização que serão
utilizados e também qual ferramenta/bilbioteca de troca de mensagens que será utilizada.
No entanto, deve estar previsto no projeto da ferramenta a troca de protocolos ou adição
de novos que poderão aparecer.
Figure 6: Demonstração do uso do simulador visual ligado ao grid
5. Comentários Finais
Neste trabalho apresenta-se um projeto de pesquisa que propõe o encaminhamento de uma
solução ao problema da pouca oferta de ambientes gráficos para a criação de modelos de
simulação discreta integrados com ambientes grid. Para isto, pretende-se desenvolver
uma ambiente gráfico para a criação e edição de modelos de simulação para rodar em ambientes grid. Para tentar alcançar esse objetivo está sendo desenvolvimento um protótipo
da ferramenta. Esse protótipo deverá gerar alguma documentação que servirá como base
para trabalhos futuros.
References
(2004). Jhotdraw. http://www.jhotdraw.org/.
Apon, A., Buyya, R., Jin, H., and Mache, J. (2001). Cluster computing in the classroom:
Topics, guidelines, and experiences. In The First IEEE/ACM International Symposium
on Cluster Computing and the Grid (CCGrid 2001), pages 476–483.
Bagrodia, R. (1996). Perils and pitfalls of parallel discrete-event simulation. In Winter
Simulation Conference, pages 136–143.
Borland Corporation (2004). The uml practical guide. http://www.borland.com/.
Buyya, R., editor (1999). High Performance Cluster Computing: Architectures and Systems, volume 1. Prentice Hall.
Dantas, M. (2002). Tecnologias de Redes de Comunicação e Computadores. Axcel Books
do Brasil Editora.
De Rose, C. A. F. and Navaux, P. O. A. (2004). Fundamentos de processamento de alto
desempenho. In ERAD 2004 - 4a. Escola Regional de Alto Desempenho, pages 41–66.
Fishwick, P. A. (1995). Simulation Model Design and Execution: Building digital worlds.
Prentice-Hall.
Foster, I. and Kesselman, C., editors (1999). The Grid: Blueprint for a New Computing
Infrastructure. Morgan Kaufmann.
Foster, I., Kesselman, C., and Tuecke, S. (2001). The anatomy of the grid: Enabling
scalable virtual organizations. International Journal of High Performance Computing
Applications, 15(2):200–222. http://www.globus.org/research/papers/anatomy.pdf.
Fujimoto, R. M. (1999). Parallel and distributed simulation. In Proceedings of the 31st
conference on Winter simulation, pages 122–131. ACM Press.
Fujimoto, R. M. (2000). Parallel and Distributed Simulation Systems. Wiley-Interscience.
Maccabe, A. B. (1993). Computer Systems: architecture, organization and programming.
McGraw-Hill, New York.
Mattson, T. G. (2001). High performance computing at intel: the oscar software solution
stack for cluster computing. In First IEEE/ACM International Symposium on Cluster
Computing and the Grid, pages 22–25.
Meredith, M., Carrigan, T., Brockman, J., Cloninger, T., Privoznik, J., and Williams, J.
(2003). Exploring beowulf clusters. J. Comput. Small Coll., 18(4):268–284.
Murphy, S. and Perera, T. (2002). Successes and failures in uk/us development of simulation. Simulation Practice and Theory 9, 9:333–348.
Niewiadomska-Szynkiewicz, E. and Sikora, A. (2002). Algorithms for distributed simulation - comparative study. In International Conference on Parallel Computing in
Electrical Engineering, pages 261–266.
Open Cluster Group (2003). Oscar : Open source cluster application resources.
http://oscar.openclustergroup.org/.
Patterson, D. A. and Hennessy, J. L. (2003). Arquitetura de Computadores: Uma abordagem quantitativa. Campus, Rio de Janeiro, 3 edition. tradução de Vanderberg D. de
Souza.
Pietriga, E. (2004).
Isaviz:
http://www.w3.org/2001/11/IsaViz/.
A
visual
authoring
tool
for
rdf.
Pitanga, M. (2003). Computação em Cluster. Brasport.
Sterling, T. (2001). An introduction to pc clusters for high performance computing.
International Journal of High Performance Computing Applications, 15(2):92–101.
http://ejournals.ebsco.com/direct.asp?ArticleID=J4H09A7A169BUCJ6547Y.
Sulistio, A., Yeo, C. S., and Buyya, R. (2003). A taxonomy of computer-based simulations
and its mapping to parallel and distributed systems simulation tools. International
Journal of Software: Practice and Experience.
University of Chicago (2004). The globus toolkit. http://www-unix.globus.org/toolkit/.
van der Steen, A. J. (2003). An evaluation of some beowulf clusters. Cluster Computing,
6(4):287–297. http://dx.doi.org/10.1023/A:1025791808283.
Vaughan, F. A., Grove, D. A., and Coddington, P. D. (2003). Communication performance
issues for two cluster computers. In Proceedings of the twenty-sixth Australasian computer science conference on Conference in research and practice in information technology, pages 171–180. Australian Computer Society, Inc.
Veiga, D. F. and Porto, L. M. (2004).
Metabolic
http://www.intelab.ufsc.br/genomica/misaviz/index.html.
isaviz
project.
Zeigler, B. P., Praehofer, H., and Kim, T. G. (2000). Theory of Modeling and Simulation:
Integrating Discrete Event and Continuous Complex Dynamic Systems. Harcourt India
Private Limited, second edition.