Aceleración del algoritmo Floyd-Warshall sobre Intel Xeon Phi KNL

Abstract

Desde hace años, los aceleradores van tomando mayor protagonismo en la comunidad de HPC. Con la introducción de los Xeon Phi de segunda generación, con nombre en código Knights Landing (KNL), la comunidad dispone de un nuevo acelerador x86 que trae importantes mejoras con respecto a su predecesor. Entre ellas se destacan la ejecución fuera de orden, la duplicación de la cantidad de VPUs, y la integración de una memoria de alto ancho de banda. Una de las áreas bien conocidas por demandar gran poder de cómputo es la teoría de grafos, siendo el algoritmo Floyd-Warshall (FW) un caso bien conocido de la misma. La popularidad y alta demanda computacional de FW lo vuelve un caso interesante de análisis en HPC. Es por este motivo que esta tesina se enfoca en evaluar el uso de arquitectura Xeon Phi KNL para acelerar el algoritmo FW. Partiendo de una versión paralela “clásica” de FW, se muestra cómo aumenta el rendimiento con cada optimización aplicada hasta llegar a la solución optimizada, con la cual se logró un pico de 1039 GFLOPS. Complementariamente, se analizaron diferentes variantes de la implementación, con el fin de evaluar su utilidad en distintos escenarios alternativos. Por último, el código se encuentra disponible para beneficio de la comunidad académica, científica y productiva.