Paralelização de um experimento para determinar a shellabilidade de grafos bipartidos usando Apache Spark
DOI:
https://doi.org/10.22579/20112629.428Palavras-chave:
Apache™ Hadoop®, Apache Spark™, shellabilidade de grafos bipartidos, experimento paralelo, problemas NP não classificadoResumo
A shellabilidade dos grafos é um problema em NP, do qual é desconhecida sua inclusão nas classes da complexidade P ou NP-completo. A fim de compreender seu comportamento computacional no caso particular dos grafos bipartidos, poderia ser útil ter um método eficiente para gerar e analisar instâncias shellables. A literatura relata um experimento sequencial, e custo exponencial, projetado para determinar a escalabilidade do um conjunto de instâncias. Neste trabalho, e a fim do melhorar o desempenho do experimento mencionado, propomos três alternativas usando Apache Spark: uma multinúcleo, outra multinó e outra completamente paralela. Além disso, nós compararmos o tempo de execução de cada um deles respeito da versão original em grafos bipartidos com 10,12,15,20 e 50 vértices e obtivemos acelerações (speedups) entre 1.37 e 1.67 para a versão Multinúcleo, entre 2.34 e 3.56 para a versão Multinó, e entre 2.37 e 3.12 para a versão completamente paralela. Os resultados sugerem que a paralelização do experimento poderia atenuar os enormes tempos de execução da abordagem original.Downloads
Referências
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.
