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

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

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

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

Necesita 8 instrucciones y 4 registros.

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.

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

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.

Recién en AVX2 hay gatherps, storeu2, reales.
(el Talón de Aquiles de todo esto)

Presenter Notes

Ejemplos sencillo

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

Patterson, Hennessy Computer Organization and Design, Fifth Edition, Morgan Kaufmann, 2012.
Intel, Intel Intrinsics Guide, 2014.
Song Ho Ahn, SSE (Streaming SIMD Extentions), 2005.
Mostafa Hagog, Looking for 4x speedups? SSE™ to the rescue!, Intel, 2006.
Jan Finis, x86 Intrinsics Cheat Sheet, v2.1.

Presenter Notes

La clase que viene

Ejemplos más complejos de SIMD.

Table of Contents	t
Exposé	ESC
Full screen slides	e
Presenter View	p
Source Files	s
Slide Numbers	n
Toggle screen blanking	b
Show/hide slide context	c
Notes	2
Help	h

SSSE3

Multiplicación punto a punto c = a*b

Operaciones +, -, *, min, max

Notar

Prefetch de la memoria en cache

Orden en la memoria

Ejercicio

Ejemplo

Usando blend

Ejercicio

Internamente

Table of Contents

Help

`SSSE3`

Multiplicación punto a punto `c = a*b`

Usando `blend`