Resumen de Algoritmos de Optimización sobre Unidades de Proceso Gráfico
En la actualidad, han emergido nuevas plataformas de cómputo paralelo tales como las Unidades de Procesamiento Gráfico (GPUs, por sus siglas en inglés). Las GPUs están especialmente diseñadas para proporcionar un entorno donde es posible explotar su modelo de paralelismo y desarrollar diferentes propuestas algorítmicas paralelas para este tipo de plataformas. En este sentido, las GPUs se han convertido en una alternativa interesante de cómputo a las tradicionales CPU dada su capacidad para realizar cálculos en paralelo y también diferenciadas de otras formas de usar múltiples procesadores, como los clusters de máquinas, entre otros. Esto ha permitido a una computadora de escritorio o portátil aumentar su capacidad de cómputo debido a las mejoras de las tarjetas a nivel hardware y software, lo que las convierte en una opción para realizar cómputo de alto rendimiento (HPC, por sus siglas en inglés). El desarrollo de estrategias metaheurísticas paralelas en GPU para la resolución de problemas complejos se presenta como una línea de investigación muy importante en la actualidad, ya que por una parte, las citadas estrategias (potencialmente no exactas) proporcionan una solución de alta calidad en un tiempo razonable, mientras que por otro, es bien sabido que tanto la eficiencia de dichos algoritmos metaheurísticos como los resultados que éstos obtienen mejoran de manera significativa cuando se aplican estrategias de paralelismo. El contenido de este trabajo se centra en evaluar técnicas metaheurísticas en arquitecturas GPU buscando la mejor técnica que se adapte a la GPU. De la misma forma, se busca diseñar y analizar nuevos modelos que puedan proveer: sencillez en la implementación y potencia computacional, equilibrio necesario entre la eficiencia y la eficacia suficiente para la supervivencia en diferentes problemas. Todo esto por varias razones: en primer lugar, las ventajas de estas nuevas tecnologías ofrece la posibilidad de cubrir la demanda de eficiencia tanto en tiempo real como numérica, lo cual nos lleva a la segunda razón. Las metaheurísticas son técnicas ampliamente aceptadas y utilizadas en diferentes áreas de aplicación. Cabe la posibilidad entonces de brindar al investigador una solución de cierta calidad en un breve periodo de tiempo: un compromiso entre calidad de la solución y la rapidez. Finalmente, muchas de las contribuciones que se materialicen pueden ser extensibles a otras técnicas metaheurísticas o ser usadas como base para otros modelos algorítmicos en futuros estudios posteriores a esta tesis. Esta tesis presenta un conjunto de consideraciones iniciales sobre los algoritmos Genéticos Celulares (cGAs). A continuación introducimos la adaptación de los principales procesos de un cGA a la GPU. Esto nos permitirá describir el alcance de la propuesta y exponer los beneficios y problemas que cabe esperar. Posteriormente, se muestra una aproximación cGA mediante una arquitectura de múltiples GPUs. Se indican las diferencias más importantes que se pueden encontrar con respecto a la primera implementación presentada. Posteriormente, se muestra un estudio sobre una aproximación original de búsqueda diseñada especialmente para funcionar sobre una plataforma GPU basada en las características de la Computación Sistólica. Luego, se provee una descripción de las diferentes mejoras a partir del modelo canónico. Inmediatamente, se discuten las ventajas e inconvenientes. La razón de este análisis es profundizar y conocer mejor el método de búsqueda. A partir del algoritmo anteriormente propuesto se presenta un nuevo modelo que utiliza la idea de paralelismo híbrido como concepto de inicio. Se discute el diseño de una técnica paralela híbrida la cual utiliza algoritmos capaces de sacar provecho de las cualidades intrínsecas de cada arquitectura (CPU y GPU). Se abordan detalles sobre la mejora de la búsqueda a través de la cooperación entre los algoritmos. Posteriormente, se analizan consideraciones importantes sobre la implementación. Todos los nuevos algoritmos propuestos en este trabajo son comparados con diferentes algoritmos canónicos y con aquellos pertenecientes al estado del arte para una plétora de problemas complejos de optimización que pertenecen a los campos de optimización combinatoria y continua. Las conclusiones alcanzadas en cuanto a aceleración y precisión en el análisis reflejan las elevadas prestaciones que las tarjetas gráficas programables ofrecen en el ámbito de la optimización metaheurística.
