Paralelização e comparação de métodos iterativos na solução de sistemas lineares grandes e esparsos

Lauro Cássio Martins de Paula

Resumo - visualizações: 4638


Apresenta-se neste trabalho uma comparação de desempenho computacional entre métodos iterativos utilizados para solução de sistemas lineares. O objetivo é mostrar que a utilização de processamento paralelo fornecido por uma Graphics Processing Unit (GPU) pode ser viável, por viabilizar a solução rápida de sistemas de equações lineares, para que sistemas grandes e esparsos possam ser solucionados em um espaço curto de tempo. Para a validação do trabalho, utilizou-se uma GPU, por meio da arquitetura Compute Unified Device Architecture (CUDA), e comparou-se o desempenho computacional dos métodos iterativos de Jacobi, Gauss-Seidel, BiCGStab e BiCGStab(2) paralelizado na solução de sistemas lineares de tamanhos variados. Foi possível observar uma aceleração significativa nos testes com o método paralelizado, que se acentua consideravelmente na medida em que os sistemas aumentam. Os resultados mostraram que a aplicação de processamento paralelo em um método robusto e eficiente, tal como o BiCGStab(2), se torna muitas vezes indispensável, para que simulações sejam realizadas com qualidade e em tempo não proibitivo.

Palavras-chave: CUDA. GPU. BiCGStab(2).

Parallelization and comparison of interative methods in solving large and sparse linear systems

Abstract

This paper presents a computational performance comparison between some iterative methods used for linear systems solution. The goal is to show that the use of parallel processing provided by a Graphics Processing Unit (GPU) may be more feasible, for making possible the fast solution of linear equations systems in order that complex and sparse problems can be solved in a short time. To validate the paper a GPU through the NVIDIA's Compute Unified Device Architecture (CUDA) was employed and the computational performance was compared with Jacobi, Gauss-Seidel, BiCGStab iterative methods and BiCGStab(2) parallelized in the solution of linear systems of varying sizes. There was a significant acceleration in tests with the parallelized code, which increases considerably as much as systems increase. The results showed that the application of parallel processing in a robust and efficient method, as BiCGStab(2), it is often necessary for the simulations be performed with quality and in not prohibitive time.

Keywords: CUDA. GPU. BiCGStab(2).


Palavras-chave


CUDA; GPU; BiCGStab(2)

Texto completo:

PDF

Referências


- ANTON, H; BUSBY, R. C. Álgebra linear contemporânea. Porto Alegre: Bookman, 2006.

- BOWINS, E. C. A comparison of sequential and GPU implementations of iterative methods to compute reachability probabilities. In: WORKSHOP ON GRAPH INSPECTION AND TRAVERSAL ENGINEERING, I., 2012, Tallim. Proceedings... Tallinn [s.n.], 2012. p. 20-34.

- CLAUDIO, D. M; MARINS, J. M. Cálculo numérico computacional. São Paulo: Atlas, 1989.

- FRANCO, N. B. Cálculo numérico. São Paulo: Pearson Prentice Hall, 2006.

- GAIOSO, R. R.; PAULA, L. C. M. Paralelização do algoritmo Floyd-Warshall usando GPU. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS. XIV., 2013. Anais... [S.l.: s.n.], 2013.

- JUDICE, J. J. et. al. Sistemas de equações lineares. Coimbra: Departamento de Matemática da Universidade de Coimbra, 1996.

- PAULA, L. C. M. Paralelização e comparação de métodos iterativos na solução de sistemas lineares grandes e esparsos

- KINCAID, D.; WARD, C. Mathematics of scientific computing. [S.l.]: Pacific Grove, 1996.

- NVIDIA CUDA. NVIDIA CUDA C Programming best practices guide. [S.l.]: NVIDIA Corporation, 2009.

- NVIDIA CUDA. NVIDIA CUDA C Programming Guide 4.2. [S.l.]: NVIDIA Corporation, 2012.

- PAULA, L. C. M et al. Aplicação de processamento paralelo em método iterativo para solução de sistemas lineares. In: ENCONTRO ANUAL DE COMPUTAÇÃO (ENACOMP), X., 2013a, Catalão. Anais... Catalão: UFG, 2013a. p. 129-136.

- PAULA, L. C. M. et al. Partial parallelization of the successive projections algorithm using compute unified device architecture. In: INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS (PDPTA). 19., 2013b, Las Vegas. Proceedings... Las Vegas: [s.n.], 2013b.

- RODRIGUEZ, N. R. et al. Resolução de sistemas de equações lineares de grande porte em clusters multi-GPU utilizando o método do gradiente conjugado em OpenCL. Rio de Janeiro: Departamento de Informática da PUC-Rio, 2013.

- TSUCHIYAMA, R. et. al. C. The openCL programming book. [S.l.] Fixstars, 2010.

- VERSTEEG, H. K; MALALASEKERA, W. An introduction to computational fluid dynamics: the finite volume method. Londres: Longman Scientific & Technical, 1995.

- VORST, H. A. V. Bi-CGStab: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM Journal of Scientific and Statistical Computing, v. 13, p. 631-644, 1992.

- VORST, H. A. V; SLEIJPEN, G. L. G. Hybrid Bi-Conjugate Gradient Methods for CFD Problems. In: HAFEZ, M.; OSHIMA K. Computational fluid dynamics REVIEW 1995. Chicester: Wiley, 1995. p 457-476.




DOI: http://dx.doi.org/10.29069/forscience.2013v1n1.e18

Apontamentos

  • Não há apontamentos.


Indexada em:

                    

          

ISSN 2318-6356

Licença Creative Commons
ForScience: Revista Científica do IFMG   http://formiga.ifmg.edu.br/forscience é licenciado sob uma Licença Creative Commons Atribuição-NãoComercial 3.0 Não Adaptada.

SalvarSalvarSalvarSalvar