Arquitecturas Modernas de CPU

Presenter Notes

Resumen:

Arquitectura del Conjunto de Instruciones (ISA).
Ejecución de la ISA.

Nicolás Wolovick 20180320

Presenter Notes

ISA `x86_64`

Presenter Notes

¿Qué ejecuta el µP?

1 void store(double *a, double *b, double *c) {
2     *c = *a + *b;
3 }

gcc-8 -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

Presenter Notes

Notar como pone y saca las cosas del stack

Un poco más simple

plata$ gcc-8 -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-8 -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

Probar con -m32 para que compile en i386, o sea 32 bits.

Presenter Notes

Tipos y sufijos de `C` a `GAS`

tipos de C y sufijos de GAS en x86_64

(Bryant, O’Hallaron, x86-64 Machine-Level Programming)

Presenter Notes

Registros

Registros en x86_64

(Bryant, O’Hallaron, x86-64 Machine-Level Programming)

Presenter Notes

Todos los registros + SSE3

Todos los registros en x86_64

Presenter Notes

Actualmente con XeonPhi

Table of x86 Registers

Presenter Notes

Comparacion de área

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.

Presenter Notes

Ejemplo

 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 }

Presenter Notes

Ejemplo

clang-6 -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-6 -O2 y gcc-8 y ver que hace. Probar con -march=haswell -O3 -ffast-math.

Presenter Notes

Entender `x86_64`

Hacer pequeños programitas, compilar con -S y mirar el .s.
- Usar -O1 que es el más legible.
- Usar -march= ... para diferentes sub-arquitecturas.
- Usar diferentes arquitecturas aarch64-linux-gnu-gcc-7, powerpc64-linux-gnu-gcc-7.
Bryant, O’Hallaron, x86-64 Machine-Level Programming.
Intel Corp., Intel® 64 and IA-32 Architectures Software Developer's Manual, Instruction Set Reference.

Presenter Notes

Ejecución de ISA `x86_64`

Presenter Notes

Procesamiento de una instrucción

1 while (1) {
2     Fetch(PC); Decode;
3     Read Inputs; Execute; Write Output;
4     Next PC;
5 }

Simple CPU Core

(Penn CIS565)

Presenter Notes

Ciclos simples vs. Multiciclos

CPI: Cycles Per Instruction IPC: 1/CPI: Instructions Per Cycle.

CPI = 1, pero ciclos lentos.

Alternativa: Ejecución Multiciclo.

Simple CPU Core

(Penn CIS501)

(-) Aumenta CPI.
(+) Puedo bajar el ciclo del reloj.
(+) Las instrucciones pueden tener una cantidad diferente de ciclos.

Procesadores de los 70's y 80's: 8080, Z80, 68000.

Presenter Notes

Pipelining

Simple CPU Core

Pipelined CPU Core

(Penn CIS501)

Presenter Notes

Instruction Level Paralelism

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:

Pasaje por el pipeline

(Penn CIS501)

Presenter Notes

Dependencias

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;

Problema de corrección

La instrucción 2 tiene que esperar que la 1 termine de operar.

Dependencia de datos.
Dependencia de control (saltos = asignaciones al PC, luego también es dependencia de datos!).

Stalls

Inyecta burbujas en el pipeline para mantener la ilusión de secuencialidad.

+ Hazards

Structural Hazards (más operaciones que el hardware disponible).
Control Hazards.

Presenter Notes

Data Hazards

Sin dependencia (dirección de asignación `<-`)

1 LD   *R1*, 45(R2)
2 DADD R5, R6, R7
3 DSUB R8, R6, R7
4 OR   R9, R6, R7

Requiere un stall

1 LD   *R1*, 45(R2)
2 DADD R5, *R1*, R7
3 DSUB R8, R6, R7
4 OR   R9, R6, R7

Se soluciona con un forwarding

1 LD   *R1*, 45(R2)
2 DADD R5, R6, R7
3 DSUB R8, *R1*, R7
4 OR   R9, R6, R7

Dependencia con acceso ordenado

1 LD   *R1*, 45(R2)
2 DADD R5, R6, R7
3 DSUB R8, R6, R7
4 OR   R9, *R1*, R7

(Hennessy, Patterson, Computer Architecture ...)

Presenter Notes

Detectar Dependencias

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.

Detección

Entre registros: directa.
Entre celdas de memoria: no trivial.

Tipos de Dependencias

RAW: read after write, true dependency.
WAW: write after write, anti-dependency.
WAR: write after read, output dependency.

Presenter Notes

Dependencia en un loop

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

