Nicolás Wolovick 20200318
x86_64
1 void store(double *a, double *b, double *c) {
2 *c = *a + *b;
3 }
$ gcc-10 -S store.c
1 store:
2 LFB0:
3 .cfi_startproc
4 pushq %rbp
5 .cfi_def_cfa_offset 16
6 .cfi_offset 6, -16
7 movq %rsp, %rbp
8 .cfi_def_cfa_register 6
9 movq %rdi, -8(%rbp)
10 movq %rsi, -16(%rbp)
11 movq %rdx, -24(%rbp)
12 movq -8(%rbp), %rax
13 movsd (%rax), %xmm1
14 movq -16(%rbp), %rax
15 movsd (%rax), %xmm0
16 addsd %xmm1, %xmm0
17 movq -24(%rbp), %rax
18 movsd %xmm0, (%rax)
19 nop
20 popq %rbp
21 .cfi_def_cfa 7, 8
22 ret
23 .cfi_endproc
Notar como pone y saca las cosas del stack
plata$ gcc-10 -S -O1 store.c
-- Intel Penryn, 2008
1 store:
2 .LFB0:
3 .cfi_startproc
4 movsd (%rdi), %xmm0
5 addsd (%rsi), %xmm0
6 movsd %xmm0, (%rdx)
7 ret
8 .cfi_endproc
jupiterace$ gcc-10 -S -O1 -march=native store.c
-- Intel Haswell, 2013
1 store:
2 .LFB0:
3 .cfi_startproc
4 vmovsd (%rdi), %xmm0
5 vaddsd (%rsi), %xmm0, %xmm0
6 vmovsd %xmm0, (%rdx)
7 ret
8 .cfi_endproc
plata$ gcc-10 -S -O1 -m32 store.c
1 store:
2 .LFB0:
3 .cfi_startproc
4 movl 4(%esp), %eax
5 fldl (%eax)
6 movl 8(%esp), %eax
7 faddl (%eax)
8 movl 12(%esp), %eax
9 fstpl (%eax)
10 ret
11 .cfi_endproc
$ aarch64-linux-gnu-gcc -S -O1 -march=armv8.2-a store.c
1 store:
2 .LFB0:
3 .cfi_startproc
4 ldr d0, [x0]
5 ldr d1, [x1]
6 fadd d0, d0, d1
7 str d0, [x2]
8 ret
9 .cfi_endproc
56 arquitecturas (similares) en una:
1 $ gcc-10 -S -O1 -m32 -march=? store.c
2
3 cc1: error: bad value (‘?’) for ‘-march=’ switch
4
5 cc1: note: valid arguments to ‘-march=’ switch are: i386 i486 i586 pentium
6 lakemont pentium-mmx winchip-c6 winchip2 c3 samuel-2 c3-2 nehemiah
7 c7 esther i686 pentiumpro pentium2 pentium3 pentium3m pentium-m
8 pentium4 pentium4m prescott nocona core2 nehalem corei7 westmere
9 sandybridge corei7-avx ivybridge core-avx-i haswell core-avx2 broadwell
10 skylake skylake-avx512 cannonlake icelake-client icelake-server cascadelake
11 tigerlake cooperlake bonnell atom silvermont slm goldmont goldmont-plus
12 tremont knl knm geode k6 k6-2 k6-3 athlon athlon-tbird athlon-4 athlon-xp
13 athlon-mp x86-64 eden-x2 nano nano-1000 nano-2000 nano-3000 nano-x2 eden-x4
14 nano-x4 k8 k8-sse3 opteron opteron-sse3 athlon64 athlon64-sse3 athlon-fx
15 amdfam10 barcelona bdver1 bdver2 bdver3 bdver4
16 znver1 znver2 btver1 btver2 native
native
significa "Mirá el CPUID y compilá para eso".C
a GAS
High amounts of compute need large amounts of state to compensate for memory BW. AVX512 has 8x state compared to SSE (conmensurate with its 8x FLOPS level)
Ian Cutress, The Intel Skylake-X Review: Core i9 7900X, i7 7820X and i7 7800X Tested, Anandtech, June 2017.
1 #include <math.h>
2
3 struct point {
4 double x;
5 double y;
6 };
7
8 double
9 max_dist(struct point const *a, const unsigned int size) {
10 double result = 0.0;
11 unsigned int i = 0;
12 for(i=0; i<size; ++a, ++i) {
13 double dst = 0.0;
14 dst = sqrt((a->x * a->x) + (a->y * a->y));
15 if (dst>result)
16 result = dst;
17 }
18 return result;
19 }
clang-9 -S -O1 -fno-math-errno
¿Porqué -fno-math-errno
?
1 max_dist: # @max_dist
2 .cfi_startproc
3 # %bb.0:
4 testl %esi, %esi
5 je .LBB0_1
6 # %bb.2:
7 xorpd %xmm1, %xmm1
8 .p2align 4, 0x90
9 .LBB0_3: # =>This Inner Loop Header: Depth=1
10 movsd (%rdi), %xmm0 # xmm0 = mem[0],zero
11 movsd 8(%rdi), %xmm2 # xmm2 = mem[0],zero
12 mulsd %xmm0, %xmm0
13 mulsd %xmm2, %xmm2
14 addsd %xmm0, %xmm2
15 xorps %xmm0, %xmm0
16 sqrtsd %xmm2, %xmm0
17 maxsd %xmm1, %xmm0
18 addq $16, %rdi
19 movapd %xmm0, %xmm1
20 addl $-1, %esi
21 jne .LBB0_3
22 # %bb.4:
23 retq
24 .LBB0_1:
25 xorps %xmm0, %xmm0
26 retq
compilar esto con clang-9 -O2
y gcc-10
y ver que hace. Probar con -march=haswell -O3 -ffast-math
. También con -march=knl
o -march=znver2
x86_64
-S
y mirar el .s
.-O1
que es el más legible.-march= ...
para diferentes sub-arquitecturas.aarch64-linux-gnu-gcc-9
, powerpc64-linux-gnu-gcc-9
, riscv-linux-gnu-gcc-9
.x86_64
1 while (1) {
2 Fetch(PC); Decode;
3 Read Inputs; Execute; Write Output;
4 Next PC;
5 }
CPI: Cycles Per Instruction IPC: 1/CPI: Instructions Per Cycle.
CPI = 1, pero ciclos lentos.
Alternativa: Ejecución Multiciclo.
MIPS (Microprocessor without Interlocked Pipelined Stages), 1984.
Pipelining implementa la primera forma de ILP.
Supone que insn1; insn2; insn3; ...
son independientes.
Procesadores avanzados de fines de 80's: Cray XMP
, NEC SX
, 80486
.
Ejemplo sencillo:
Paralelismo entre las fases de la línea de montaje.
¿Y si hay dependencia secuencial? -> Data Hazard
1 a = b+c;
2 d = a*a;
La instrucción 2
tiene que esperar que la 1
termine de operar.
PC
, luego también es dependencia de datos!).Stalls: inyecta burbujas en el pipeline para mantener la semántica secuencial.
←
)1 LD *R1*, 45(R2)
2 DADD R5, R6, R7
3 DSUB R8, R6, R7
4 OR R9, R6, R7
1 LD *R1*, 45(R2)
2 DADD R5, *R1*, R7
3 DSUB R8, R6, R7
4 OR R9, R6, R7
1 LD *R1*, 45(R2)
2 DADD R5, R6, R7
3 DSUB R8, *R1*, R7
4 OR R9, R6, R7
1 LD *R1*, 45(R2)
2 DADD R5, R6, R7
3 DSUB R8, R6, R7
4 OR R9, *R1*, R7
(Hennessy, Patterson, Computer Architecture ...)
Dependencia: clausura transitiva de la relación binaria depende-de.
Es una propiedad del programa.
La implementación del pipeline determina cuantos stalls se producen.
Loop típico
1 for (int i=0; i<N; ++i) {
2 a[i] = a[i] * 17;
3 }
Lo extiendo un poco, el for
es un azúcar sintáctico.
1 int i = 0;
2 while (i<N) {
3 a[i] = a[i] * 17;
4 ++i;
5 }
La línea 3
depende de la 4
cuando da la vuelta.
Fuerza secuencialidad
1 for (int i=0; i<N; i+=2) { // supongo N%2==0
2 a[i] = a[i] * 17;
3 a[i+1] = a[i+1] * 17;
4 }
Compilado con AVX2: gcc-10 -O1 -S -march=haswell unroll.c
1 leaq 8192(%rdi), %rax
2 vmovss .LC0(%rip), %xmm0
3 .L5:
4 vmulss (%rdi), %xmm0, %xmm1
5 vmovss %xmm1, (%rdi)
6 vmulss 4(%rdi), %xmm0, %xmm1
7 vmovss %xmm1, 4(%rdi)
8 addq $8, %rdi
9 cmpq %rax, %rdi
10 jne .L5
xmm1
.-funroll-loops
.Técnicas:
Evitar WAW y WAR mediante renombre de registros.
(+) Se acerca al IPC ideal.
1 R4 <- R1 + *R5*
2 *R5* <- R1 + R2
Register renaming o α-conversion ;)
1 R4 <- R1 + *R5*
2 R5' <- R1 + R2
3 // de acá para abajo `R5 -> R5'`
1 *R2* <- R4 + R7
2 *R2* <- R1 + R3
Después de renombre de registros
1 *R2* <- R4 + R7
2 *R2'* <- R1 + R3
3 // de acá para abajo `R2 -> R2'`
Muchísimos más registros. Dependen del tipo: integer, floating point, vectorial.
The integer register file has 168 physical registers of 64 bits each. The floating point register file has 160 registers of 128 bits each.
Agner Fog, The microarchitecture of Intel and AMD CPUs, Chp 20, 2020.
WikiChip, Skylake (client) - Microarchitectures - Intel, 2020.
No puedo mover el salto ni para arriba ni para abajo. (asignación ←)
1 DADDU R2, R3, R4
2 BEQZ R2, L1
3 LW R1, 0(R2)
4 L1: ...
Y por más de que no dependa arriba, tampoco puedo moverlo!
1 DADDU R1, R2, R3
2 BEQZ R4, L
3 DSUBU R1, R5, R6
4 L: ...
5 OR R7, R1, R8
Es muy complicado reordenar un branch
.
Opciones:
Postura optimista:
En pipelines profundos el UnDo penaliza mucho.
Dan Luu, Branch prediction , 2017.
M.Lipp, M.Schwarz, D.Gruss, T.Prescher, W.Haas, S.Mangard, P.Kocher, D.Genkin, Y.Yarom, M.Hamburg, Meltdown, 2018.
Saber que rama tomará es no-computable.
Lo mejor que podemos acertar es ... ¿50%?, meh.
1 int max(const int x, const int y)
2 {
3 return (x < y) ? y : x;
4 }
gcc
1 #define likely(x) __builtin_expect((x),1)
2 #define unlikely(x) __builtin_expect((x),0)
3 .
4 .
5 .
6 if (unlikely(fd < 0))
7 {
8 /* Do something */
9 }
10 .
11 .
12 .
x86
1 cmpl %esi, %edi
2 cmovll %esi, %edi
3 movl %edi, %eax
4 ret
nop
innecesario si el salto era predecible.movfuscator
, the single instruction C compiler.sandsifter
del mismo autor.Es algo estandar en:
Todas las instrucciones tienen un bitfield de 4 banderas: Z, C, O, P.
Si se dan las condiciones, ejecuta.
Si no, skip
o nop
.
¡Por ahora solo uno y de una forma!
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 |