Adaptación de algoritmo OpenMP para computar caminos mínimos en grafos en arquitecturas x86

Título:

Adaptación de algoritmo OpenMP para computar caminos mínimos en grafos en arquitecturas x86

Autor:

Calderón, Sergio

Colaboradores:

; Rucci, Enzo; Chichizola, Franco

Temas:

COMPUTACIÓN DE ALTO RENDIMIENTO - HPCARQUITECTURAS MULTICORE

En:

Congreso Argentino de Ciencias de la Computación (29no : 2023 : Luján, Argentina)

Resumen:

Los grafos han adquirido una relevancia significativa para modelar y resolver problemas en diversas áreas. El algoritmo FloydWarshall (FW) permite hallar los caminos mínimos entre vértices. Es una solución de alta demanda computacional (O(n 3 )), debiendo emplear cómputo paralelo cuando el tamaño del problema escala. En este trabajo, se presenta la optimización de FW en arquitecturas multicore x86 de propósito general, adaptando un código diseñado para un acelerador específico (Xeon Phi KNL). Se parte desde una versión paralela que emplea una técnica de blocking, y luego se describen las mejoras incrementales aplicadas. Las pruebas realizadas en un servidor con 2×Intel Xeon Platinum 8276L y en un equipo comercial con Intel Core i5-10400F muestran mejoras acumuladas de 7.31× y 6.98×, respectivamente. Todas las optimizaciones resultan beneficiosas, aunque con distinto impacto. Por último, se plantea la idea de una nueva optimización FW

URL/DOI:

http://sedici.unlp.edu.ar/handle/10915/164997

Medio:

Soporte electrónico

Tipo de documento:

Artículo

Descripción física:

1 archivo (892 KB)

Idioma:

Español

Publicación:

, 2023

Puede solicitar más fácilmente el ejemplar con: A1372

Ver estantes