Análise de Complexidade do Método de Eliminação Gaussiana em GPU Através da Ferramenta EMA
Resumo
Neste trabalho é apresentada uma análise empírica utilizando uma nova ferramenta chamada EMA (Empirical Analysis of Algorithms). O objetivo da EMA é fornecer análises empíricas sobre o uso de recursos (tempo e espaço) de um determinado algoritmo, através de execuções iterativas sobre a implementação fornecida como entrada. Como aplicação, consideramos a resolução de sistemas lineares através do algoritmo de Eliminação Gaussiana, dividido em duas etapas. Para a primeira etapa, apresentamos uma comparação com a literatura utilizando o paralelismo das GPUs (Unidade de Processamento Gráficos), enquanto que na segunda etapa propomos um algoritmo inovador que explora o paralelismo entre threads de um mesmo bloco, de forma a obter reduções no número de passos total. A análise de complexidade de cada etapa do método em sua versão sequencial e paralela são determinadas com os recursos oferecidos pela ferramenta EMA, e também o comportamento das operações de transferência de memória entre dispositivo e hospedeiro. Palavras-Chave: Análise Empírica de Algoritmos, Sistemas de Grande Porte, Eliminação Gaussiana, Computação GPU.Referências
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.
Publicado
05/10/2016
Como Citar
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: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (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.
