- -

Solución en paralelo del problema de la mochila

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

Solución en paralelo del problema de la mochila

Show simple item record

Files in this item

dc.contributor.advisor Alonso Jordá, Pedro es_ES
dc.contributor.author Verdeguer López, David es_ES
dc.date.accessioned 2017-09-13T11:35:45Z
dc.date.available 2017-09-13T11:35:45Z
dc.date.created 2017-07-17
dc.date.issued 2017-09-13 es_ES
dc.identifier.uri http://hdl.handle.net/10251/87210
dc.description.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). es_ES
dc.description.abstract [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). es_ES
dc.description.abstract [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.). es_ES
dc.format.extent 42 es_ES
dc.language Español es_ES
dc.publisher Universitat Politècnica de València es_ES
dc.rights Reconocimiento - No comercial - Sin obra derivada (by-nc-nd) es_ES
dc.subject GPUs es_ES
dc.subject Mochila es_ES
dc.subject Paralelo es_ES
dc.subject OpenMP es_ES
dc.subject Mpi es_ES
dc.subject Motxilla es_ES
dc.subject Knapsack es_ES
dc.subject Parallel es_ES
dc.subject.classification LENGUAJES Y SISTEMAS INFORMATICOS es_ES
dc.subject.classification CIENCIAS DE LA COMPUTACION E INTELIGENCIA ARTIFICIAL es_ES
dc.subject.other Grado en Ingeniería Informática-Grau en Enginyeria Informàtica es_ES
dc.title Solución en paralelo del problema de la mochila es_ES
dc.type Proyecto/Trabajo fin de carrera/grado es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Escola Tècnica Superior d'Enginyeria Informàtica es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation Verdeguer López, D. (2017). Solución en paralelo del problema de la mochila. http://hdl.handle.net/10251/87210. es_ES
dc.description.accrualMethod TFGM es_ES
dc.relation.pasarela TFGM\35010 es_ES


This item appears in the following Collection(s)

Show simple item record