class: center, middle # Computación Paralela # ISPC 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%]()] --- # ISPC [Intel SPMD Program Compiler](https://ispc.github.io/) - Lenguaje y compilador creado por Matt Pharr mientras trabajaba en Intel - Basado en LLVM - Genera código para SSE2, AVX, AVX2, AVX512, AArch64 [Blog posts sobre su historia](https://pharr.org/matt/blog/2018/04/18/ispc-origins.html) --- # ISPC (lenguaje) - Basado en C99 más algunas cosas de C++ - Referencias, overloading, `new/delete` - **Single Program, Multiple Data** - `programCount` instancias del **mismo programa** (múltiplo de la longitud del vector) corren en simultáneo la misma instrucción **sobre distintos datos** - `programIndex` devuelve el índice de la instancia `\( \mathtt{programIndex} \in [0, \mathtt{programCount}) \)` - Dos calificadores nuevos para las variables - `varying`: Vector, pueden valer distinto para cada instancia - `programIndex` es `varying` - `uniform`: Dato escalar, vale lo mismo para todas las instancias - `programCount` es `uniform` - Operaciones mixtas devuelven `varying` --- # Empezando ```ispc export void vector_add(const uniform float * uniform a, const uniform float * uniform b, uniform float * uniform c, uniform int n) { for (uniform int base = 0; base < n; base += programCount) { // base = [ i i i ... i ] varying int index = base + programIndex; // index = [ i+0 i+1 i+2 ... i+programCount-1 ] varying float result = a[index] + b[index]; // result = [ a[i+0]+b[i+0] a[i+1]+b[i+1] a[i+2]+b[i+2] ... ] c[index] = result; } } ``` Problema: `index` se puede ir de rango --- # Aclaraciones - Punteros raros - `uniform float * uniform ptr`: Un único puntero a un elemento singular (C típico) - `varying float * uniform ptr`: Un único puntero a `programCount` elementos - `uniform float * varying ptr`: `programCount` punteros a un elemento cada uno. - `varying float * varying ptr`: `programCount` punteros a `programCount` elementos cada uno - Accesos a direcciones no secuenciales generan gathers o scatters - `export` indica que la función se llama desde afuera - Todos los parámetros deben ser `uniform` - ISPC genera un header C con la interfaz de esta función --- # Control de flujo En un branch ISPC genera una máscara y sólo opera sobre las instancias que evaluaron a verdadero, que son las activas. - Barato en AVX-512, no tanto en anteriores - Optimización: `cif` (coherent `if`) cuando uno espera que todas las instancias tomen el branch - `foreach_active` itera **secuencialmente** sobre los índices de las instancias activas. --- # Bounds check ```ispc void vector_add(const uniform float * uniform a, const uniform float * uniform b, uniform float * uniform c, uniform int n) { for (uniform int base = 0; base < n; base += programCount) { varying int index = base + programIndex; if (index < n) { varying float result = a[index] + b[index]; c[index] = result; } } } ``` Problema: Cálculo de máscara en todas las iteraciones. --- # Peeling de la iteración insegura ```ispc void vector_add(const uniform float * uniform a, const uniform float * uniform b, uniform float * uniform c, uniform int n) { uniform int base; // Loop vectorial donde no necesito verificar nada for (base = 0; base < n - n % programCount; base += programCount) { varying int index = base + programIndex; varying float result = a[index] + b[index]; c[index] = result; } // Loop escalar para los últimos n % programCount elementos for (; base < n; ++base) { uniform float result = a[base] + b[base]; c[base] = result; } } ``` --- # Syntax sugar - Las variables son `varying` por defecto - `foreach (i = desde ... hasta)` genera un `const varying int32 i` que itera de forma óptima en el rango `[desde,hasta-1]` - No se pueden anidar, usar `foreach (i=d0...h0, j=d1...h1)` que itera más rápido sobre `i` - Loop tiling: `foreach_tiled` reparte las instancias de la forma más cercana posible a un cuadrado sin partir vectores ```ispc void vector_add(const uniform float * uniform a, const uniform float * uniform b, uniform float * uniform c, uniform int n) { foreach (index = 0 ... n) { float result = a[index] + b[index]; c[index] = result; } } ``` --- # Reducción ```ispc export uniform float reduce(const uniform float * uniform v, uniform int n) { float partial_sum = 0.0f; foreach (i = 0 ... n) { partial_sum += v[i]; } // TODO: ¿Y ahora qué hago con partial_sum? return gang_reduce(partial_sum); } ``` --- # Movimiento de datos - `T broadcast(T v, uniform int index)`: Copia el valor de `v` en la instancia `index` al resto - `T shift(T v, uniform int offset)`: Desplaza el valor de cada instancia `i` a la instancia `i+offset` - `T rotate(T v, uniform int offset)`: Rota el valor de cada instancia `i` a la instancia `(i+offset) % programCount` - `T shuffle(T v, int from)`: Trae a cada instancia el valor `v` de la instancia `from` - `T insert(T v, uniform int index, uniform T x)`: Reemplaza el valor de `v` en la instancia `index` por `x` - `uniform T extract(T v, uniform int index)`: Devuelve el valor `v` de la instancia `index` --- # Reducción de `partial_sum` ```ispc uniform float gang_reduce(float partial_sum) { uniform float sum = 0.0f; for (uniform int i = 0; i < programCount; ++i) { sum += extract(partial_sum, i); } return sum; } ``` - **O(programCount)** instrucciones. - ¡Código escalar! --- # Reducción rápida ```ispc uniform float gang_reduce(float partial_sum) { float sum = partial_sum; for (uniform int s = programCount / 2; s > 0; s /= 2) { // Ej. programCount == 4 // inicial: a b c d // +shift -2: a+c b+d c d // +shift -1: a+b+c+d b+c+d c+d d sum += shift(sum, -s); } return extract(sum, 0); } ``` - **O(log programCount)** instrucciones. - Ojo: Este loop actualmente genera código lento por un problema de ISPC. - La biblioteca estándar tiene `reduce_add` para calcularlo. - Alternativa: Desenrollar el loop a mano. (feo) --- # Biblioteca estándar - Aritmética entera - Partes de `
` - PRNG básico - Reducción, scan - Streaming loads/stores - Atomics, barreras - Conversiones AoS - SoA --- # Recursos - [ISPC User's Guide](https://ispc.github.io/ispc.html) - [ISPC Performance Guide](https://ispc.github.io/perfguide.html) - P. Brubaker, J. Kennedy, [Simple SIMD Using ISPC](https://www.gdcvault.com/play/1026201/), GDC 2019. - J. Amstutz, D. Babokin, P. Brubaker, [Advanced SIMD Programming with the Intel ISPC Compiler](https://software.intel.com/en-us/videos/advanced-single-instruction-multiple-data-simd-programming-with-intel-implicit-spmd-program), SIGGRAPH 2019. - M. Pharr, W. R. Mark, [ispc: A SPMD Compiler for High-Performance CPU Programming](https://github.com/downloads/ispc/ispc/ispc_inpar_2012.pdf), InPar 2012.