Análise de Complexidade do Método de Eliminação Gaussiana em GPU Através da Ferramenta EMA - Zudio, Anderson; de Souza, Raquel; Coelho, Igor; Faria, Cristiane; Oliveira, Fabiano (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD); 2016: Anais do XVII Simpósio em Sistemas Computacionais de Alto DesempenhoDO - 10.5753/wscad.2016.14260, 2016)
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áﬁcos), 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.