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

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(n3)), debiendo emplear cómputo paralelo cuando el tamaño del...

Descripción completa

Detalles Bibliográficos
Autores principales:	Calderón, Sergio, Rucci, Enzo, Chichizola, Franco
Formato:	Objeto de conferencia
Lenguaje:	Español
Publicado:	2023
Materias:	Ciencias Informáticas Floyd-Warshall Multicore HPC Caminos mínimos Xeon Xeon Phi Knights Landing Core OpenMP
Acceso en línea:	http://sedici.unlp.edu.ar/handle/10915/164997
Aporte de:	SEDICI (UNLP) de Universidad Nacional de La Plata

id	I19-R120-10915-164997
record_format	dspace
spelling	I19-R120-10915-1649972024-04-18T20:03:12Z http://sedici.unlp.edu.ar/handle/10915/164997 Adaptación de algoritmo OpenMP para computar caminos mínimos en grafos en arquitecturas x86 Calderón, Sergio Rucci, Enzo Chichizola, Franco 2023-10 2024 2024-04-18T12:37:17Z es Ciencias Informáticas Floyd-Warshall Multicore HPC Caminos mínimos Xeon Xeon Phi Knights Landing Core OpenMP 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(n3)), 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. Red de Universidades con Carreras en Informática Instituto de Investigación 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 489-500
institution	Universidad Nacional de La Plata
institution_str	I-19
repository_str	R-120
collection	SEDICI (UNLP)
language	Español
topic	Ciencias Informáticas Floyd-Warshall Multicore HPC Caminos mínimos Xeon Xeon Phi Knights Landing Core OpenMP
spellingShingle	Ciencias Informáticas Floyd-Warshall Multicore HPC Caminos mínimos Xeon Xeon Phi Knights Landing Core OpenMP Calderón, Sergio Rucci, Enzo Chichizola, Franco Adaptación de algoritmo OpenMP para computar caminos mínimos en grafos en arquitecturas x86
topic_facet	Ciencias Informáticas Floyd-Warshall Multicore HPC Caminos mínimos Xeon Xeon Phi Knights Landing Core OpenMP
description	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(n3)), 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.
format	Objeto de conferencia Objeto de conferencia
author	Calderón, Sergio Rucci, Enzo Chichizola, Franco
author_facet	Calderón, Sergio Rucci, Enzo Chichizola, Franco
author_sort	Calderón, Sergio
title	Adaptación de algoritmo OpenMP para computar caminos mínimos en grafos en arquitecturas x86
title_short	Adaptación de algoritmo OpenMP para computar caminos mínimos en grafos en arquitecturas x86
title_full	Adaptación de algoritmo OpenMP para computar caminos mínimos en grafos en arquitecturas x86
title_fullStr	Adaptación de algoritmo OpenMP para computar caminos mínimos en grafos en arquitecturas x86
title_full_unstemmed	Adaptación de algoritmo OpenMP para computar caminos mínimos en grafos en arquitecturas x86
title_sort	adaptación de algoritmo openmp para computar caminos mínimos en grafos en arquitecturas x86
publishDate	2023
url	http://sedici.unlp.edu.ar/handle/10915/164997
work_keys_str_mv	AT calderonsergio adaptaciondealgoritmoopenmpparacomputarcaminosminimosengrafosenarquitecturasx86 AT ruccienzo adaptaciondealgoritmoopenmpparacomputarcaminosminimosengrafosenarquitecturasx86 AT chichizolafranco adaptaciondealgoritmoopenmpparacomputarcaminosminimosengrafosenarquitecturasx86
_version_	1807222958276476928

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

Ejemplares similares