Optimización sistólica sobre GPUs

Abstract

En este trabajo se estudia una nueva aproximación algorítmica basada en un modelo de procesamiento paralelo conocido como computación sistólica. Este algoritmo se ejecuta sobre una Unidad de Procesamiento Gráfico empelando CUDA (Compute Unified Device Architecture). El algoritmo se compone de una matriz de celdas, donde cada una de ellas trabaja sobre una solución, realizando operaciones que la modifican para luego moverla a la celda contigua y repetir el proceso. Hemos evaluado el comportamiento del algoritmo sobre diferentes instancias del problema de la mochila multidimensional. La evaluación experimental sobre las instancias seleccionadas demuestra la eficiencia y competitividad de nuestra aproximación.