SIMD

Presenter Notes

Resumen:

  • Motivación.
  • SSE Intrinsics.
  • Ejemplos sencillos.

Nicolás Wolovick 20160407

Presenter Notes

SIMD

Single Instruction Multiple Data

SIMD en la Flynn's taxonomy

Nos vamos a concentrar en una versión particular.

SSSE3

  • Circa 2006.
  • Core 2 Duo.

Presenter Notes

Motivación

Multiplicación punto a punto c = a*b

1 #define N (1<<25)
2 float a[N], b[N], c[N];
3 int main(void) {
4     for (unsigned int i=0; i<N; ++i) {
5         a[i] = b[i]*c[i];
6     }
7 }

Compilamos y ejecutamos.

 1 $ gcc -O1 multmap.c && perf stat -e cycles,instructions,cache-references,cache-misses -r 16 ./a.out
 2 
 3  Performance counter stats for './a.out' (16 runs):
 4 
 5 267,858,747   cycles                                                   ( +-  0.14% )
 6 310,616,425   instructions         #    1.16  insns per cycle          ( +-  0.03% )
 7     288,130   cache-references                                         ( +-  1.23% )
 8     181,542   cache-misses         #   63.007 % of all cache refs      ( +-  0.76% )
 9 
10 0.152007928 seconds time elapsed                                       ( +-  0.43% )

Presenter Notes

Paralelismo SIMD

Tiene un sencillo paralelismo de grano fino. ¡Qué lo descubra el compilador!

 1 $ gcc -O1 -ftree-vectorize -fopt-info-vec multmap.c && perf stat -e cycles,instructions,cache-references,cache-misses -r 16 ./a.out
 2 multmap.c:6:2: note: loop vectorized
 3 
 4 Performance counter stats for './a.out' (16 runs):
 5 
 6    231,978,316  cycles                                                    ( +-  0.37% )
 7    159,692,799  instructions          #    0.69  insns per cycle          ( +-  0.09% )
 8        284,584  cache-references                                          ( +-  1.68% )
 9        179,267  cache-misses          #   62.993 % of all cache refs      ( +-  1.14% )
10 
11        0.132852903 seconds time elapsed                                      ( +-  1.72% )
  • Usamos -fopt-info-vec para ver si pudo vectorizar.
  • Usamos -fopt-info-vec-missed para ver que NO pudo vectorizar.
  • -O3 incluye vectorización, pero también muchas más cosas que dificultan la lectura del assembler.

-ftree-vectorizer-verbose=2 para gcc-4.8 y menores.

Presenter Notes

Comparación

  • 159M vs. 310M de instrucciones.
  • 0.13s vs. 0.15s de walltime.

Código absolutamente memory-bound con intensidad aritmética de 1 FLOP/ 8 bytes.

Aun asi, mejora "leer ancho".

Looking for 4x speedups? SSE™ to the rescue!

Mostafa Hagog, Looking for 4x speedups? SSE™ to the rescue!, Intel, 2006.

Presenter Notes

Por dentro

gcc -S -O1 multmap.c

1 .L2:
2     movss   b(%rax), %xmm0
3     mulss   c(%rax), %xmm0
4     movss   %xmm0, a(%rax)
5     addq    $4, %rax
6     cmpq    $134217728, %rax
7     jne .L2

gcc -S -O1 -ftree-vectorize multmap.c

1 .L2:
2     movaps  b(%rax), %xmm0
3     mulps   c(%rax), %xmm0
4     movaps  %xmm0, a(%rax)
5     addq    $16, %rax
6     cmpq    $134217728, %rax
7     jne .L2

Notar:

  • %rax va 4 veces más rápido (repite lazo 4x menos).
  • Usa instrucciones con ps: packed single.
  • Usar -O2 y ver como reordena instrucciones.

Presenter Notes

SSE Intrinsics

Presenter Notes

Registros SSE3

x86_64 all registers

Presenter Notes

Tipos de Datos para xmm{0..15}

  • __m128: 4 flotantes.
  • __m128d: 2 dobles.
  • __m128i: 16 bytes, 8 shorts, 4 ints, 2 longs.

SSE2 datatypes

Presenter Notes

