class: center, middle # Computación Paralela # Compiladores Carlos Bederián, [carlos.bederian@unc.edu.ar](mailto:carlos.bederian@unc.edu.ar) Nicolás Wolovick, [nicolasw@famaf.unc.edu.ar](mailto:nicolasw@famaf.unc.edu.ar) .center[![:scale 100%](lowhanging.jpg)] --- # Motivación - En HPC se puede llegar relativamente lejos con poco trabajo - Buen uso de las herramientas disponibles - Paralelización con directivas - Bibliotecas - ¡Y se puede llegar a ninguna parte después de mucho trabajo! - "Optimizar" **todo** a mano - Hoy: Mejorar performance fácilmente con el compilador - Y todos los rabbit holes donde no meterse --- # Compiladores modernos 1. Front end que convierte el código en un lenguaje particular a una representación intermedia (IR) - Preprocesador - Análisis léxico - Análisis sintáctico - Análisis semántico 2. Middle end que transforma la representación intermedia - Análisis y optimización 3. Back end que transforma IR a la arquitectura destino - Optimización para la arquitectura - Generación de código --- # GCC Clásica suite de compiladores de GNU - Iniciado en 1987 por Richard Stallman - Licencia GPL (copyleft) - Front ends: Ada, C, C++, D, Fortran, Go, Objective-C... - Back ends: Soporta prácticamente cualquier arquitectura popular - Última versión: GCC 9.3.0 (marzo 2020) .right[![:scale 40%](gcc.png)] --- # LLVM Colección modular de tecnología para compiladores - Iniciado en 2003 por Chris Lattner - Licencia UIUC/NCSA - Altamente modular, resulta en proliferación de compiladores, intérpretes y lenguajes - DragonEgg: Reemplazo de middle-end y back-end de GCC - Clang (Apple), compilador completo para C, C++, Objective-C - Compatible con GCC en parámetros y extensiones por diseño - Fortran, CUDA, ISPC, Julia, OpenCL, OpenGL, Rust, Swift... - Soporte de arquitecturas generalmente provisto por los fabricantes - Aunque no siempre en código abierto - Última versión: LLVM 10.0 (marzo 2020) --- # Intel Suite propietaria de compiladores para HPC - Propietario - *Caro* (para nosotros) - Licencias especiales para estudiantes, proyectos open source, educadores - C, C++, Fortran - Optimizado para arquitecturas Intel - ...y a veces ofuscado para AMD - Última versión: Parallel Studio XE 2020 (diciembre 2019) --- # Consiguiendo compiladores Cada versión nueva de un compilador tiene: - Bugfixes - Soporte de versiones nuevas de lenguajes en el front end - Más o mejores optimizaciones Formas de obtener la última versión: - Esperar una nueva versión de la distribución de linux - Usar repositorios third-party - Bajarlo y compilarlo - Spack, Easybuild --- # Proebsting's Law > Compiler technology doubles CPU power every 18 years > > This means that while hardware computing horsepower increases at roughly 60%/year, compiler optimizations contribute only 4%. Basically, compiler optimization work makes only marginal contributions. > > Perhaps this means Programming Language Research should be concentrating on something other than optimizations. Perhaps programmer productivity is a more fruitful arena. \- Todd Proebsting, Microsoft Research, 1998 --- # El programa óptimo - Problema NP-completo o indecidible - ...y muy poco tiempo para intentar cosas - Solución parcial: heurísticas - No siempre aciertan - Generalmente conservadoras para prevenir peor código .center[![:scale 40%](compiling.png)] --- # Optimizaciones - La representación intermedia está en **static single assignment (SSA) form** que facilita la optimización - Cada variable se asigna una única vez - Transformaciones de código por otro equivalente a distintas escalas - Peephole (ventana pequeña de instrucciones) - Local (bloque básico) - Flujo de programa (loops y branches) - Global (función) - Interprocedural --- # Bloques básicos Nodo del grafo de flujo del programa, con código sin ramificaciones ni loops. .center[![:scale 40%](basicblock.png)] --- # Debajo del capot: GIMPLE `gcc -c -fdump-tree-gimple ir.c` ```c int j,k,m,n; while (j
;
: _1 = j * 2; k = k + _1; m = j * 2; j = j + 1;
: if (j < n) goto
; else goto
;
:``` --- #Debajo del capot: LLVM IR ```llvm %1 = alloca i32, align 4 %2 = alloca i32, align 4 %3 = alloca i32, align 4 %4 = alloca i32, align 4 br label %5 ;
:5: ; preds = %9, %0 %6 = load i32, i32* %1, align 4 %7 = load i32, i32* %4, align 4 %8 = icmp slt i32 %6, %7 br i1 %8, label %9, label %18 ;
:9: ; preds = %5 %10 = load i32, i32* %2, align 4 %11 = load i32, i32* %1, align 4 %12 = mul nsw i32 %11, 2 %13 = add nsw i32 %10, %12 store i32 %13, i32* %2, align 4 %14 = load i32, i32* %1, align 4 %15 = mul nsw i32 %14, 2 store i32 %15, i32* %3, align 4 %16 = load i32, i32* %1, align 4 %17 = add nsw i32 %16, 1 store i32 %17, i32* %1, align 4 br label %5 ;
:18: ; preds = %5 ``` --- # Compiler Explorer Sitio que permite ver inmediatamente la salida generada por distintos compiladores. [Compiler Explorer](https://godbolt.org/) --- # Strength reduction, instruction combining Reemplazo de expresiones por otras equivalentes con menor costo computacional ||| |--------------|----------------| | `4 * a` | `a << 2` | | `n % 2 == 0` | `n & 1 == 0` | | `i++; i++` | `i += 2` | | `x = 0` | `x = x^x` | | `for (i=0; i