Paralelización de algoritmos genéticos utilizando unidades de procesamiento gráficas

Abstract

Cuando se intenta resolver un problema a través de un algoritmo computacional, parte del diseño del mismo consiste en definir no solo cómo se va a resolver, sino también administrar de una manera relativamente eficiente el tiempo que demandará resolver el mismo. Si el espacio de búsqueda de soluciones es lo suficientemente grande, resulta favorable que sea resuelto a través de un algoritmo evolutivo, más particularmente, un algoritmo genético. Ahora bien, el algoritmo puede ser ejecutado sobre una CPU (Unidad Central de Procesamiento) de manera secuencial, como suele suceder, tradicionalmente, en términos de programación. Pero también existe la posibilidad de que sea diseñado para correr sobre una Unidad de Procesamiento Gráfico (GPU). Mediante esta tesina, se propone analizar un problema en particular: el problema de la mochila (knapsack problem, en inglés), programado para correr en estas dos diferentes unidades de procesamiento, CPU y GPU, permitiendo observar cuál es la diferencia de rendimiento en tiempos de ejecución, así como también en la calidad de soluciones. Para ello, debe tenerse en cuenta que, en virtud de elaborar esta comparativa, es primordial tener en cuenta las especificaciones del hardware con el que se dispone.

Solving problems through computational algorithms implies that design is not the only thing to be addressed, the processing time needs to be taken into account and be managed efficiently. If the search space is big enough, it's suitable to solve them using evolutive algorithms, in particular, genetic algorithms. These algorithms can be executed on a CPU (Central Processing Unit) in a sequential mode, commonly used by programmers. However, there is also another possibility: design them to run over Graphics Processing Units (GPU). Through this work, a commonly-known problem will be analyzed: the knapsack problem. Two genetic algorithms are going to be programmed and executed over two different processing units, CPU and GPU, with the proposal to analyze the difference in terms of processing time between them, as well as the quality of its solutions. To achieve this comparison, it is essential to consider all the hardware specifications available.