Presenter Notes

Aumento de la independencia: unrolling

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

Dependencia falsa WAW en xmm1.
El µP hace register renaming interno y ambas sumas van en paralelo.
Se podría haber hecho también en tiempo de compilación.
Probar la versión no-desenrollada a mano con -funroll-loops.

Presenter Notes

Evitando los Data Hazards

Pipeline bubbles.
Operand forwarding.
OoO execution!
- w/register renaming.

Presenter Notes

Ejecución Fuera de Orden (OoO)

Planificación dinámica de las operaciones.
Evitar RAW mediante planificación: ejecución fuera de órden.
Evitar WAW y WAR mediante renombre de registros.
(+) Se acerca al IPC ideal.
(-) Incrementa el área.
(-) Incrementa la potencia.

CPUs

En orden: Intel Atom, ARM Cortex-A8 (Apple A4, TI OMAP 3), ARM Cortex-M.
Fuera de orden: ≥Pentium Pro, ARM Cortex A9 (Apple A5, NV Tegra 2/3, TI OMAP 4).

Presenter Notes

Control Hazards

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:

Stall hasta saber el resultado de la comparación.
... o seguir como si nada hubiera pasado.

Presenter Notes

Ejecución Especulativa

Postura optimista:

Especula que el branch no se va a tomar.
Si hay miss-prediction: deshacer cambios.
- Se hace un check-point de todo el estado interno de la µArquitectura y si se equivoca, rollback.

En pipelines profundos el undo penaliza mucho.

Predicción de saltos

Pequeño análisis estadístico en runtime.
Predictores modernos >90% de exactitud.

(Dan Luu, Branch prediction , 2017.)

Presenter Notes

Ejecución especulativa, side-effects

No se pueden deshacer todos los cambios del estado en la µArquitectura.
En particular si la caché se tocó, eso queda ahi.

M.Lipp, M.Schwarz, D.Gruss, T.Prescher, W.Haas, S.Mangard, P.Kocher, D.Genkin, Y.Yarom, M.Hamburg, Meltdown, 2018.

Presenter Notes

Uso de Predicados

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 }

"Una aiuda" a `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 .

Presenter Notes

Instrucciones Predicadas en `x86`

Copia condicional

1 cmpl    %esi, %edi
2 cmovll  %esi, %edi
3 movl    %edi, %eax
4 ret

(+) Evita el predictor de saltos.
(-) Mete un nop innecesario si el salto era predecible.

Filigrana computacional

Stephen Dolan, mov is Turing-complete.
Chris Domas, movfuscator, the single instruction C compiler.
- mirar sandsifter del mismo autor.

Presenter Notes

Instrucciones predicadas

Es algo estandar en:

ARM32 (pero no en ARM64)
GPUs

Todas las instrucciones tienen un bitfield de 4 banderas: Z, C, O, P.
Si se dan las condiciones, ejecuta.
Si no, skip o nop.

Presenter Notes

Profundidad de los pipelines

486: 5 fases.
Pentium: 7 fases.
Pentium II/III: 12 fases.
Pentium 4: 22 fases (super-pipelined).
Core 1/2: 14 fases.

Incrementar la profundidad

(+) Se puede incrementar la frecuencia del clock (pero no paga tanto).
(-) El IPC decrece:
- Data Hazards que no se pueden resolver penalizan mucho.
- Saltos mal predichos penalizan mucho.

Presenter Notes

Los tres niveles de paralelismo

Instrucciones: ILP
Datos: DLP
Hilos: TLP

Por ahora solo uno y de una forma!

Presenter Notes

Bibliografía

Presenter Notes

Bibliografía

Bryant, O’Hallaron, x86-64 Machine-Level Programming, 2008.
Intel Corp., Intel® 64 and IA-32 Architectures Software Developer's Manual, Instruction Set Reference.
Hennessy, Patterson, Computer Architecture: A Quantitative Approach, Fourth Edition, Morgan Kaufmann, 2011.
Penn CIS565.
Penn CIS501.

Presenter Notes

La clase que viene

Superscalar.
OoO.

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

Problema de corrección

Stalls

+ Hazards

Sin dependencia (dirección de asignación <-)

Requiere un stall

Se soluciona con un forwarding

Dependencia con acceso ordenado

Detección

Tipos de Dependencias

CPUs

Predicción de saltos

"Una aiuda" a gcc

Copia condicional

Filigrana computacional

Incrementar la profundidad

Table of Contents

Help

Sin dependencia (dirección de asignación `<-`)

"Una aiuda" a `gcc`