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

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

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