Framework para el desarrollo de algoritmos genéticos en GPU.

Abstract

Para la resolución de problemas de optimización del tipo NP-difícil, no es posible utilizar métodos exactos debido al excesivo tiempo de cómputo que implican. Para este tipo de problemas, las metaheurísticas han demostrado ser una buena herramienta, aunque en problemas de gran dimensionalidad, pueden incrementar el tiempo de cómputo, al punto de volver también impracticable esta opción. Por esto, y por las posibilidades que brindan las nuevas arquitecturas de hardware, una buena alternativa es la aplicación de estrategias de computación de alto desempeño (HPC). En los últimos años, las tarjetas gráficas (co-procesador gráfico, GPU) han experimentado una evolución vertiginosa. Este hecho ha motivado que muchos científicos busquen la utilización de las GPUs, para atacar problemas de propósito general (GPGPU). Sumado a esto, la arquitectura Fermi y la plataforma CUDA han evolucionado ofreciendo extensiones en C y C++, facilitando la programación sobre las GPUs. En este proyecto se realiza el diseño, la implementación y la documentación de un framework para la implementación de algoritmos genéticos sobre arquitecturas híbridas que incluyen GPUs. En particular, se logró un prototipo avanzado de un framework para que pueda ser utilizado por el resto de la comunidad académica/científica. Este abarca diversos tipos de representación y sus correspondientes operadores evolutivos. Los resultados obtenidos sobre casos de prueba específicos para cada tipo de representación denotan speedups de hasta 6.70x para representación binaria, 11.68x para representación entera y 35.10x para representación real. Los resultados obtenidos en representación de permutación no fueron buenos en cuanto al tiempo de ejecución, a pesar de haber realizado diversas implementaciones para tratar de mejorar la eficiencia de los operadores evolutivos y de la función fitness.