Análise de Complexidade do Método de Eliminação Gaussiana em GPU Através da Ferramenta EMA
Abstract
In this work, it is presented an empirical analysis using a novel tool called EMA (Empirical Analysis of Algorithms). The purpose of EMA is to provide empirical analysis regarding the computional resources (time and space) of a specific algorithm, by means of iterative executions over an implementation given as input. As an application, we consider the resolution of linear systems with the Gaussian Elimination algorithm, divided in two phases. In the first phase, we perform a comparison with the literature exploring the paralelism of GPUs (Graphics Processing Units), and in phase two, we propose a novel algorithm that explores the parallelism between threads of a same block, in order to obtain a reduction in the total number of steps. The complexity analysis of each phase of the method in its parallel and sequential versions are determined by the EMA tool, also the behavior analysis of the memory transfers between device and host. Keywords: Empirical Analysis of Algorithms, Large Systems, Gaussian Elimination, GPU Computing.References
Buluç, A., Gilbert, J. R., and Budak, C. (2008). Gaussian elimination based algorithms on the gpu. Technical report, University of California.
Che, S., Li, J., Sheaffer, J. W., Skadron, K., and Lach, J. (2008). Accelerating computeintensive applications with gpus and fpgas. In Symposium on Application Specific Processors (SASP) 2008, pages 101–107.
de Souza, R. M. (2015). Análise Empírica do Algoritmo Shellsort. TCC – Trabalho de Conclusão de Curso, Universidade do Estado do Rio de Janeiro.
Golub, G. H. and van Loan, C. F. (1989). Matrix Computations. Number 3 in Johns Hopkins Series in the Mathematical Sciences. The Johns Hopkins University Press.
Gonçalves, N., Costa, C., Araújo, J., Costa, J., and Panetta, J. (2015). Comparação e análise de desempenho de aceleradores grácos no processamento de matrizes. In Anais do XIV Workshop em Desempenho de Sistemas Computacionais e de Comunicação, pages 1–13.
Kirk, D. B. and Wen-mei, W. H. (2012). Programming massively parallel processors: a hands-on approach. Newnes.
Lehmann, E. L. and Casella, G. (1991). Theory of point estimation. Wadsworth & Brooks/Cole Advanced Books & Software.
Marrakchi, M. and Robert, Y. (1989). Optimal algorithms for gaussian elimination on an mimd computer. Parallel Computing, 12(2):183 – 194.
Oliveira, F. S. (2016). EMA - WebPage. http://fabianooliveira.ime.uerj.br/ema. [ Última vez acessado: 07 de Junho de 2016].
Robert, Y. and Trystram, D. (1989). Optimal scheduling algorithms for parallel gaussian elimination. Theoretical Computer Science, 64(2):159 – 173.
Roger, T. (1969-1970). Algébre Linéaire, C3 Analyse Numérique. Technical report, University of California.
Che, S., Li, J., Sheaffer, J. W., Skadron, K., and Lach, J. (2008). Accelerating computeintensive applications with gpus and fpgas. In Symposium on Application Specific Processors (SASP) 2008, pages 101–107.
de Souza, R. M. (2015). Análise Empírica do Algoritmo Shellsort. TCC – Trabalho de Conclusão de Curso, Universidade do Estado do Rio de Janeiro.
Golub, G. H. and van Loan, C. F. (1989). Matrix Computations. Number 3 in Johns Hopkins Series in the Mathematical Sciences. The Johns Hopkins University Press.
Gonçalves, N., Costa, C., Araújo, J., Costa, J., and Panetta, J. (2015). Comparação e análise de desempenho de aceleradores grácos no processamento de matrizes. In Anais do XIV Workshop em Desempenho de Sistemas Computacionais e de Comunicação, pages 1–13.
Kirk, D. B. and Wen-mei, W. H. (2012). Programming massively parallel processors: a hands-on approach. Newnes.
Lehmann, E. L. and Casella, G. (1991). Theory of point estimation. Wadsworth & Brooks/Cole Advanced Books & Software.
Marrakchi, M. and Robert, Y. (1989). Optimal algorithms for gaussian elimination on an mimd computer. Parallel Computing, 12(2):183 – 194.
Oliveira, F. S. (2016). EMA - WebPage. http://fabianooliveira.ime.uerj.br/ema. [ Última vez acessado: 07 de Junho de 2016].
Robert, Y. and Trystram, D. (1989). Optimal scheduling algorithms for parallel gaussian elimination. Theoretical Computer Science, 64(2):159 – 173.
Roger, T. (1969-1970). Algébre Linéaire, C3 Analyse Numérique. Technical report, University of California.
Published
2016-10-05
How to Cite
ZUDIO, Anderson; DE SOUZA, Raquel; COELHO, Igor; FARIA, Cristiane; OLIVEIRA, Fabiano.
Análise de Complexidade do Método de Eliminação Gaussiana em GPU Através da Ferramenta EMA. In: SYMPOSIUM ON HIGH PERFORMANCE COMPUTING SYSTEMS (SSCAD), 17. , 2016, Aracajú.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 203-214.
DOI: https://doi.org/10.5753/wscad.2016.14260.
