o bovino

Computer on the Beach 2013 - Artigos Completos

79

Análise Comparativa de Algoritmos NP-Completo
Executados em CPU E GPU Utilizando CUDA
Elcio Arthur Cardoso, Rafael de Santiago

Curso de Ciência da Computação – Universidade do Vale do Itajaí (UNIVALI)
Caixa Postal 360 – CEP 88302-202 – Itajaí – SC – Brasil
{elcio_arthur, rsantiago}@univali.br

Abstract. Research for greater computing power, always present in the computation that led to the creation of parallel architectures consisting of thousands of processing units, as occurs in the architectures of GPUs. In this context, this work presents a search for using the computational power of
GPUs through CUDA architecture, aiming to solve computational problems found in the class NP-Complete, those that can take years to resolve. This paper shows three strategies to approach with their limitations and benefits.
With these results, there is evidence that the architecture is efficient in solving these problems.
Keywords: CUDA. NP-Complete. Parallel Computing.
Resumo. A busca por maior poder computacional, sempre esteve presente na computação o que levou à criação de arquiteturas paralelas compostas por milhares de unidades de processamento, como ocorre nas arquiteturas das
GPUs. Neste contexto, apresenta-se uma pesquisa para utilizar o poder computacional das GPUs, através da arquitetura CUDA, buscando resolver problemas computacionais, encontrados na classe NP-Completo, estes que podem levar anos para serem resolvidos. São apresentadas três estratégias de abordagem com suas limitações e benefícios. Com os resultados obtidos, há evidencias que a arquitetura é eficiente na solução destes problemas.
Palavras-Chave: CUDA. NP-Completo. Computação Paralela.

1. Introdução
Segundo Tanembaum (2003), há uma demanda por computadores cada vez mais rápidos, demanda esta principalmente suprida devido a incrementos na velocidade de operação dos processadores, porém estas evoluções chegaram ao seu