class: inverse, center, middle count: false background-image: url(htop.png) # Computación Paralela ## Performance Carlos Bederián, [carlos.bederian@unc.edu.ar](mailto:carlos.bederian@unc.edu.ar) --- # Motivación "We should forget about small efficiencies, say about 97% of the time: ** premature optimization is the root of all evil **" \- Donald Knuth .right[![:scale 40%](knuth.jpg)] --- # Primero, antes que nada... - ¿Hasta dónde llega mi hardware? - ¿Cómo veo si es malo mi código? --- # CPU: Performance pico Ejercicio teórico: GFLOPS que le puedo exprimir al procesador si se alinean todos los astros 1. Identificar las unidades de vectores en el diagrama de la arquitectura y su ancho 2. Ver si soportan FMA, que duplica la cantidad de operaciones por ciclo de reloj (caso contrario: 1 por unidad por ciclo) 2. Buscar la frecuencia máxima de las unidades de vectores en el modo más ancho 3. Multiplicar todo: `$$ \mathit{GFLOPS}_{64} = \mathit{Cores} * \mathit{Unidades_{64}} * \frac{\mathit{Ancho}}{64} * \mathit{Frecuencia} * \mathit{FMA} $$` `$$ \mathit{GFLOPS}_{32} = \mathit{Cores} * \mathit{Unidades_{32}} * \frac{\mathit{Ancho}}{32} * \mathit{Frecuencia} * \mathit{FMA} $$` --- # CPU round up |Equipo | Procesador | Cores | GHz | FPUs x ancho | FMA | GFLOPS | |--------|------------|:-----:|:---:|:------------:|:---:|:------:| |CCAD Cristina (2010) | 2x Xeon E5420 (2007) | 4 | 2.5 | 2 x 128 | no | 80 | |CCAD Mendieta (2013) | 2x Xeon E5-2680 (2012) | 8 | 2.7 | 2 x 256 | no | 346 | |CSC TUPAC (2015) | 4x Opteron 6276 (2011), |8 | 2.3 | 2 x 128 | sí | 589 | |CCAD Eulogia (2017) | 1x Xeon Phi 7210 (2016), | 64| 1.3 | 2 x 512 | sí | 2662 | |CCAD Mulatona (2018) | 2x Xeon E5-2683 v4 (2016) |16 | 1.7 | 2 x 256 | sí | 870 | |SMN Huayra Muyu (2019) | 2x Xeon Gold 6142 (2017) |16 | 1.6 | 2 x 512 | sí | 1638 | |Gaming PC (2019) | 1x Core i9-9900K (2018) | 8 | 3.6 | 2 x 256 | sí | 461 | --- # Encuentre las diferencias |Equipo | Procesador | Cores | GHz | FPUs x ancho | FMA | GFLOPS | |--------|------------|:-----:|:---:|:------------:|:---:|:------:| |CCAD Mulatona (2018) | 2x Xeon E5-2683 v4 (2016) |16 | **1.7** | 2 x 256 | sí | 870 | |SMN Huayra Muyu (2019) | 2x Xeon Gold 6142 (2017) |16 | **1.6** | 2 x 512 | sí | 1638 | .center[![:scale 100%](2683.png)] .center[![:scale 100%](6142.png)] --- .center[![:scale 70%](turbo.png)] [Microway Inc., Detailed Specifications of the “Skylake-SP” Intel Xeon Processor Scalable Family CPUs](https://www.microway.com/knowledge-center-articles/detailed-specifications-of-the-skylake-sp-intel-xeon-processor-scalable-family-cpus/) --- # Throttling .center[![:scale 60%](dog.jpeg)] > Since a significant portion of the power consumption under heavy load is due to leakage current (which increases very rapidly with temperature), a more aggressive cooling solution that keeps the die temperature lower should also help the processor attain higher Turbo frequencies before hitting the power limit. > \- [John McCalpin a.k.a. Dr. Bandwidth](https://software.intel.com/en-us/forums/intel-isa-extensions/topic/710250#comment-1896726) --- # Memoria: Performance pico Ejercicio teórico: GBps que le puedo exprimir al sistema de memoria 1. Identificar la velocidad (en gigatransferencias/s) de la memoria - Cada transferencia es de 64 bits 2. Ver la cantidad de canales de memoria que soporta cada procesador - Revisar que estén efectivamente poblados! - `sudo dmidecode -t memory` 3. Ver la cantidad de procesadores instalados 4. Multiplicar `$$ \mathit{GBps} = \mathit{Procesadores} * \mathit{Canales} * \mathit{Velocidad} * 8 $$` --- # CPU: Performance práctica El benchmark más utilizado en HPC es LINPACK - Precisión doble - Resuelve un sistema denso de ecuaciones lineales `\( Ax = B \)` - Factorización LU con pivoting parcial e intercambio de filas (`dgesv` de LAPACK) - `\( \frac{2}{3}N^{3} + 2N^{2} \)` operaciones con N arbitrario Highly-Parallel LINPACK - Versión distribuida de LINPACK usando MPI - Llama a BLAS para operaciones matriciales --- # Top500 Lista de las 500 supercomputadoras más potentes ordenadas por performance obtenida en HPL. - Datos desde 1993 (!!!) - Información detallada de la configuración de cada cluster - Dos ediciones anuales: - Junio (ISC) - Noviembre (SC) - Nuevos benchmarks similares: Green500, HPCG, Graph500, IO500 .right[![:scale 90%](dongarra.jpg)] --- .center[![:scale 100%](top500.png)] --- # Goodhart's Law > When a measure becomes a target, it ceases to be a good measure. Double-precision FPUs in High-Performance Computing: an Embarrassment of Riches? - La mitad del poder de cómputo de un Xeon Phi 72x0 se desperdicia, **incluso en HPL** - Una unidad de precisión doble ocupa ~3x más transistores que el equivalente en precisión simple --- # Memoria: Performance real STREAM: Benchmark de ancho de banda de memoria escrito por John McCalpin Para `\( i \in [1..N] \)` con arreglos de N elementos que son mucho más grandes que la cache - Copy: `C[i] = A[i];` - Scale: `C[i] = scalar * A[i];` - Add: `C[i] = A[i] + B[i];` - Triad: `C[i] = A[i] + scalar * B[i];` --- .center[![:scale 100%](memflops.png)] .footnote[Fuente: [John McCalpin, Memory Bandwidth and System Balance in HPC Systems](https://sites.utexas.edu/jdm4372/2016/11/22/sc16-invited-talk-memory-bandwidth-and-system-balance-in-hpc-systems/)] --- # Intensidad aritmética Para operar sobre datos es necesario transportar datos desde memoria al procesador, y viceversa. Para un problema dado, la intensidad aritmética es el ratio entre la cantidad de operaciones y los bytes transferidos para realizarlas. - Intensidad baja: Suma de dos matrices en precisión simple, `\( O(n) \)` operaciones 1 op, 12 bytes (2 lecturas, 1 escritura) por elemento = 0.083 ops/byte - Intensidad alta: Multiplicación de dos matrices `\( N x N \)` en precisión simple (optimista), `\( O(n^3) \)` operaciones `\( N^3 - N \)` ops, `\( 4 * 3 N^2 \)` bytes transferidos `\( \approx \frac{N}{12} \)` ops/byte *Para problemas de intensidad aritmética baja, el límite no es el poder de cómputo sino la capacidad de transferir datos.* --- # Roofline Performance Model Modelo del límite efectivo de un nodo de cómputo. 1. Medimos el poder de cómputo máximo (Rmax, en GFLOPS) con [HPL](https://www.netlib.org/benchmark/hpl/) * Techo para problemas de alta intensidad aritmética 2. Medimos el ancho de banda de memoria (MemBW, en GBps) con [STREAM](https://www.cs.virginia.edu/stream/) * Techo para problemas de baja intensidad aritmética 3. `\( \frac{Rmax}{MemBW} \)`: Intensidad aritmética mínima para utilizar todo el poder de cómputo del procesador 4. Graficar GFLOPS máximo respecto a la intensidad aritmética --- .center[![:scale 90%](roofline-apps.png)] .footnote[Fuente: Double-precision FPUs in High-Performance Computing: an Embarrassment of Riches?] --- # ¿Cómo procedo? - Obtener el gráfico - Sin renegar: usar Intel Advisor - Si no llegamos al techo, subir - Exprimir más el procesador (vectorización, paralelización) - Nota: El techo para problemas que no pueden usar Fused Multiply-Add (FMA) es la mitad - Si el techo nos limita, ir hacia la derecha - Aumentar la localidad del código para operar más en cache --- # Escalabilidad: Speedup **Speedup** se define como el ratio de mejora sobre una implementación de referencia: `$$ S = \frac{T_{orig}}{T_{new}} $$` Donde `\(T_{orig}\)` y `\(T_{new}\)` son tiempos de ejecución. - Se usa para comparar una implementación nueva con una de referencia, generalmente una paralela contra la secuencial original: `$$ S = \frac{T_1}{T_N} $$` --- # Escalabilidad: Eficiencia **Eficiencia** muestra cuánto perdimos de lo teóricamente posible a la práctica: `$$ \mathit{Eff} = \frac{M_{\mathit{efectivo}}}{M_{\mathit{teorico}}} $$` En el caso de paralelización: `$$\mathit{Eff} = \frac{S}{N} $$` --- .center[![:scale 100%](gromacsscale.png)] --- .center[![:scale 100%](gromacseff.png)] --- # Ley de Amdahl > …the effort expended on achieving high parallel processing rates is wasted unless it is accompanied by achievements in sequential processing rates of very nearly the same magnitude. > > — Gene Amdahl El speedup máximo obtenible agregando procesadores está acotado por la porción secuencial del código. `$$ T_N = T_1 (s + \frac{p}{N}) \hskip 6em S_N = \frac{1}{s + \frac{p}{N}} $$` .center[![:scale 80%](amdahlwork.png)] --- # Ley de Gustafson Observación: Generalmente la parte secuencial es independiente del tamaño del problema. >…speedup should be measured by scaling the problem to the number of processors, not by fixing the problem size. > >— John Gustafson Workaround: Si no escala, agrandar el problema. `$$ S_N = N - s (N - 1) $$` .center[![:scale 65%](gustafsonwork.png)] --- # Scaling **Strong scaling**: Escalabilidad de un problema de tamaño fijo respecto a la cantidad de procesadores. **Weak scaling**: Escalabilidad de un problema de **tamaño fijo por procesador** respecto a la cantidad de procesadores. --- # Profiling en general Técnicas para obtener información sobre la ejecución de un programa - Generalmente métricas con el objetivo de optimizar cuellos de botella - Dos tipos generales según cómo obtienen los datos - Los que instrumentan el código para hacer las mediciones necesarias (e.g. `gcc -pg`, luego `gprof` o `gcov`) - Los que observan el código en ejecución sin requerir modificaciones (e.g. `perf`, `VTune`...) --- # Sampling Un procesador tiene un conjunto de contadores configurables para llevar rastro de una variedad de eventos - `cpuid` los lista ``` number of fixed counters = 0x3 (3) number of counters per logical processor = 0x8 (8) ``` Se configura un contador que al hacer overflow genera una interrupción y en cada interrupción el kernel anota dónde ocurrió el evento - Pueden ser ciclos (tiempo) o eventos del procesador - Default 1 kHz, máximo `kernel.perf_event_max_sample_rate` (100 kHz) Limitaciones: - Teorema de muestreo - A muy alta frecuencia no queda tiempo para trabajo útil --- # Counting Se configuran los mismos contadores que para sampling, pero en lugar de parar cada tanto se reportan las cantidades al final Pros: - No se pierden datos - ...hasta que pedimos más metricas que los contadores disponibles Cons: - Difícil de acertarle a la etapa que queremos en programas complejos --- # Tracing A veces la muestra no alcanza, necesitamos contexto para ver de dónde venimos. Soluciones: - Capturar más información al tomar la muestra - Guardar toda la información siempre Cosas interesantes que trazar: - Call stack - Last Branch Record (acelerado en hardware) Limitaciones: - Tamaño - Overhead --- # Sanity check: `htop` Antes de hacer nada, veamos que todo esté en orden. `htop` es un `top` alternativo, features similares - Utilización desglosada de cada core - Utilización de memoria - Lista de procesos en ejecución Cosas para revisar: - Un proceso o hilo por core o hilo del procesador - No se pelea por tiempo de procesador con otros programas. --- # `perf` Herramienta de profiling asociada a la system call `perf_event_open` del kernel de Linux - No requiere instrumentación - Bajo overhead - Hace sampling, counting, tracing Permite observar: - La ejecución entera de un programa (cuando se pasa el comando) - Un proceso en ejecución pasando el PID - **Todo** lo que ocurre en todo el sistema (`-a`) --- # Primeras mediciones: `perf stat` Counting profiler. Muestra un resumen de métricas de ejecución de **todo un programa**. - Métricas por defecto - Tiempo en espacio de usuario y en kernel (como `time comando`) - Utilización de CPUs - Ciclos, instrucciones, IPC - Branches, predicciones de branches erradas - (`-ddd`) Loads de distintos niveles de cache y sus misses - Se puede configurar a mano cualquier conjunto de eventos (`-e`) y métricas basadas en eventos (`-M`) obtenidos con `perf list` - Top-down profiling con `--topdown` --- # `perf list` Lista los eventos y métricas que conoce `perf` - Hay muchos más y con mucho más detalle de lo que generalmente necesitamos - Y aún así no son todos - Herramienta con lista extendida para procesadores Intel: `ocperf` - "Metric groups" (al final) provee algunas métricas útiles ya procesadas --- # Top-down profiling .center[![:scale 100%](topdown.png)] Ahmad Yasin, Top-down Microarchitecture Analysis through Linux perf and toplev tools --- # Explorando: `perf top` Sampling de tiempo *todo el sistema* con información en tiempo real - Interfaz de texto - Reporte de utilización de CPU por función - Opción para hacer zoom en una función y ver utilización por instrucción - Si hay información de debugging, se muestra el código fuente asociado a cada instrucción también - Incluye utilización del kernel, que puede ayudar para problemas más complicados con system calls --- # Apartado: Symbol table El sampling de `perf` crea un histograma de ocurrencias de eventos por instrucción. Para sacar algo útil de esta información, necesitamos tener un mapeo entre el binario en ejecución y el código fuente. (la tabla de símbolos) - Viene con la información de debugging (compilar con `-g`) A tener en cuenta: - Algunos eventos demoran algunas instrucciones en notificarse y se le cuentan a la instrucción equivocada - Las optimizaciones más agresivas vistas ayer (inlining, LTO, transformaciones de loops) destruyen la relación 1:1 entre binario y código - Aflojarle un poco a las optimizaciones (`-O2`) para ubicarse --- # Dump de métricas: `perf record` Sampling profiler. Se configuran las métricas a observar y se inicia el profiling. `perf` vuelca los datos a `perf.data` para posterior análisis. # Análisis offline: `perf report` Interfaz similar a `perf top`, procesa y muestra lo guardado en `perf.data`. --- # `perf c2c` Sampling profiler de propósito específico. Sólo cuenta líneas de cache que han sido encontradas modificadas en un lugar remoto (HITM) - Para detectar contención sobre líneas de cache, en particular false sharing (problema común por el que OpenMP no paraleliza aunque parezca trivial) --- # Intel Advisor Profiler para asistir con vectorización y paralelización de código. Features interesantes: - Roofline analysis por función - Análisis muy específico para generar sugerencias de optimizaciones Para utilizar: 1. `source (...)/intel/advisor/advixe-vars.sh` 2. Correr el profiler - `advixe-gui` para la interfaz gráfica - `advixe-cl` para el programa de línea de comandos (para poner en jobs) --- # Intel VTune Amplifier Profiler de propósito general con interfaz gráfica amigable - Hotspots: Sampling profiler similar a `perf record` + `perf report` - Microarchitecture exploration: *top-down metrics por función* Para utilizar: 1. `source (...)/intel/vtune_amplifier/amplxe-vars.sh` 2. Correr el profiler - `amplxe-gui` para la interfaz gráfica - `amplxe-cl` para el programa de línea de comandos (para poner en jobs) --- # Profiling en Python: - cProfile - Profiler de funciones - `python -m cProfile script.py` - scalene - Profiling línea por línea de tiempo de CPU - `python -m scalene script.py`