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

Título:

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

Autor:

Costi, Ulises

Otros autores / Colaboradores:

 Rucci, Enzo; [ Director/a]  Chichizola, Franco; [ Director/a] 

Temas:

MULTIPROCESADORES; 

URL:

http://sedici.unlp.edu.ar/handle/10915/109801,

Palabras clave:

Floyd-Warshal, Xeon Phi, 

Nota de tesis:

Tesina (Licenciatura en Informática) - Universidad Nacional de La Plata. Facultad de Informática, 2020.

Extensión:

1 archivo (2,93 MB) : il. col.

Resumen:

En la última década, los aceleradores han tomado mayor protagonismo en la comunidad de HPC. Recientemente, Intel introdujo la segunda generación de aceleradores Xeon Phi, con nombre en código Knights Landing (KNL), el cual trae importantes mejoras con respecto a su predecesor. Esta tesina se enfoca en evaluar el uso de la arquitectura KNL para acelerar el algoritmo Floyd-Warshall (FW). Partiendo de una versión paralela “clásica” del mismo, se muestra cómo aumenta el rendimiento con cada optimización aplicada hasta llegar a la solución óptimizada, con la cual se logró un pico de 1039 GFLOPS.

Puede solicitar más fácilmente el ejemplar con: TES 20/23

Capítulo 1 Introducción 
1.1. Motivación
 1.2. Objetivos y metodología 
1.3. Contribuciones
 1.4. Publicaciones 
1.5. Organización 

Capítulo 2 Intel Xeon Phi Knighs Landing 
2.1. Organización y arquitectura 
2.1.1. Orígen 
2.1.2. Novedades de KNL con respecto a las versiones anteriores de Xeon Phi 
2.1.3. Unidad de replicación escalable de la arquitectura 
2.1.4. Modos de ejecución (modos cluster)
 2.1.5. Tipos de memoria (MCDRAM y DDR)
 2.1.6. Modos de memoria 
2.1.7. Simultaneous Multi Threading (SMT) 
2.2. Modelos de programación
 2.2.1. OpenMP 
2.3. Optimizaciones 
2.3.1. Modos Cluster
 2.3.2. Modos de memoria 
2.3.3. Elección de cantidad de hilos por núcleo (SMT)
 2.3.4. Afinidad de hilos con núcleos 
2.3.5. MCDRAM y DDR 
2.3.6. Procesamiento vectorial (SIMD) 
2.3.7. Alineamiento de datos en memoria
 2.3.8. Desenrollado de bucles
 2.4. Resumen

 Capítulo 3 Algoritmos para caminos mínimos en grafos 
3.1. Problema de caminos mínimos en grafos
 3.2. Algoritmos para caminos mínimos en grafos 
3.2.1. Algoritmo Floyd-Warshall 
3.3. Estado del arte sobre aceleración del algoritmo Floyd-Warshall 
3.4. Resumen 

Capítulo 4 Aceleración del algoritmo Floyd-Warshall sobre Xeon Phi KNL
 4.1. Plataforma de pruebas 
4.2. Configuraciones de las pruebas
 4.3. Primeras versiones de FW implementadas 
4.3.1. Versión Naive-Sec: FW Secuencial “clásico”
4.3.2. Versión Naive-Par: FW “clásico” paralelizado
 4.3.3. Versión Block-Sec: Variante de FW con blocking 
4.4. Versión Opt-0 y sus optimizaciones incrementales
 4.4.1. Versión Opt-0: FW con blocking paralelizado
 4.4.2. Versión Opt-1: Optimización utilizando MCDRAM 
4.4.3. Versión Opt-2: Optimización utilizando vectorización guiada (SSE) 
4.4.4. Versión Opt-3: Optimización utilizando vectorización guiada (AVX2)
4.4.5. Versión Opt-4: Optimización utilizando vectorización guiada (AVX512)
 4.4.6. Versión Opt-5: Optimización utilizando alineación de datos en memoria 
4.4.7. Versión Opt-6: Optimización utilizando predicción de saltos por software
 4.4.8. Versión Opt-7: Optimización utilizando desenrollado de bucles
 4.4.9. Versión Opt-8: Optimización utilizando afinidad de hilos con núcleos
 4.4.10. Probando eficacia de la MCDRAM sobre el nivel de optimización Opt-5
 4.5. Experimentos adicionales