Nicolás Wolovick 20150315
x86_64
1 void store(double *a, double *b, double *c) {
2 *c = *a + *b;
3 }
gcc -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 popq %rbp
20 .cfi_def_cfa 7, 8
21 ret
22 .cfi_endproc
Notar como pone y saca las cosas del stack
Acá van notas de presentación.
gcc -S -O2 store.c
1 store:
2 .LFB0:
3 .cfi_startproc
4 movsd (%rdi), %xmm0
5 addsd (%rsi), %xmm0
6 movsd %xmm0, (%rdx)
7 ret
8 .cfi_endproc
C
a GAS
(Bryant, O’Hallaron, x86-64 Machine-Level Programming)
(Bryant, O’Hallaron, x86-64 Machine-Level Programming)
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-3.7 -S -O1 -fno-math-errno
¿Porqué -fno-math-errno
?
1 max_dist: # @max_dist
2 .cfi_startproc
3 # BB#0:
4 xorpd %xmm1, %xmm1
5 testl %esi, %esi
6 je .LBB0_1
7 .align 16, 0x90
8 .LBB0_2: # %.lr.ph
9 # =>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 decl %esi
20 movapd %xmm0, %xmm1
21 jne .LBB0_2
22 # BB#3: # %._crit_edge
23 retq
24 .LBB0_1:
25 xorps %xmm0, %xmm0
26 retq
compilar esto con clang-3.7 -O2
y gcc
y ver que hace.
x86_64
-S
y mirar el .s
.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.
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
).Inyecta burbujas en el pipeline para mantener la ilusión de secuencialidad.
<-
)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
1 .L5:
2 movss (%rdi,%rax), %xmm1
3 mulss %xmm0, %xmm1
4 movss %xmm1, (%rdi,%rax)
5 movss 4(%rdi,%rax), %xmm1
6 mulss %xmm0, %xmm1
7 movss %xmm1, 4(%rdi,%rax)
8 addq $8, %rax
9 cmpq $8192, %rax
10 jne .L5
xmm1
.-funroll-loops
.CDC 6600
.IBM 360/91
.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.
Saber que rama tomará es no-computable.
Lo mejor que podemos acertar es ... ¿50%?, meh.
1 int max(int x, 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.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
.
Aumenta el ancho del pipeline.
El IPC pico es N para un N-way superscalar µP.
Es increible como todavía le pueden sacar jugo a la secuencialidad.
(Intel five generation IPC test: Broadwell, Haswell, Ivy Bridge, Sandy Bridge and Nehalem)
((Anand Lal Shimpi)[http://en.wikipedia.org/wiki/Anand_Lal_Shimpi], Haswell's Wide Execution Engine)
((Anand Lal Shimpi)[http://en.wikipedia.org/wiki/Anand_Lal_Shimpi], Haswell's Wide Execution Engine)
((Anand Lal Shimpi)[http://en.wikipedia.org/wiki/Anand_Lal_Shimpi], Haswell's Wide Execution Engine)
Mucha área del µP destinada a descubrir paralelismo.
¡Ya no paga más! Law of diminishing returns.
Pasarle la pelota al programador/compilador.
Explicitar el paralelismo.
8 copias de lo mismo, 8 cores.
Gran porcentaje de la superficie para extraer paralelismo y mitigar el memory wall.
Symmetric Multithreading
Por ahora solo uno.
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 |