Arquitecturas Modernas de CPU

Presenter Notes

Resumen:

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

Nicolás Wolovick 20200318

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

Presenter Notes

Notar como pone y saca las cosas del stack

Un poco más simple

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

Presenter Notes

¿Y en 32 bits?

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

¿Y en una máquina que no tengo? aka cross-compiling Fugaku

$ 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

Presenter Notes

Un solo compilador MUCHOS targets

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".

Presenter Notes

Tipos y sufijos de C a GAS

tipos de C y sufijos de GAS en x86_64

Presenter Notes

Registros

Registros en x86_64

Presenter Notes

Todos los registros + SSE3

Todos los registros en x86_64

Presenter Notes

Actualmente con XeonPhi

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

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-9, powerpc64-linux-gnu-gcc-9, riscv-linux-gnu-gcc-9.
  • 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

CARDIAC single cycle in paper computer

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

MIPS (Microprocessor without Interlocked Pipelined Stages), 1984.

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 semántica secuencial.

Hazards

  • Data Hazards (los anteriores)
  • 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 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
  • 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

Técnicas:

  • Pipeline bubbles (stalls).
  • Operand forwarding.
  • ¡OoO execution!
    • w/register renaming.
    • Dos sabores:
      • Tomasulo (IBM)
      • Scoreboarding (CDC)

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

Como se evitan los WAW y WAR

WAR

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'`

WAW

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'`

Presenter Notes

Architectural Regs. vs. Physical Regs.

Muchísimos más registros. Dependen del tipo: integer, floating point, vectorial.

AMD Zen

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.

Zeroing idioms

WikiChip, Skylake (client) - Microarchitectures - Intel, 2020.

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/si 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

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

Presenter Notes

La clase que viene

  • Superscalar.
  • OoO.

Presenter Notes