How to Cite
Abstract
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).
References
- 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.
Authors who post on ForScience agree to the following terms:
- The said work is of own authorship and has never been published or sent to another magazine, this magazine having the right of exclusivity on the edition and publication, under the license Creative Commons Attribution License 3.0 (CC-BY-NC) which allows anyone to share to adapt the work according to the following terms:
Atribuição — You must give the appropriate credit, provide a link to the license and indicate if the changes have been made. You must do so in any reasonable circumstance, but in no way do you suggest to the licensor to support you or your use.
Non-Commercial — You may not use the material for commercial purposes.
- If plagiarism has been proven in any published work, this Journal is free of any responsibility, and its author (s) shall bear the penalties provided by law.
- Authors are authorized to take additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
- Authors are allowed and encouraged to publish and distribute their work online (eg in institutional repositories or on their personal page), as this can generate productive changes, as well as increase the impact and citation of the published work. However, it should be noted that once approved by the evaluators, the manuscript can not be changed. If the author wishes to do so, he should restart the submission process.