Implementación de Algoritmos Genéticos sobre la plataforma de desarrollo paralelo CUDA Víctor Manuel Abascal Pelayo Pablo Feijoo Ugalde Dirigido por: Prof. José Ignacio Hidalgo Pérez Dpto. Arquitectura de Computadores y Automática Facultad de Informática Universidad Complutense de Madrid Asignatura de Sistemas Informáticos. Curso 2008/2009 Proyecto: Implementación de Algoritmos Genéticos sobre la plataforma de desarrollo paralelo CUDA Dirigido por el profesor D. José Ignacio Hidalgo Pérez Autorizamos a la Universidad Complutense de Madrid a difundir y utilizar con fines académicos, no comerciales y mencionando expresamente a sus autores, tanto la propia memoria, como el código, la documentación y/o el prototipo desarrollado. Víctor Manuel Abascal Pelayo Pablo Feijoo Ugalde Madrid, 1 de Septiembre de 2009. Sistemas Informáticos UCM Curso 2008/2009 Prof. José Ignacio Hidalgo Pérez Víctor Manuel Abascal Pelayo, Pablo Feijoo Ugalde Palabras Clave Algoritmo CUDA EMMRS Genético Paralelo Schwefel Viajante de comercio Key Words Algorithm CUDA EMMRS Genetic Parallel Schwefel TSP Implementación de Algoritmos Genéticos sobre la plataforma de desarrollo paralelo CUDA - 1 - Sistemas Informáticos UCM Curso 2008/2009 Prof. José Ignacio Hidalgo Pérez Víctor Manuel Abascal Pelayo, Pablo Feijoo Ugalde Resumen Español Los algoritmos genéticos (AGs) son técnicas de búsqueda y optimización inspiradas en la naturaleza que utilizan propiedades como la herencia, mutación, selección y cruce. Una de las cualidades principales de los algoritmos genéticos es su grado de paralelismo implícito, ya que se trabaja con un conjunto de soluciones de forma simultánea. Al igual que en la naturaleza, la evolución de los individuos no depende únicamente de ellos, si no también de la población a la que pertenece. Por otra parte, actualmente casi todos los computadores personales cuentan con una tarjeta gráfica destinada a la ejecución de aplicaciones gráficas (videojuegos). En la mayoría de las ocasiones estas tarjetas aparecen inactivas y se está desperdiciando su capacidad para realizar cálculos paralelos. Nuestro trabajo está destinado a utilizar ese hardware desaprovechado para implementar un conjunto de algoritmos que solucionen el problema del Viajante de Comercio y la función de Schwefel. Los principales objetivos de nuestro trabajo son estudiar la sobrecarga de comunicaciones en la comunicación CPU-GPU y evaluar distintos operadores genéticos utilizando las ventajas de programación que proporciona CUDA, el nuevo lenguaje de programación paralelo de Nvidia. English The genetic algorithms (GAs) are search and improvement technique inspired by evolutionary biology such as inheritance, mutation, selection and crossover. One of the most important features of the genetic algorithms is their high degree to be parallelised, because they use a group of solutions at the same time. As in the natural world, individual’s evolution depends not only the character, but also the environment. Nowadays, almost all the medium PC’s have a graphic card used to execute graphic applications (videogames). The most of the time, we are wasting all this capacity of parallel calculation. Our work is destined to use this wasted hardware to implement GA that solvent the Traveling Salesman Problem (TSP) and the Schwefel function as well. The project’s goals are to study the communication overload in the transfers between CPU and GPU and to evaluate different genetic operators using the CUDA’s advantages, the new language for parallel programming of NVIDIA Implementación de Algoritmos Genéticos sobre la plataforma de desarrollo paralelo CUDA - 2 - Sistemas Informáticos UCM Curso 2008/2009 Prof. José Ignacio Hidalgo Pérez Víctor Manuel Abascal Pelayo, Pablo Feijoo Ugalde Agradecimientos Gracias a José Ignacio Hidalgo Pérez por su apoyo, guía y paciencia en la realización de este trabajo. Implementación de Algoritmos Genéticos sobre la plataforma de desarrollo paralelo CUDA - 3 - Sistemas Informáticos UCM Curso 2008/2009 Prof. José Ignacio Hidalgo Pérez Víctor Manuel Abascal Pelayo, Pablo Feijoo Ugalde Índice 1. Introducción 7 1.1 Objetivos 7 1.2 Motivación 8 2. Algoritmos Genéticos 12 2.1 Introducción 12 2.2 Marco de Aplicación 15 3 Algoritmo Genético Simple 17 3.1 Población Inicial 18 3.2 Función de fitness 18 3.3 Métodos de Selección 20 3.4 Cruce y Mutación 23 3.5 Reducción 27 3.6 Ventajas y Desventajas de los AG’s 28 3.6.1 Puntos Fuertes 28 3.6.2 Limitaciones 31 4 Algoritmos Híbridos o Meméticos 35 4.1 EMMRS 35 Implementación de Algoritmos Genéticos sobre la plataforma de desarrollo paralelo CUDA - 4 - Sistemas Informáticos UCM Curso 2008/2009 Prof. José Ignacio Hidalgo Pérez Víctor Manuel Abascal Pelayo, Pablo Feijoo Ugalde 4.2 Hill Climbing 36 5 Compute Unified Device Architecture 38 5.1 Historia y motivación 39 5.2 GPU vs. CPU 40 5.3 Características Principales 43 5.3.1 Abstracción 43 5.3.2 Gestión de los Hilos 44 5.4 Modelos de compilación y ejecución 48 5.4.1 Compilación 48 5.4.2 Ejecución 51 5.5 Glosario 53 6. Problemas Implementados 55 6.1. Problemas Continuos. Funciones multimodales 56 6.2. Problemas discretos NP-completos 57 7. Implementación y desarrollo 58 7.1. Detalles Técnicos 58 7.1.1. NVIDIA GeForce 8800 GTX 59 7.2 Implementación 60 7.2.1. Representación de los datos, codificación y función de ajuste 61 7.2.2. Estructura 7.2.3. Operadores Evolutivos 64 Implementación de Algoritmos Genéticos sobre la plataforma de desarrollo paralelo CUDA - 5 - Sistemas Informáticos UCM Curso 2008/2009 Prof. José Ignacio Hidalgo Pérez Víctor Manuel Abascal Pelayo, Pablo Feijoo Ugalde 7.2.4. Problemas durante el desarrollo de la implementación 67 8. Gráficas de rendimiento y comparativas 70 8.1 Resultados de calidad: Función de Schwefel 72 8.2 Speed-Up: Función de Schwefel 76 8.3 Resultados de calidad: TSP 78 8.4 Speed-Up: TSP 96 8.5 Conclusiones y futuras líneas de trabajo 105 9. Bibliografía y Referencias 108 10. Apéndice A: TSP gr48 110 11. Apéndice B: Código función Schwefel 111 12. Apéndice C: Código TSP 122 Implementación de Algoritmos Genéticos sobre la plataforma de desarrollo paralelo CUDA - 6 - Sistemas Informáticos UCM Curso 2008/2009 Prof. José Ignacio Hidalgo Pérez Víctor Manuel Abascal Pelayo, Pablo Feijoo Ugalde Implementación de Algoritmos Genéticos sobre la plataforma de desarrollo paralelo CUDA - 7 - Sistemas Informáticos UCM Curso 2008/2009 Prof. José Ignacio Hidalgo Pérez Víctor Manuel Abascal Pelayo, Pablo Feijoo Ugalde 1 Introducción 1.1 Objetivos La optimización de recursos a través de su máxima utilización, es un tema de permanente actualidad, no sólo en el campo de la informática, si no también en cualquier proyecto de ingeniería. Las numerosas líneas de investigación que hay referentes a la máxima utilización de los recursos hardware muestran también su capital importancia. Desde los continuos avances en el campo del diseño de computadores que minimicen los tiempos de espera hasta su utilización masiva en proyectos como SETI@home1, la obsesión por la máxima eficiencia es una constante en el mundo de la computación. Con la nueva generación de microprocesadores de sobremesa (multinúcleo) estamos en un redescubrimiento de los paradigmas paralelos de programación (directivas y paso de mensajes) y de las tecnologías que introdujeron a principios de los 90, compañías como MassPar2 y Thinking Machines3, y que derivan en el nuevo objetivo de la industria tecnológica: paralelizar. La misma tendencia que ahora están siguiendo los procesadores, ya había sido iniciada anteriormente por las tarjetas gráficas, cuya capacidad de cálculo venía siendo superior en varios órdenes de magnitud a la de los procesadores desde mediados de 2003. Obviamente este tipo de dispositivos tiene limitado su rango de acción. Sin embargo con la reciente introducción de la plataforma de desarrollo CUDA de la empresa norteamericana Nvidia4, se pone a disposición de los usuarios un software para Implementación de Algoritmos Genéticos sobre la plataforma de desarrollo paralelo CUDA - 8 -