Publicación: Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark
Portada
Citas bibliográficas
Gestores Bibliográficos
Indexadores
Código QR
Autor corporativo
Recolector de datos
Otros/Desconocido
Director audiovisual
Editor/Compilador
Editores
Fecha
Cita bibliográfica
Título de serie/ reporte/ volumen/ colección
Es Parte de
Resumen en español
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.
Resumen en inglés
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.