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

Abstract

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.