Solución en paralelo del problema de la mochila

Abstract

[ES] El problema de la mochila es un problema NP-Completo bien conocido, que, en sus diferentes variantes, tiene un gran interés, tanto teórico como práctico, y ha sido sujeto de un amplio número de estudios. Si bien la formulación del problema es sencilla, su resolución es más compleja. Dado que el problema de la mochila es un problema NPCompleto, aún con los mejores algoritmos que existen actualmente la tarea de resolver instancias del problema grandes requeriría mucho tiempo de cómputo, por lo que estos algoritmos se suelen paralelizar para reducir el tiempo que necesitan para obtener una solución. En este trabajo se ha implementado una versión paralela del algoritmo de las dos listas desarrollado por Horowitz Y Sahni, utilizando un modelo de programación híbrido MPI/OpenMP. Para ello primero se ha implementado la versión secuencial, que luego se ha utilizado para a) implementar la versión paralela en base a ella y b) ejecutar pruebas y comparar la ganancia de rendimiento obtenida al paralelizar el algoritmo. Estas implementaciones se han realizado con el lenguaje de programación C. La implementación paralela se ha realizacion con la intención que sea ejecutada en un clúster actual, con varios nodos, cada uno teniendo disponible varios núcleos. Para ello se ha realizado un estudio del problema de la mochila, de donde proviene y su importancia histórica, así y como se presentan las principales instancias y variaciones del problema, junto con otros problemas importantes que son derivados de, o pueden reducirse al problema de la mochila. También se presentan las dos librerías de paralelización a utilizar, MPI y OpenMP, describiendo sus características principales y los mecanismos de paralelización que utilizan, además de enumerar las principales utilidades que ofrecen para ese propósito (funciones, directivas, etc).

[CA] El problema de la motxilla és un problema NP-Complet ben conegut, que, en les seues diferents variants, té un gran interés, tant teòric com pràctic, i ha sigut subjecte d’un ampli nombre d’estudis. Si bé la formulació del problema és senzilla, la seua resolució és més complexa. Atés que el problema de la motxilla és un problema NP-Complet, encara amb els millors algoritmes que existixen actualment la tasca de resoldre instàncies grans del problema requeriria molt de temps de còmput, raó per la qual aquestos algoritmes es solen paralelizar per a reduir el temps que necessiten per a obtindre una solució. En este treball s’ha implementat una versió paral·lela de l’algoritme de les dos llistes desenvolupat per Horowitz I Sahni, utilitzant un model de programació híbrid MPI/OpenMP. Per això primer s’ha implementat la versió seqüencial, que després s’ha utilitzat per a) implementar la versió paral·lela basant-se en ella i b) executar proves i comparar el increment de rendiment obtingut al paralelizar l’algoritme. Estes implementacions s’han realitzat amb el llenguatge de programació C. La implementació paral·lela s’ha realitzat amb l’intenció que siga executada en un cluster actual, amb diversos nodes, aquestos tenint disponible diversos nuclis. Per a aquesta tarea s’ha realitzat un estudi del problema de la motxilla, d’on prové i la seua importància històrica, així com es presenten les principals instàncies i variacions del problema, junt amb altres problemes importants que són derivats de, o poden reduirse al problema de la motxilla. També es presenten les dos llibreries de paralelización a utilitzar, MPI i OpenMP, descrivint les seues característiques principals i els mecanismes de paralelización que utilitzen, a més d’enumerar les principals utilitats que oferixen per a eixe propòsit (funcions, directives, etc).

[EN] The knapsack problem is a well-known NP-Complete problem, which, in its different variants, has a great interest, both theoretical and practical, and has been the subject of a large number of studies. Although the formulation of the problem is simple, its resolution is more complex. Since the knapsack problem is a NP-Complete problem, even with the best algorithms that currently exist, the task of solving large instances of the problem would require a lot of computing time, so these algorithms are often parallelized to reduce the time they need to get a solution. In this work a parallel version of the two lists algorithm developed by Horowitz and Sahni has been implemented, using an MPI/OpenMP hybrid programming model. To do this, the sequential version has been implemented, which has been used to a) implement the parallel version on top of it and b) run tests and compare the performance gained by parallelizing the algorithm. These implementations have been done with the programming language C. The parallel implementation has been developed with the intention of executing it in a modern cluster, with several nodes, each having several cores available. For this, the knapsack problem has been studied, stating its historical importance, as well its main instances and variations of the problem are presented, together with other important problems that are derived, or can be reduced to, the knapsack problem. It is also presented the two parallelization libraries to be used, MPI and OpenMP, describing their main characteristics and the parallelization mechanisms they use, as well as listing the main utilities they offer for that purpose (functions, directives, etc.).