Adaptación de algoritmo OpenMP para computar caminos mínimos en grafos en arquitecturas x86
Material type:
ArticleDescription: 1 archivo (892 KB)Subject(s): Online resources: Summary: 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
| Item type | Home library | Collection | Call number | URL | Status | Date due | Barcode | |
|---|---|---|---|---|---|---|---|---|
Capítulo de libro
|
Biblioteca de la Facultad de Informática | Biblioteca digital | A1372 (Browse shelf(Opens below)) | Link to resource | No corresponde |
Browsing Biblioteca de la Facultad de Informática shelves, Collection: Biblioteca digital Close shelf browser (Hides shelf browser)
Formato de archivo PDF. -- Este documento es producción intelectual de la Facultad de Informática - UNLP (Colección BIPA/Biblioteca)
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
Congreso Argentino de Ciencias de la Computación (29no : 2023 : Luján, Argentina)