Comparando diferentes implementações paralelas de algoritmos genéticos em GPUs com CUDA

Abstract

O advento das GPUs para computação de propósito geral ampliou as possibilidades de utilização dessas arquiteturas para além da aceleração de aplicações gráficas. O campo de estudo de algoritmos de otimização tem especial interesse nessas arquiteturas, pois a aceleração desses algoritmos pode impactar significativamente na qualidade das soluções obtidas. Desde o início da última década, uma classe das técnicas de otimização que vem sendo adaptada com sucesso em GPUs é a dos Algoritmos Genéticos. Este trabalho apresenta duas formas distintas de se paralelizar algoritmos genéticos em GPUs com CUDA. Uma utiliza a memória compartilhada da GPU para obter cooperação na computação paralela enquanto a outra utiliza as funções de Warp-Shuffle da CUDA. Buscando avaliar cada uma dessas implementações em termos de desempenho, são realizados diversos experimentos variando os parâmetros de execução da aplicação (i.e granularidade do paralelismo, tamanho da população e número de dimensões do problema).

The advent of GPUs for general-purpose computing has broadened the possibilities of the use of these architectures beyond the traditional acceleration of graphics-based applications. The research field of optimization algorithms has a special interest in these architectures because the acceleration of these algorithms may improve significantly the quality of the obtained solutions. Since the beginning of the last decade, one of the classes of optimization techniques that have been successfully adapted in the GPUs is that of Genetic Algorithms. This work presents two manners of implementing genetic algorithms in GPU using CUDA that exploit different levels of parallelism. In one of them, the cooperation of the parallel computation is achieved through the shared memory of the GPU, whereas the other one uses the CUDA Warp Shuffle functions. To evaluate the performance of these implementations, different experiments that change the execution parameters of the application (i.e the granularity, the population size, and the number of dimensions of the problem) are made.