Operaciones SSSE3

  • Construcción.
  • Acceso a memoria.
  • Movimientos (shuffles).
  • Aritméticas: básicas, especiales (y caras).
  • Lógicas.
  • Comparación.
  • Macros.
  • Horizontales.

Presenter Notes

Para usarlo

 1 #include <mmintrin.h>  // MMX
 2 #include <xmmintrin.h> // SSE
 3 #include <emmintrin.h> // SSE2
 4 #include <pmmintrin.h> // SSE3
 5 #include <tmmintrin.h> // SSSE3
 6 #include <smmintrin.h> // SSE4.1
 7 #include <nmmintrin.h> // SSE4.2
 8 #include <ammintrin.h> // SSE4A
 9 #include <wmmintrin.h> // AES
10 #include <immintrin.h> // AVX, AVX2

ó

1 #include <x86intrin.h> // el que sea necesario

Presenter Notes

Construcción

Copiar un valor a las 4 componentes.

1 __m128 _mm_set1_ps (float a)

Establece las 4 componentes.

1 __m128 _mm_setr_ps (float e3, float e2, float e1, float e0)

Presenter Notes

Ejemplo

 1 #include <xmmintrin.h>
 2 #include <stdio.h>
 3 
 4 __m128 ta;
 5 
 6 void main(void) {
 7     __m128 tb = _mm_setr_ps(1.0f, 2.0f, 3.0f, 4.0f);
 8     ta = _mm_add_ps(ta, tb);
 9     printf("%f %f %f %f\n", ta[0], ta[1], ta[2], ta[3]);
10 }

Ejecutamos

1 $ $ gcc -O1 store_load.c && ./a.out
2 1.000000 2.000000 3.000000 4.000000

Notar: __m128 v se puede acceder como si fuera float v[4].

Presenter Notes

Acceso a memoria

1 __m128 _mm_loadl_pi (__m128 a, __m64 const* mem_addr) // movlps
2 void _mm_store_ps (float* mem_addr, __m128 a) // movaps

Songho sse08 Memoria

Más

1 __m128 _mm_loadh_pi (__m128 a, __m64 const* mem_addr) // movhps
2 __m128d _mm_loadh_pd (__m128d a, double const* mem_addr) // movhpd
3 void _mm_store_pd (double* mem_addr, __m128d a) // movapd

Presenter Notes

Acceso a memoria

Este intrinsic se mapea a una instrucción movaps.

_mm_load_ps

(Intel Intrinsics Guide)

Presenter Notes

Acceso a memoria

En este caso tenemos dos: movss + shufps.

_mm_load_ps1

(Intel Intrinsics Guide)

Presenter Notes

Movimientos

1 __m128 _mm_movelh_ps (__m128 a, __m128 b) // movlhps

movelhps

1 __m128 _mm_unpacklo_ps (__m128 a, __m128 b) // unpcklps

unpcklps, unpckhps

También está _mm_movehl_ps (movhlps).

Presenter Notes

Shuffles

1 __m128 _mm_shuffle_ps (__m128 a, __m128 b, unsigned int imm) // shufps

_mm_shuffle_ps

NO se puede hacer unpcklps, unpckhps con shufps

Presenter Notes

Shuffles, todos

(Franz Franchetti and Markus Püschel, Generating SIMD Vectorized Permutations, 2008.)

Presenter Notes

Shuffles: swap, rotate

swap

rotate

Presenter Notes

Aritméticas Básicas

Escalares vs. Empaquetadas

Operaciones +, -, *, min, max

1 __m128 _mm_add_ps (__m128 a, __m128 b) // addps
2 __m128 _mm_sub_ps (__m128 a, __m128 b) // subps
3 __m128 _mm_mul_ps (__m128 a, __m128 b) // mulps
4 __m128 _mm_min_ps (__m128 a, __m128 b) // minps
5 __m128 _mm_max_ps (__m128 a, __m128 b) // maxps
  • latencia de 3 ciclos
  • throughput de 1 ciclo.

Presenter Notes

Aritméticas Caras

