Librería C para cómputo paralelo de caminos mínimos en grafos sobre arquitecturas multicore

Los grafos han adquirido una relevancia significativa para modelar y resolver problemas en diversas áreas. El algoritmo Floyd-Warshall (FW) permite hallar los caminos mínimos entre todos los vértices de un grafo pesado. Debido a su alta demanda computacional (O(n3)), muchos esfuerzos se han realizad...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Lambre, Jerónimo, Rucci, Enzo
Formato:	Objeto de conferencia
Lenguaje:	Español
Publicado:	2024
Materias:	Ciencias Informáticas FW Librería Caminos mínimos OpenMP
Acceso en línea:	http://sedici.unlp.edu.ar/handle/10915/177685
Aporte de:	SEDICI (UNLP) de Universidad Nacional de La Plata

id	I19-R120-10915-177685
record_format	dspace
spelling	I19-R120-10915-1776852025-03-26T20:04:09Z http://sedici.unlp.edu.ar/handle/10915/177685 Librería C para cómputo paralelo de caminos mínimos en grafos sobre arquitecturas multicore Lambre, Jerónimo Rucci, Enzo 2024-10 2024 2025-03-26T13:36:19Z es Ciencias Informáticas FW Librería Caminos mínimos OpenMP Los grafos han adquirido una relevancia significativa para modelar y resolver problemas en diversas áreas. El algoritmo Floyd-Warshall (FW) permite hallar los caminos mínimos entre todos los vértices de un grafo pesado. Debido a su alta demanda computacional (O(n3)), muchos esfuerzos se han realizado en las últimas 2 décadas para acelerarlo. Sin embargo, las propuestas existentes suelen obviar los aspectos funcionales para priorizar los vinculados al rendimiento, lo que limita seriamente su reúso. Es por lo que en este artículo se presenta el diseño y desarrollo de una librería en C que provee implementac.iones optimizadas del algoritmo FW para arquitecturas multicore. La librería diseñada soporta grafos de cualquier tamaño, múltiples tipos de datos, y compatibilidad con diferentes formatos de archivo (JSON y CSV) y sistemas operativos (Windows y Linux). Adicionalmente, también permite configurar diferentes aspectos de la ejecución, tanto funcionales como de rendimiento. Los resultados experimentales muestran que es capaz de lograr un aprovechamiento alto de los recursos del sistema de prueba, a un muy bajo esfuerzo de programación por parte del usuario. Red de Universidades con Carreras en Informática Objeto de conferencia Objeto de conferencia http://creativecommons.org/licenses/by-nc-sa/4.0/ Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) application/pdf 258-269
institution	Universidad Nacional de La Plata
institution_str	I-19
repository_str	R-120
collection	SEDICI (UNLP)
language	Español
topic	Ciencias Informáticas FW Librería Caminos mínimos OpenMP
spellingShingle	Ciencias Informáticas FW Librería Caminos mínimos OpenMP Lambre, Jerónimo Rucci, Enzo Librería C para cómputo paralelo de caminos mínimos en grafos sobre arquitecturas multicore
topic_facet	Ciencias Informáticas FW Librería Caminos mínimos OpenMP
description	Los grafos han adquirido una relevancia significativa para modelar y resolver problemas en diversas áreas. El algoritmo Floyd-Warshall (FW) permite hallar los caminos mínimos entre todos los vértices de un grafo pesado. Debido a su alta demanda computacional (O(n3)), muchos esfuerzos se han realizado en las últimas 2 décadas para acelerarlo. Sin embargo, las propuestas existentes suelen obviar los aspectos funcionales para priorizar los vinculados al rendimiento, lo que limita seriamente su reúso. Es por lo que en este artículo se presenta el diseño y desarrollo de una librería en C que provee implementac.iones optimizadas del algoritmo FW para arquitecturas multicore. La librería diseñada soporta grafos de cualquier tamaño, múltiples tipos de datos, y compatibilidad con diferentes formatos de archivo (JSON y CSV) y sistemas operativos (Windows y Linux). Adicionalmente, también permite configurar diferentes aspectos de la ejecución, tanto funcionales como de rendimiento. Los resultados experimentales muestran que es capaz de lograr un aprovechamiento alto de los recursos del sistema de prueba, a un muy bajo esfuerzo de programación por parte del usuario.
format	Objeto de conferencia Objeto de conferencia
author	Lambre, Jerónimo Rucci, Enzo
author_facet	Lambre, Jerónimo Rucci, Enzo
author_sort	Lambre, Jerónimo
title	Librería C para cómputo paralelo de caminos mínimos en grafos sobre arquitecturas multicore
title_short	Librería C para cómputo paralelo de caminos mínimos en grafos sobre arquitecturas multicore
title_full	Librería C para cómputo paralelo de caminos mínimos en grafos sobre arquitecturas multicore
title_fullStr	Librería C para cómputo paralelo de caminos mínimos en grafos sobre arquitecturas multicore
title_full_unstemmed	Librería C para cómputo paralelo de caminos mínimos en grafos sobre arquitecturas multicore
title_sort	librería c para cómputo paralelo de caminos mínimos en grafos sobre arquitecturas multicore
publishDate	2024
url	http://sedici.unlp.edu.ar/handle/10915/177685
work_keys_str_mv	AT lambrejeronimo libreriacparacomputoparalelodecaminosminimosengrafossobrearquitecturasmulticore AT ruccienzo libreriacparacomputoparalelodecaminosminimosengrafossobrearquitecturasmulticore
_version_	1845116797496328192

Librería C para cómputo paralelo de caminos mínimos en grafos sobre arquitecturas multicore

Ejemplares similares