SIMD

Presenter Notes

Resumen:

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

Nicolás Wolovick 20140401

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 -std=c99 -O1 multmap.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        454.302.503 cycles                    #    0,000 GHz                      ( +-  0,48% ) [49,18%]
 6        323.757.709 instructions              #    0,71  insns per cycle          ( +-  0,20% ) [74,60%]
 7            884.318 cache-references                                              ( +-  2,18% ) [75,85%]
 8            361.578 cache-misses              #   40,888 % of all cache refs      ( +-  1,73% ) [75,78%]
 9 
10        0,173437347 seconds time elapsed                                          ( +-  0,28% )

Presenter Notes

Paralelismo SIMD

Tiene un paralelismo trivial de grano fino. ¡Qué lo descubra el compilaror!

 1 $ gcc -std=c99 -O1 -ftree-vectorize -ftree-vectorizer-verbose=2 multmap.c && perf stat -e cycles,instructions,cache-references,cache-misses -r 3 ./a.out
 2 
 3 Analyzing loop at multmap.c:6
 4 
 5 
 6 Vectorizing loop at multmap.c:6
 7 
 8 6: LOOP VECTORIZED.
 9 multmap.c:5: note: vectorized 1 loops in function.
10 
11  Performance counter stats for './a.out' (3 runs):
12 
13        400.026.689 cycles                    #    0,000 GHz                      ( +-  1,61% ) [49,17%]
14        169.915.260 instructions              #    0,42  insns per cycle          ( +-  1,21% ) [75,36%]
15            918.045 cache-references                                              ( +-  0,72% ) [75,66%]
16            377.502 cache-misses              #   41,120 % of all cache refs      ( +-  0,43% ) [75,71%]
17 
18        0,153767320 seconds time elapsed                                          ( +-  0,91% )
  • Usamos -ftree-vectorizer-verbose=2 para que informe si pudo vectorizar.
  • -O3 incluye vectorización, pero también muchas más cosas que dificultan la lectura del assembler.

Presenter Notes

Comparación

  • 168M vs. 323M de instrucciones.
  • 0.15s vs. 0.17s de walltime.

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

Aun asi, mejora "leer ancho".

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

Presenter Notes

Por dentro

gcc -std=c99 -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 -std=c99 -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.

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

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

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

ó

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

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

Notar que NO se puede hacer unpcklps, unpckhps con shufps.

(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. Empacketadas.

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

Todas tienen un 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.

Presenter Notes

Comparaciones

cpm y flia

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

Presenter Notes

Bitwise