1 __m128 _mm_div_ps (__m128 a, __m128 b) // divps
2 __m128 _mm_rcp_ps (__m128 a) // rcpps
3 __m128 _mm_sqrt_ps (__m128 a) // sqrtps
4 __m128 _mm_rsqrt_ps (__m128 a) // rsqrtps

Notar

  • divps tiene throughput de 14 ciclos en Sandy Bridge, mulps y rcpps de 1.
  • sqrtps tiene throughput de 14 ciclos en Sandy Bridge, rsqrtps de 1.

Comparación de div y rcp en diferentes arquitecturas

Presenter Notes

Comparaciones

1 __m128 _mm_cmpeq_ps (__m128 a, __m128 b) // cmpps
2 __m128 _mm_cmpneq_ps (__m128 a, __m128 b) // cmpps
3 __m128 _mm_cmplt_ps (__m128 a, __m128 b) // cmpps
4 __m128 _mm_cmpnlt_ps (__m128 a, __m128 b) // cmpps

Semántica gráfica

cpm y flia

Semántica como programa

1 FOR j := 0 to 3
2     i := j*32
3     dst[i+31:i] := ( a[i+31:i] == b[i+31:i] ) ? 0xffffffff : 0
4 ENDFOR

Presenter Notes

Bitwise

1 __m128 _mm_and_ps (__m128 a, __m128 b) // andps
2 __m128 _mm_or_ps (__m128 a, __m128 b) // orps
3 __m128 _mm_xor_ps (__m128 a, __m128 b) // xorps
4 __m128 _mm_andnot_ps (__m128 a, __m128 b) // andnps

Presenter Notes

Conversión

conversion

1 int _mm_cvtss_si32 (__m128 a) // cvtss2si
2 __m128 _mm_cvtsi32_ss (__m128 a, int b) // cvtsi2ss
3 __m64 _mm_cvtps_pi32 (__m128 a) // cvtps2pi
4 __m128 _mm_cvtpi32_ps (__m128 a, __m64 b) // cvtpi2ps

Y otras cosas sencillas como tomar el primer elemento y devolver un float.

1 float _mm_cvtss_f32 (__m128 a) // movss

Presenter Notes

Cosas raras con la memoria

Prefetch de la memoria en cache

1 void _mm_prefetch (char const* p, int i) // prefetchnta, prefetcht0, prefetcht1, prefetcht2
  • El parámetro i es un hint para decirle a donde queremos que vaya a parar: L1, L2, L3.
  • ¡Se usa!

Orden en la memoria

1 void _mm_lfence (void) // lfence
2 void _mm_sfence (void) // sfence
3 void _mm_mfence (void) // mfence

Presenter Notes

Aritmética horizontal

1 __m128 _mm_addsub_ps (__m128 a, __m128 b)

Input: { A0, A1, A2, A3 }, { B0, B1, B2, B3 }
Output: { A0 - B0, A1 + B1, A2 - B2, A3 + B3 }

1 __m128 _mm_hsub_ps (__m128 a, __m128 b)

Input: { A0, A1, A2, A3 }, { B0, B1, B2, B3 }
Output: { A0 - A1, A2 - A3, B0 - B1, B2 - B3 }

1 __m128 _mm_hadd_ps (__m128 a, __m128 b)

Input: { A0, A1, A2, A3 }, { B0, B1, B2, B3 }
Output: { A0 + A1, A2 + A3, B0 + B1, B2 + B3 }

Ejercicio

¿Cómo sumo las 4 compontentes de un __m128?

Presenter Notes

Macros

Transpuesta 4x4

1 _MM_TRANSPOSE4_PS (__m128 row0, __m128 row1, __m128 row2, __m128 row3)

Necesita 8 instrucciones y 4 registros.

Armar bits para _mm_shuffle_ps

1 _MM_SHUFFLE(z, y, x, w)
2 // expands to the following value (z<<6) | (y<<4) | (x<<2) | w

Ejemplo

Broadcast el elemento 1 del vector, aka _mm_load_ps1.

1 _mm_shuffle_ps(v, v, _MM_SHUFFLE(1,1,1,1))

Presenter Notes

(De acá en adelante SSE4.1)

Presenter Notes

Blend (copia condicional)

