Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark

La escalonabilidad* de grafos es un problema en NP del que se desconoce su inclusión en las clases de complejidad P o NP-completa. Con el fin de comprender su comportamiento computacional en el caso particular de los grafos bipartitos, podría ser de utilidad disponer de un método eficiente para gene...

Full description

Autores:
Arango Holguín, Julián David
Cárdenas Álzate, Milena
Santamaría Galvis, Andrés David
Tipo de recurso:
Article of journal
Fecha de publicación:
2017
Institución:
Universidad de los Llanos
Repositorio:
Repositorio Digital Universidad de los LLanos
Idioma:
eng
OAI Identifier:
oai:repositorio.unillanos.edu.co:001/3902
Acceso en línea:
https://repositorio.unillanos.edu.co/handle/001/3902
https://doi.org/10.22579/20112629.428
Palabra clave:
Apache™ Hadoop®
Apache Spark™
bipartite graph shellability
parallel experiments
unclassified NP problems
Apache™ Hadoop®
Apache Spark™
shellabilidade de grafos bipartidos
experimento paralelo
problemas NP não classificado
Apache™ Hadoop®
Apache Spark™
escalonabilidad de grafos bipartitos
experimentos en paralelo
problemas NP sin clasificar
Rights
openAccess
License
Orinoquia - 2019
id Unillanos2_f55820b6f564658828cf2d01c6eeb4c0
oai_identifier_str oai:repositorio.unillanos.edu.co:001/3902
network_acronym_str Unillanos2
network_name_str Repositorio Digital Universidad de los LLanos
repository_id_str
dc.title.spa.fl_str_mv Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark
dc.title.translated.eng.fl_str_mv Parallelizing an experiment to decide shellability on bipartite graphs using Apache Spark
title Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark
spellingShingle Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark
Apache™ Hadoop®
Apache Spark™
bipartite graph shellability
parallel experiments
unclassified NP problems
Apache™ Hadoop®
Apache Spark™
shellabilidade de grafos bipartidos
experimento paralelo
problemas NP não classificado
Apache™ Hadoop®
Apache Spark™
escalonabilidad de grafos bipartitos
experimentos en paralelo
problemas NP sin clasificar
title_short Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark
title_full Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark
title_fullStr Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark
title_full_unstemmed Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark
title_sort Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark
dc.creator.fl_str_mv Arango Holguín, Julián David
Cárdenas Álzate, Milena
Santamaría Galvis, Andrés David
dc.contributor.author.spa.fl_str_mv Arango Holguín, Julián David
Cárdenas Álzate, Milena
Santamaría Galvis, Andrés David
dc.subject.eng.fl_str_mv Apache™ Hadoop®
Apache Spark™
bipartite graph shellability
parallel experiments
unclassified NP problems
Apache™ Hadoop®
Apache Spark™
shellabilidade de grafos bipartidos
experimento paralelo
problemas NP não classificado
topic Apache™ Hadoop®
Apache Spark™
bipartite graph shellability
parallel experiments
unclassified NP problems
Apache™ Hadoop®
Apache Spark™
shellabilidade de grafos bipartidos
experimento paralelo
problemas NP não classificado
Apache™ Hadoop®
Apache Spark™
escalonabilidad de grafos bipartitos
experimentos en paralelo
problemas NP sin clasificar
dc.subject.spa.fl_str_mv Apache™ Hadoop®
Apache Spark™
escalonabilidad de grafos bipartitos
experimentos en paralelo
problemas NP sin clasificar
description La escalonabilidad* de grafos es un problema en NP del que se desconoce su inclusión en las clases de complejidad P o NP-completa. Con el fin de comprender su comportamiento computacional en el caso particular de los grafos bipartitos, podría ser de utilidad disponer de un método eficiente para generar y analizar instancias escalonables. La literatura reporta un experimento secuencial, y de costo exponencial, diseñado para determinar la escalonabilidad de un conjunto de instancias. En el presente trabajo, y con el fin de mejorar el desempeño experimento mencionado, proponemos tres alternativas utilizando Apache Spark: una multinúcleo, otra multinodo y otra completamente paralela. Además, comparamos el tiempo de ejecución de cada una de ellas respecto a la versión original en grafos bipartitos aleatorios con 10,12,15,20 y 50 vértices, y obtuvimos aceleraciones (speedups) entre 1.37 y 1.67 para la versión multinúcleo, entre 2.34 y 3.56 para la versión multinodo, y entre 2.37 y 3.12 para la versión completamente paralela. Los resultados sugieren que la paralelización del experimento podría mitigar los enormes tiempos de ejecución del enfoque original.
publishDate 2017
dc.date.accessioned.none.fl_str_mv 2017-07-16T00:00:00Z
2024-07-25T18:14:35Z
dc.date.available.none.fl_str_mv 2017-07-16T00:00:00Z
2024-07-25T18:14:35Z
dc.date.issued.none.fl_str_mv 2017-07-16
dc.type.spa.fl_str_mv Artículo de revista
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.driver.eng.fl_str_mv info:eu-repo/semantics/article
dc.type.local.eng.fl_str_mv Journal article
dc.type.version.eng.fl_str_mv info:eu-repo/semantics/publishedVersion
dc.type.coar.eng.fl_str_mv http://purl.org/coar/resource_type/c_6501
dc.type.content.eng.fl_str_mv Text
dc.type.coarversion.eng.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
format http://purl.org/coar/resource_type/c_6501
status_str publishedVersion
dc.identifier.issn.none.fl_str_mv 0121-3709
dc.identifier.uri.none.fl_str_mv https://repositorio.unillanos.edu.co/handle/001/3902
dc.identifier.doi.none.fl_str_mv 10.22579/20112629.428
dc.identifier.eissn.none.fl_str_mv 2011-2629
dc.identifier.url.none.fl_str_mv https://doi.org/10.22579/20112629.428
identifier_str_mv 0121-3709
10.22579/20112629.428
2011-2629
url https://repositorio.unillanos.edu.co/handle/001/3902
https://doi.org/10.22579/20112629.428
dc.language.iso.eng.fl_str_mv eng
language eng
dc.relation.references.eng.fl_str_mv Björner A, Wachs ML. Shellable Nonpure Complexes and Posets I. Trans. Amer. Math. Soc. 1996;348(4):1299-1327.
Castrillón ID, Cruz R.). Escalonabilidad de grafos e hipergrafos simples que contienen vértices simpliciales. Matemáticas: Enseñanza Universitaria. 2012;20(1):29-80.
Cruz R, Estrada M. Vértices simpliciales y escalonabilidad de grafos. Morfismos. 2008;12:21-36.
Csárdi G, Nepusz T. 2006. The igraph software package for complex network research. InterJournal Complex Systems. Retrieved from http://igraph.sf.net
Csárdi G, Nepusz T. (2012, June). The igraph software package for complex network research, (ver. 0.6). Retrieved from http://igraph.sf.net
Hadoop®, A. 2016. The Apache® Software Foundation. Retrieved from The Apache® Software Foundation: http://hadoop.apache.org/
Hennessy JL, Patterson DA. 2012. Computer Architecture: A Quantitative Approach. 5th ed. Elsevier - Morgan Kaufmann.
Herlihy M. 2010. Applications of Shellable Complexes to Distributed Computing. CONCUR (pp. 19-20). Springer.
Herlihy M, Rajsbaum S. 2010. Concurrent Computing and Shellable Complexes. DISC (pp. 109-123). Springer.
Kaibel V, Pfetsch ME. 2003. Some Algorithmic Problems in Polytope Theory. Algebra, Geometry, and Software Systems (outcome of a Dagstuhl Seminar) (pp. 23-47). Springer-Verlag.
Lewiner T. 2005. Complexos de Morse discretos e geométricos. master's thesis. Rio de Janeiro.
Müller-Hannemann M. Shelling Hexahedral Complexes for Mesh Generation. Journal of Graph Algortihms and Applications, 2001;5(5):59-91.
Santamaria-Galvis AD. 2013. On Algorithmic Complexity of Shellability in Graphs and their Associated Simplicial Complexes. Master's thesis, Facultad de Minas, Universidad Nacional de Colombia, Medellin, Colombia, Medellín.
Schläfli L. (1901, January). Theorie der vielfachen Kontinuität; hrsg. im Auftrage der Denkschriften_Kommission der Schweizer. Naturforschenden Gesellschaft. Zürich: Zürcher & Furrer.
Spark™ A. 2016. Apache Spark™ Lightning-fast cluster computing. (The Apache® Software Foundation) Retrieved from Apache Spark™ Lightning-fast cluster computing: http://spark.apache.org/
Van Tuyl A, Villarreal RH. Shellable graphs and sequentially Cohen-Macaulay bipartite graphs. J. Combin. Theory Ser. A, 2008;115(5):799-814.
Woodroofe R. Vertex decomposable graphs and obstructions to shellability. Proc. Amer. Math. Soc. 2009;137(10):3235-3246.
dc.relation.bitstream.none.fl_str_mv https://orinoquia.unillanos.edu.co/index.php/orinoquia/article/download/428/1019
dc.relation.citationendpage.none.fl_str_mv 36
dc.relation.citationissue.spa.fl_str_mv 1 Sup
dc.relation.citationstartpage.none.fl_str_mv 30
dc.relation.citationvolume.spa.fl_str_mv 21
dc.relation.ispartofjournal.spa.fl_str_mv Orinoquia
dc.rights.eng.fl_str_mv Orinoquia - 2019
dc.rights.uri.eng.fl_str_mv https://creativecommons.org/licenses/by-nc-sa/4.0/
dc.rights.accessrights.eng.fl_str_mv info:eu-repo/semantics/openAccess
dc.rights.coar.eng.fl_str_mv http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv Orinoquia - 2019
https://creativecommons.org/licenses/by-nc-sa/4.0/
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.mimetype.eng.fl_str_mv application/pdf
dc.publisher.spa.fl_str_mv Universidad de los Llanos
dc.source.eng.fl_str_mv https://orinoquia.unillanos.edu.co/index.php/orinoquia/article/view/428
institution Universidad de los Llanos
bitstream.url.fl_str_mv https://repositorio.unillanos.edu.co/bitstreams/1342ff8c-fc75-4dde-baaa-bda6b734ce41/download
bitstream.checksum.fl_str_mv 3d2d11e3b0a826c7ee569a2fa6c4d4ac
bitstream.checksumAlgorithm.fl_str_mv MD5
repository.name.fl_str_mv Repositorio Universidad de Los Llanos
repository.mail.fl_str_mv repositorio@unillanos.edu.co
_version_ 1812104650675978240
spelling Arango Holguín, Julián DavidCárdenas Álzate, MilenaSantamaría Galvis, Andrés David2017-07-16T00:00:00Z2024-07-25T18:14:35Z2017-07-16T00:00:00Z2024-07-25T18:14:35Z2017-07-160121-3709https://repositorio.unillanos.edu.co/handle/001/390210.22579/20112629.4282011-2629https://doi.org/10.22579/20112629.428La escalonabilidad* de grafos es un problema en NP del que se desconoce su inclusión en las clases de complejidad P o NP-completa. Con el fin de comprender su comportamiento computacional en el caso particular de los grafos bipartitos, podría ser de utilidad disponer de un método eficiente para generar y analizar instancias escalonables. La literatura reporta un experimento secuencial, y de costo exponencial, diseñado para determinar la escalonabilidad de un conjunto de instancias. En el presente trabajo, y con el fin de mejorar el desempeño experimento mencionado, proponemos tres alternativas utilizando Apache Spark: una multinúcleo, otra multinodo y otra completamente paralela. Además, comparamos el tiempo de ejecución de cada una de ellas respecto a la versión original en grafos bipartitos aleatorios con 10,12,15,20 y 50 vértices, y obtuvimos aceleraciones (speedups) entre 1.37 y 1.67 para la versión multinúcleo, entre 2.34 y 3.56 para la versión multinodo, y entre 2.37 y 3.12 para la versión completamente paralela. Los resultados sugieren que la paralelización del experimento podría mitigar los enormes tiempos de ejecución del enfoque original.Graph shellability is an NP problem whose classification either in P or in NP-complete remains unknown. In order to understand the computational behavior of graph shellability on bipartite graphs, as a particular case, it could be useful to develop an efficient way to generate and analyze results over sets of shellable and non-shellable instances. In this way, a sequentially designed exponential time experiment for deciding shellability on randomly generated instances was proposed in literature. In this work, with the aim of improving the performance of that experiment, we propose three alternative approaches using Apache Spark™, we called multi-core, multi-node and full-parallel. We tested and compared their execution time for bipartite graphs with 10,12,15,20 and 50 vertices with regard to the original version, and we got speedups between 1.37 and 1.67 for the first one, between 2.34 and 3.56 for the second one, and between 2.37 y 3.12 for the last version. The results suggest that parallelization could relieve the large execution times of the original approach.application/pdfengUniversidad de los LlanosOrinoquia - 2019https://creativecommons.org/licenses/by-nc-sa/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2https://orinoquia.unillanos.edu.co/index.php/orinoquia/article/view/428Apache™ Hadoop®Apache Spark™bipartite graph shellabilityparallel experimentsunclassified NP problemsApache™ Hadoop®Apache Spark™shellabilidade de grafos bipartidosexperimento paraleloproblemas NP não classificadoApache™ Hadoop®Apache Spark™escalonabilidad de grafos bipartitosexperimentos en paraleloproblemas NP sin clasificarParalelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache SparkParallelizing an experiment to decide shellability on bipartite graphs using Apache SparkArtículo de revistainfo:eu-repo/semantics/articleJournal articleinfo:eu-repo/semantics/publishedVersionhttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1Texthttp://purl.org/coar/version/c_970fb48d4fbd8a85Björner A, Wachs ML. Shellable Nonpure Complexes and Posets I. Trans. Amer. Math. Soc. 1996;348(4):1299-1327.Castrillón ID, Cruz R.). Escalonabilidad de grafos e hipergrafos simples que contienen vértices simpliciales. Matemáticas: Enseñanza Universitaria. 2012;20(1):29-80.Cruz R, Estrada M. Vértices simpliciales y escalonabilidad de grafos. Morfismos. 2008;12:21-36.Csárdi G, Nepusz T. 2006. The igraph software package for complex network research. InterJournal Complex Systems. Retrieved from http://igraph.sf.netCsárdi G, Nepusz T. (2012, June). The igraph software package for complex network research, (ver. 0.6). Retrieved from http://igraph.sf.netHadoop®, A. 2016. The Apache® Software Foundation. Retrieved from The Apache® Software Foundation: http://hadoop.apache.org/Hennessy JL, Patterson DA. 2012. Computer Architecture: A Quantitative Approach. 5th ed. Elsevier - Morgan Kaufmann.Herlihy M. 2010. Applications of Shellable Complexes to Distributed Computing. CONCUR (pp. 19-20). Springer.Herlihy M, Rajsbaum S. 2010. Concurrent Computing and Shellable Complexes. DISC (pp. 109-123). Springer.Kaibel V, Pfetsch ME. 2003. Some Algorithmic Problems in Polytope Theory. Algebra, Geometry, and Software Systems (outcome of a Dagstuhl Seminar) (pp. 23-47). Springer-Verlag.Lewiner T. 2005. Complexos de Morse discretos e geométricos. master's thesis. Rio de Janeiro.Müller-Hannemann M. Shelling Hexahedral Complexes for Mesh Generation. Journal of Graph Algortihms and Applications, 2001;5(5):59-91.Santamaria-Galvis AD. 2013. On Algorithmic Complexity of Shellability in Graphs and their Associated Simplicial Complexes. Master's thesis, Facultad de Minas, Universidad Nacional de Colombia, Medellin, Colombia, Medellín.Schläfli L. (1901, January). Theorie der vielfachen Kontinuität; hrsg. im Auftrage der Denkschriften_Kommission der Schweizer. Naturforschenden Gesellschaft. Zürich: Zürcher & Furrer.Spark™ A. 2016. Apache Spark™ Lightning-fast cluster computing. (The Apache® Software Foundation) Retrieved from Apache Spark™ Lightning-fast cluster computing: http://spark.apache.org/Van Tuyl A, Villarreal RH. Shellable graphs and sequentially Cohen-Macaulay bipartite graphs. J. Combin. Theory Ser. A, 2008;115(5):799-814.Woodroofe R. Vertex decomposable graphs and obstructions to shellability. Proc. Amer. Math. Soc. 2009;137(10):3235-3246.https://orinoquia.unillanos.edu.co/index.php/orinoquia/article/download/428/1019361 Sup3021OrinoquiaPublicationOREORE.xmltext/xml2709https://repositorio.unillanos.edu.co/bitstreams/1342ff8c-fc75-4dde-baaa-bda6b734ce41/download3d2d11e3b0a826c7ee569a2fa6c4d4acMD51001/3902oai:repositorio.unillanos.edu.co:001/39022024-07-25 13:14:36.033https://creativecommons.org/licenses/by-nc-sa/4.0/Orinoquia - 2019metadata.onlyhttps://repositorio.unillanos.edu.coRepositorio Universidad de Los Llanosrepositorio@unillanos.edu.co

Publicaciones similares