Resumen:
|
[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 ...[+]
[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ó ...[+]
[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 ...[+]
[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.).
[-]
|