Comparação entre Métodos de Decomposição de Domínio e Decomposição de Dados na Solução de Sistemas de Equações
Resumo
Neste trabalho é apresentado um estudo comparativo entre as abordagens de decomposição de dados e decomposição de domínio para a resolução em paralelo de sistemas de equações. As duas abordagens mostraram-se eficientes, com bons ganhos de desempenho na resolução de sistemas de equações. Nos testes efetuados a abordagem de decomposição de dados mostrou-se mais adequada para uma quantidade menor de processos, enquanto que a abordagem de decomposição de domínio mostrou-se mais escalável, comportando-se melhor com quantidades mais elevadas de processos.
Referências
OPENMP: Simple, Portable, Scalable SMP Programming. Disponível em: http://www.openmp.org/. Acesso em: out. 2003, 2003.
R. Buyya. High Performance Cluster Computing: Architecture and Systems, volume 1. Prentice Hall, 1999.
A. P. Canal. Paralelização de Métodos de Resolução de Sistemas Lineares Esparsos com o DECK em Clusters de PCs. Master's thesis, Instituto de Informática, UFRGS, Porto Alegre, 2000. Foz do Iguaçu, 27 a 29 de Outubro de 2004
A. Chan, D. Ashton, R. Lusk, and W. Gropp. Jumpshot- 4's User's Guide, 2003. Disponível em http://www-unix.mcs.anl.gov/perfvis/software/viewers/. Acesso em: out. 2003.
A. Chan, W. Gropp, and E. Lusk. User's Guide for MPE: Extensions for MPI programs, 2003. Disponível em http://www-unix.mcs.anl.gov/mpi/mpich/. Acesso em: out. 2003.
A. S. Charão. Multiprogrammation Paralèle Générique des Méthodes de Décomposition de Domaine. PhD thesis. Institui National Polytechnique de Grenoble, 2001.
L. Debreu andE. Blayo. On the Schwarz Altemating Method for Solving Oceanic Models on Parallel Computers. Joumal of Computational Physics, 141:93-111, 1998.
R. V. Domeles. Particionamento de Domínio e Balanceamento de Carga no Modelo HIDRA. PhD thesis, Instituto de Informática, UFRGS, Porto Alegre-RS, 2003.
A. O. Fortuna. Técnicas Computacionais para Dinâmica dos Fluidos. Editora da Universidade de São Paulo, 2000.
G. Galante, A. L. Martinotto, R. L. Rizzi, and T. A. Diverio. Solução Paralela de Sistemas de Equações Lineares Através de Métodos de Decomposição de Domínio. In ERAD 2004. Pelotas, RS, 2004.
M. R. Garey and D. S.Johnson. Computer and lntractability: a Guide to the Theory of NP-completeness. Freeman, San Francisco, 1979.
G. Karypis and V. Kumar. METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes. and Computing Fill-reducing Orderings of Sparse Matrices, 1998. Disponível em: http://www.cs.umn.edu/~karypis. Acesso em: out. 2003.
A. L. Martinouo, D. Picinin, R. L. Rizzi, R. V. Domeles, and T. A. Diverio. Paralelização de Métodos Númericos para a Solução de Sistemas de Equações Lineares. In ERAD 2004. Pelotas, RS, 2004.
P. S. Pacheco. Parallel Programming with MPI. Morgan Kaufmann, San Francisco, 1997.
D. Picinin. Paralelização de Métodos Numéricos em Clusters Empregando as Bibliotecas MPI, DECK e Pthreads. Master's thesis, Instituto de Informática, UFRGS, Porto Alegre. 2003.
R. L. Rizzi. Modelo Computacional Paralelo para a Hidrodinâmica e para o Transporte de Massa Bidimensional e Tridimensional. PhD thesis, Instituto de Informática. UFRGS, Porto Alegre, 2002.
Y. Saad. Ieralive Melhods for Sparse Linear Systems. PWS Publishing Company, 1996.
J. R. Shewchuk. An lntroduction to the Conjugate Gradient Method without the Agonizing Pain. Disponível em: http://www.cs.cmu.edu/~jrs/jrspapers.html. Acesso em: out. 2003, 1994.
B. Smith, P. Bjorstad, and W. Gropp. Doma in Decomposition: Parallel Multilevel Methods for Elliptic Partial Diferential Equations. Cambridge University Pres, Cambridge. 1996.
M. Snir, S. Otto, S. Huss-Ledermann, D. Walker, and J. Dongarra. MPI: The Complete Reference. MIT Press, 1996.
R. Buyya. High Performance Cluster Computing: Architecture and Systems, volume 1. Prentice Hall, 1999.
A. P. Canal. Paralelização de Métodos de Resolução de Sistemas Lineares Esparsos com o DECK em Clusters de PCs. Master's thesis, Instituto de Informática, UFRGS, Porto Alegre, 2000. Foz do Iguaçu, 27 a 29 de Outubro de 2004
A. Chan, D. Ashton, R. Lusk, and W. Gropp. Jumpshot- 4's User's Guide, 2003. Disponível em http://www-unix.mcs.anl.gov/perfvis/software/viewers/. Acesso em: out. 2003.
A. Chan, W. Gropp, and E. Lusk. User's Guide for MPE: Extensions for MPI programs, 2003. Disponível em http://www-unix.mcs.anl.gov/mpi/mpich/. Acesso em: out. 2003.
A. S. Charão. Multiprogrammation Paralèle Générique des Méthodes de Décomposition de Domaine. PhD thesis. Institui National Polytechnique de Grenoble, 2001.
L. Debreu andE. Blayo. On the Schwarz Altemating Method for Solving Oceanic Models on Parallel Computers. Joumal of Computational Physics, 141:93-111, 1998.
R. V. Domeles. Particionamento de Domínio e Balanceamento de Carga no Modelo HIDRA. PhD thesis, Instituto de Informática, UFRGS, Porto Alegre-RS, 2003.
A. O. Fortuna. Técnicas Computacionais para Dinâmica dos Fluidos. Editora da Universidade de São Paulo, 2000.
G. Galante, A. L. Martinotto, R. L. Rizzi, and T. A. Diverio. Solução Paralela de Sistemas de Equações Lineares Através de Métodos de Decomposição de Domínio. In ERAD 2004. Pelotas, RS, 2004.
M. R. Garey and D. S.Johnson. Computer and lntractability: a Guide to the Theory of NP-completeness. Freeman, San Francisco, 1979.
G. Karypis and V. Kumar. METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes. and Computing Fill-reducing Orderings of Sparse Matrices, 1998. Disponível em: http://www.cs.umn.edu/~karypis. Acesso em: out. 2003.
A. L. Martinouo, D. Picinin, R. L. Rizzi, R. V. Domeles, and T. A. Diverio. Paralelização de Métodos Númericos para a Solução de Sistemas de Equações Lineares. In ERAD 2004. Pelotas, RS, 2004.
P. S. Pacheco. Parallel Programming with MPI. Morgan Kaufmann, San Francisco, 1997.
D. Picinin. Paralelização de Métodos Numéricos em Clusters Empregando as Bibliotecas MPI, DECK e Pthreads. Master's thesis, Instituto de Informática, UFRGS, Porto Alegre. 2003.
R. L. Rizzi. Modelo Computacional Paralelo para a Hidrodinâmica e para o Transporte de Massa Bidimensional e Tridimensional. PhD thesis, Instituto de Informática. UFRGS, Porto Alegre, 2002.
Y. Saad. Ieralive Melhods for Sparse Linear Systems. PWS Publishing Company, 1996.
J. R. Shewchuk. An lntroduction to the Conjugate Gradient Method without the Agonizing Pain. Disponível em: http://www.cs.cmu.edu/~jrs/jrspapers.html. Acesso em: out. 2003, 1994.
B. Smith, P. Bjorstad, and W. Gropp. Doma in Decomposition: Parallel Multilevel Methods for Elliptic Partial Diferential Equations. Cambridge University Pres, Cambridge. 1996.
M. Snir, S. Otto, S. Huss-Ledermann, D. Walker, and J. Dongarra. MPI: The Complete Reference. MIT Press, 1996.
Publicado
27/10/2004
Como Citar
GALANTE, Guilherme; DIVERIO, Tiarajú Asmuz; MARTINOTTO, André Luis; PICININ JÚNIOR, Delcino; DORNELES, Ricardo Vargas; RIZZI, Rogério Luis.
Comparação entre Métodos de Decomposição de Domínio e Decomposição de Dados na Solução de Sistemas de Equações. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 5. , 2004, Foz do Iguaçu.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2004
.
p. 98-104.
DOI: https://doi.org/10.5753/wscad.2004.19006.
