Ordenação de Mensagens e Pré-Condicionamento na Solução Paralela do Gradiente Conjugado em Clusters de PCs Multiprocessados

• Delcino Picinin Jr UFRGS
• André L. Martinotto UFRGS
• Rogério L. Rizzi UFRGS / UNIOESTE
• Ricardo V. Dorneles UFRGS / UCS
• Tiaraju A. Diverio UFRGS
• Philippe O. A. Navaux UFRGS

DOI: https://doi.org/10.5753/wscad.2002.20767

Resumo

Este trabalho apresenta uma solução paralela para o algoritmo do gradiente conjugado pré-condicionado de modo a resolver sistemas de equações lineares simétricos definidos-positivos em cluster multiprocessado. Essa solução paralela é obtida via decomposição de dados, onde o domínio computacional é particionado usando o algoritmo RCB (Recursive Coordinate Bisection), de modo a minimizar as comunicações e balancear a carga computacional. O modelo de programação utilizado é o SPMD e o paralelismo entre os nodos no cluster de PCs é explorado via troca de mensagens usando a biblioteca MPICH. A troca de mensagens entre os processos usa dois algoritmos de ordenação para evitar deadlock e melhorar o desempenho computacional. O paralelismo intra-nodal é explorado empregando a biblioteca Pthreads.

Referências

BARRETI, R., BERRY, M., CHAN, T. F., DEMMEL, J., DONATO, J. M., DONGARRA, J., EIJKHOUT, V. POZO, ROLDAN, ROMINE, C., VORST, H. V. Templates for the Solution of Linear Systems: building Blocks for lterative Methods. 1994. Disponível em http://www.netlib.org.

CATABRIGA, L. Estudo de Pré-condicionadores para o Método GMRES usando Estruturas de Dados por Arestas. Seminário de Qualificação ao doutorado, COPPE, UFRJ, Maio 1998. Disponível em http://www.coc.ufrj.br/~luci/.

GAREY, M. R., JOHNSON, D. S. Computer and Intractability: a guide to the theory of NP-completeness. Freeman, San Francisco, 1979.

JÚDICE, J. J., PATRICIU, J.M. Sistemas de Equações Lineares. Departamento de Matemática da Universidade de Coimbra, Coimbra, Portugal, 1996.

MARTINOTTO, A. L., FRIZZO, E. J., DORNELES R. V., DIVERIO, T. A. Paralelização do Método do GMRES com MPI e Threads, SCIENTIA, São Leopoldo, 2002. (em avaliação).

RIZZI, R. L., ZEFERINO, C. A., DORNELES, R. V., NAVAUX, P. O. A., BAMPI, S., SUZIN, A. A., DIVERIO, T. A. Fluvial Flowing of Guaiba River Estuary: A Parallel Solution for the Shallow Water Equations Model in: Proceedings of the Fourth Vecpar. 2000. p. 895-896, Porto, Portugal, 2000.

SHEWCHUCK, Jonathan. R. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. School of Computer Science. Carnegie Mellon University, 1994.

SILVA, R. S. et al. Iterative Local Solvers for Distributed Krylov-Schwarz Method Applied to Convection-Diffusion Problems. Computer Methods for Applied Mechanics and Engineering, Vol. 149, 353-362, 1997.

SMITH, B., BJORSTAD, P., GROPP, W., Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University, 1996.