Implementação do Método dos Gradientes Conjugados em Multiprocessadores com Arquitetura Hipercúbica
Resumo
Neste trabalho, são apresentadas implementações paralelas do algoritmo do Gradiente Conjugado (GC) Precondicionado para resolução de sistemas lineares de equações esparsas, em multiprocessadores com arquitetura hipercúbica. As computações do algoritmo GC paralelo consistem primordialmente de operações matriciais que são implementadas em cada nó do hipercubo, utilizando esquemas com paralelismo de dados. A implementação paralela síncrona (no iPSC/860) apresenta razoável desempenho, por outro lado uma versão assíncrona preliminar apresentou problemas de convergência em sistemas de equações de porte médio provenientes de cálculo estrutural.
Referências
Bertsekas, D.P., Tsitsiklis, J.N.: 'Parallel and Distribuited Computation: Numerical Methods'. Prentice-Hall Inc., Englewood, N.Y., 1989.
Fox, G.C., Johnson, M.A., Lyzenga, G.A., Otto, S.W., Salmon, J.K., Walker, D.W.: 'Solving Problems on Concurrent Processors'. Prentice-Hall, Englewood Cliffs, N.J., 1988.
Gustafson, J.L., Montry, G.R, Benner, R.E.: 'Development of Parallel Methods for a 1024-Processor Hypercube'. Siam J. Sci. Stat. Comput., vol. 9, no 4, jul 1988.
Justino, M.R.F.:'Solugéo Multi-frontal de Sistemas de Equações Algébricas Lineares Esparsas Simétricas Esparsas', Seminário de Doutorado do Programa de Engenharia Civil - COPPE/UFRJ, 19 de dezembro de 1990.
Cabral, R.G.: 'Avaliação do Desempenho do Método dos Gradientes Conjugados em Multiprocessadores com Arquitetura Hipercúbica'. Tese de Mestrado COPPE/UFRJ. Março de 1991, Rio de Janeiro.
George A. e Liu,J.W.H.: 'Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Inc. Engewood Cliffs, New Jersey 1981.
Chan, T.F. e Saad, Y.: 'Multigrid Algorithms on the Hipercube Multiprocessor'. IEEE Transactions on Computers, vol-35, no 11, novembro de 1986.
Chen, M.S., Shin, K.G.:'Processor Allocation in an N-Cube Multiprocessor Using Gray Codes'. IEEE Trans. on Computers, vol 36, no 12, dez 1987.
Abe, G.B. e Hane, K.: 'The Preconditioned Conjugate Gradient Method on the Hypercube'. The Third Conference on Hypercube Concurrent Computers and Applications, Pasadena, California, jan 1988.
Van Der Vorst, H.K., e Dekker: 'Conjugate Gradiente Type Methods and Preconditioning'. Journal of Computational and Mathematics 24, pp 73-87, North-Holland, novembro de 1988.
Golub, G.H. e Van Loan, C.F.: 'Matrix Computations'. The Johns Hopkins Universty Press, Baltimore, Maryland 1983.
Aykanat, C., Ozguner, F., Ercal, F., Sadayapan, P.: 'Iterative Algorithms for Solution of Large Sparse Systems of Linear Equations on Hypercubes'. IEEE Transactions on Computers, vol-37, no 12, dezembro 1988.
Ortega, J.M.: 'Introduction to Parallel and Vector Solution of Linear Systems'. Plenum Press, New York and London, 1988.
Hillis, W.D., Steele, G.L.Jr.:'Data Parallel Algorithms', Communications of the ACM, vol 29, no 12, dez 1986, pg 1170-1183.
Ni, L.M., King, C.T.'On Partitioning and Mapping for Hypercube Computing'. International Journal of Parallel Programming, vol 17, no 5, pg 475-495, 1988.
Luenberger,D. : "Introdution to Linear and Nonlinear Programming". Reading , MA : Addison Wesley, 1973.
Kaszkurewies,E., Bhaya,A. e Siljak, D.D.: 'On the Convergence of Parallel Asynchronous Block-Iterative Computations'. Linear Algebra and Its Applications pg 139-160. Elsevier Science Publishing Co., Inc., 1990.
Decker, LC., Falcão, D.M., Kaszkurewicz, E.: 'Parallel Implementation of a Power System Simulation Methodology using the Conjugate Gradient Method'. IEEE-Transactions on Power System Computation Conference, pp 509-519, 1991.
Eager, D.L., Zahorjan, J., Lazowska, E.D.: 'Speedup Versus Efficiency in Parallel Systems'. IEEE-Transactions on Computers, vol 38, no 3, mar 1989.
Fox, G.C., Johnson, M.A., Lyzenga, G.A., Otto, S.W., Salmon, J.K., Walker, D.W.: 'Solving Problems on Concurrent Processors'. Prentice-Hall, Englewood Cliffs, N.J., 1988.
Gustafson, J.L., Montry, G.R, Benner, R.E.: 'Development of Parallel Methods for a 1024-Processor Hypercube'. Siam J. Sci. Stat. Comput., vol. 9, no 4, jul 1988.
Justino, M.R.F.:'Solugéo Multi-frontal de Sistemas de Equações Algébricas Lineares Esparsas Simétricas Esparsas', Seminário de Doutorado do Programa de Engenharia Civil - COPPE/UFRJ, 19 de dezembro de 1990.
Cabral, R.G.: 'Avaliação do Desempenho do Método dos Gradientes Conjugados em Multiprocessadores com Arquitetura Hipercúbica'. Tese de Mestrado COPPE/UFRJ. Março de 1991, Rio de Janeiro.
George A. e Liu,J.W.H.: 'Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Inc. Engewood Cliffs, New Jersey 1981.
Chan, T.F. e Saad, Y.: 'Multigrid Algorithms on the Hipercube Multiprocessor'. IEEE Transactions on Computers, vol-35, no 11, novembro de 1986.
Chen, M.S., Shin, K.G.:'Processor Allocation in an N-Cube Multiprocessor Using Gray Codes'. IEEE Trans. on Computers, vol 36, no 12, dez 1987.
Abe, G.B. e Hane, K.: 'The Preconditioned Conjugate Gradient Method on the Hypercube'. The Third Conference on Hypercube Concurrent Computers and Applications, Pasadena, California, jan 1988.
Van Der Vorst, H.K., e Dekker: 'Conjugate Gradiente Type Methods and Preconditioning'. Journal of Computational and Mathematics 24, pp 73-87, North-Holland, novembro de 1988.
Golub, G.H. e Van Loan, C.F.: 'Matrix Computations'. The Johns Hopkins Universty Press, Baltimore, Maryland 1983.
Aykanat, C., Ozguner, F., Ercal, F., Sadayapan, P.: 'Iterative Algorithms for Solution of Large Sparse Systems of Linear Equations on Hypercubes'. IEEE Transactions on Computers, vol-37, no 12, dezembro 1988.
Ortega, J.M.: 'Introduction to Parallel and Vector Solution of Linear Systems'. Plenum Press, New York and London, 1988.
Hillis, W.D., Steele, G.L.Jr.:'Data Parallel Algorithms', Communications of the ACM, vol 29, no 12, dez 1986, pg 1170-1183.
Ni, L.M., King, C.T.'On Partitioning and Mapping for Hypercube Computing'. International Journal of Parallel Programming, vol 17, no 5, pg 475-495, 1988.
Luenberger,D. : "Introdution to Linear and Nonlinear Programming". Reading , MA : Addison Wesley, 1973.
Kaszkurewies,E., Bhaya,A. e Siljak, D.D.: 'On the Convergence of Parallel Asynchronous Block-Iterative Computations'. Linear Algebra and Its Applications pg 139-160. Elsevier Science Publishing Co., Inc., 1990.
Decker, LC., Falcão, D.M., Kaszkurewicz, E.: 'Parallel Implementation of a Power System Simulation Methodology using the Conjugate Gradient Method'. IEEE-Transactions on Power System Computation Conference, pp 509-519, 1991.
Eager, D.L., Zahorjan, J., Lazowska, E.D.: 'Speedup Versus Efficiency in Parallel Systems'. IEEE-Transactions on Computers, vol 38, no 3, mar 1989.
Publicado
07/09/1993
Como Citar
CABRAL, Roberto G.; KASZKUREWICZ, Eugenius.
Implementação do Método dos Gradientes Conjugados em Multiprocessadores com Arquitetura Hipercúbica. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 5. , 1993, Florianópolis/SC.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1993
.
p. 412-425.
DOI: https://doi.org/10.5753/sbac-pad.1993.23048.