1 __m128 _mm_blend_ps (__m128 a, __m128 b, const int imm) // blendps

  • Es un conditional move componente a componente.
  • Codifica un if sencillo.
  • Evita el flujo divergente.

Presenter Notes

Flujo divergente

1 for (i=0; i<N; ++i) {
2     if (a[i]<b[i])
3         c[i]=a[i]*b[i];
4     else
5         c[i]=a[i];
6 }

Usando blend

1 for (i=0; i<N; i+=4){
2     A = _mm_load_ps(&a[i]);
3     B = _mm_load_ps(&b[i]);
4     C = _mm_mul_ps (A, B);
5     mask = _mm_cmplt_ps (A, B);
6     C = _mm_blend_ps (C, A, mask);
7     _mm_store_ps (&c[i], C);
8 }

Presenter Notes

Producto punto condicional

1 __m128 _mm_dp_ps (__m128 a, __m128 b, const int imm) // dpps

Ejercicio

¿Cómo se hace un producto punto en SSE3?

Presenter Notes

Gather/Scatter

1 __m128 _mm_insert_ps (__m128 a, __m128 b, const int imm) // insertps
2 int _mm_extract_ps (__m128 a, const int imm) // extractps

Escribe/lee elementos individualmente.
Anterior a SSE4.1, muchas instrucciones de shuffling.

AVX2 agrega gather _mm256_i32gather_epi32

1 FOR j := 0 to 7
2     i := j*32
3     dst[i+31:i] := MEM[base_addr + SignExtend(vindex[i+31:i])*scale]
4 ENDFOR
5 dst[MAX:256] := 0

AVX512F agrega scatter _mm256_i32scatter_ps

1 FOR j := 0 to 7
2     i := j*32
3     MEM[base_addr + SignExtend(vindex[i+31:i])*scale] := a[i+31:i]
4 ENDFOR

(con Skylake-S, ¿Alguno de los i7-6700?)

Presenter Notes

Ejemplos sencillos

Presenter Notes

Ejemplo, multmap a mano

El código armado a mano con intrinsics de C.

 1 #include <xmmintrin.h>
 2 #define N (1<<25)
 3 float a[N], b[N], c[N];
 4 
 5 void main(void) {
 6     for (unsigned int i=0; i<N; i+=4) {
 7         __m128 ta = _mm_load_ps(&a[i]);
 8         __m128 tb = _mm_load_ps(&b[i]);
 9         __m128 tc = _mm_mul_ps(ta, tb);
10         _mm_store_ps(&c[i], tc);
11     }
12 }

Podríamos haber hecho un one-liner con los operadores prefijos en vez de infijos.

1 for (unsigned int i=0; i<N; i+=4)
2     _mm_store_ps(&c[i], _mm_mul_ps(_mm_load_ps(&a[i]), _mm_load_ps(&b[i])));

Pero quiero ser como René Lavard:

"no se puede hacer más lento"

Presenter Notes

Medición

 1 $ gcc -O1 multmap_quadload.c && perf stat -e cycles,instructions,cache-references,cache-misses -r 3 ./a.out
 2 
 3  Performance counter stats for './a.out' (3 runs):
 4 
 5        408.215.203 cycles                    #    0,000 GHz                      ( +-  5,94% ) [49,80%]
 6        190.947.933 instructions              #    0,47  insns per cycle          ( +-  3,37% ) [75,25%]
 7            905.136 cache-references                                              ( +-  4,67% ) [76,07%]
 8            348.820 cache-misses              #   38,538 % of all cache refs      ( +-  1,84% ) [74,87%]
 9 
10        0,156784760 seconds time elapsed                                          ( +-  5,28% )

Funciona igual que el vectorizador.

Internamente

1 .L2:
2     movl    %eax, %edx
3     movaps  a(,%rdx,4), %xmm0
4     mulps   b(,%rdx,4), %xmm0
5     movaps  %xmm0, c(,%rdx,4)
6     addl    $4, %eax
7     cmpl    $33554432, %eax
8     jne .L2

Presenter Notes

Bibliografía

Presenter Notes

Bibliografía

Presenter Notes

La clase que viene

  • Ejemplos más complejos de SIMD.

Presenter Notes