Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark
Fuente:
Redalyc
Saved in:
| Main Author: | |
|---|---|
| Format: | Artículo científico |
| Language: | es |
| Published: |
Universidad de Los Llanos
2017
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1876431046989316096 |
|---|---|
| author | Julián D. Arango-Holguín |
| author_facet | Julián D. Arango-Holguín |
| contents | Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark Julián D. Arango-Holguín Milena Cárdenas-Álzate2 Andrés D. Santamaría-Galvis Veterinaria pro Apache Spark™ Apache™ Hadoop® blemas NP sin clasif experimentos en paralelo 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 instan-cias. 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érti-ces, 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 2017 artículo científico 0121-3709 https://www.redalyc.org/articulo.oa?id=89659219005 es http://www.redalyc.org/revista.oa?id=896 Orinoquia application/pdf Universidad de Los Llanos Orinoquia (Colombia) Num.1 Vol.21 |
| format | Artículo científico |
| id | redalyc_89659219005 |
| institution | Redalyc |
| language | es |
| publishDate | 2017 |
| publisher | Universidad de Los Llanos |
| spellingShingle | Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark Julián D. Arango-Holguín Veterinaria pro Apache Spark™ Apache™ Hadoop® blemas NP sin clasif experimentos en paralelo Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark Julián D. Arango-Holguín Milena Cárdenas-Álzate2 Andrés D. Santamaría-Galvis Veterinaria pro Apache Spark™ Apache™ Hadoop® blemas NP sin clasif experimentos en paralelo 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 instan-cias. 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érti-ces, 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 2017 artículo científico 0121-3709 https://www.redalyc.org/articulo.oa?id=89659219005 es http://www.redalyc.org/revista.oa?id=896 Orinoquia application/pdf Universidad de Los Llanos Orinoquia (Colombia) Num.1 Vol.21 |
| title | Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark |
| topic | Veterinaria pro Apache Spark™ Apache™ Hadoop® blemas NP sin clasif experimentos en paralelo |
| url | https://www.redalyc.org/articulo.oa?id=89659219005 |