Análise de Complexidade do Método de Eliminação Gaussiana em GPU Através da Ferramenta EMA

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.