Arquitecturas Modernas de CPU

Presenter Notes

Resumen:

  • Arquitectura del Conjunto de Instruciones (ISA).
  • Ejecución de la ISA.
  • Jerarquía de Memoria.

Nicolás Wolovick 20140317

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

Presenter Notes

Acá van notas de presentación.

Un poco más simple

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

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

Ejemplo

 1 #include <math.h>
 2 
 3 struct point {
 4     double x;
 5     double y;
 6 };
 7 
 8 double max_dist(struct point *a, const unsigned int size) {
 9     double result = 0.0;
10     unsigned int i = 0;
11     for(i=0; i<size; ++a, ++i) {
12         double dst = 0.0;
13         dst = sqrt((a->x * a->x) + (a->y * a->y));
14         if (dst>result)
15             result = dst;
16     }
17     return result;
18 }

Presenter Notes

Ejemplo

clang -S -O2 -fno-math-errno ¿Porqué -fno-math-errno?

 1 max_dist:                               # @max_dist
 2         .cfi_startproc
 3 # BB#0:
 4         xorps   %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
11         movsd   8(%rdi), %xmm2
12         mulsd   %xmm0, %xmm0
13         mulsd   %xmm2, %xmm2
14         addsd   %xmm0, %xmm2
15         sqrtsd  %xmm2, %xmm0
16         maxsd   %xmm1, %xmm0
17         addq    $16, %rdi
18         decl    %esi
19         movaps  %xmm0, %xmm1
20         jne     .LBB0_2
21 # BB#3:                                 # %._crit_edge
22         ret
23 .LBB0_1:
24         xorps»  %xmm0, %xmm0
25         ret

compilar esto con gcc y ver que hace.

Presenter Notes

Entender x86_64

  • Hacer pequeños programitas, compilar con -S y mirar el .s.
  • 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: Cicles 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 trivial:

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

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

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.
  • WAW: write after write.
  • WAR: write after read.

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 con -funroll-loops.

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.
  • Algoritmo de Tomasulo. Presentado en 1967 para la FP unit de la IBM 360/91.
  • (+) Se acerca al IPC ideal.
  • (-) Incrementa el área.
  • (-) Incrementa la potencia.

CPUs

  • En orden: Intel Atom, ARM Cortex-A8 (Apple A4, TI OMAP 3).
  • 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.

En pipelines profundos el undo penaliza mucho.

Predicción de saltos

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

Presenter Notes

Uso de Predicados

Saber que rama tomará es no-computable.

Lo mejor que podemos acertar es el 50%.

1 int max(int x, int y)
2 {
3     return (x < y) ? y : x;
4 }

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.
  • Técnica estándar en GPGPU Computing.

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

Procesadores superescalares

  • Estamos limitados a 1<=CPI.

Superescalar

Aumenta el ancho del pipeline.

Superescalar CPU Core

(Penn CIS565)

El IPC pico es N para un N-way superscalar µP.

Presenter Notes

Superescalar en Nehalem

Nehalem Execution Engine

((Anand Lal Shimpi)[http://en.wikipedia.org/wiki/Anand_Lal_Shimpi], Haswell's Wide Execution Engine)

Presenter Notes

Superescalar en Sandy Bridge

Sandy Bridge Execution Engine

((Anand Lal Shimpi)[http://en.wikipedia.org/wiki/Anand_Lal_Shimpi], Haswell's Wide Execution Engine)

Presenter Notes

Superescalar en Haswell

Haswell Execution Engine

((Anand Lal Shimpi)[http://en.wikipedia.org/wiki/Anand_Lal_Shimpi], Haswell's Wide Execution Engine)

Presenter Notes

Discusión: the free launch is over

Mucha área del µP destinada a descubrir paralelismo.

¡Ya no paga más!

Solución

Pasarle la pelota al programador/compilador.

Explicitar el paralelismo.

  • Simultaneous Multithreading -- SMT (Hyperthreading™).
    • Utilizar unidades funcionales ociosas con otro hilo.
    • Más libertad al planificador OoO.
    • Necesita de un juego alternativo de registros para hacer el cambio.
  • Multicore.

Presenter Notes

Xeon Ivy Bridge

Ivy Bridge floor plan

(Xeon E5-2680)

8 copias de lo mismo, 8 cores.

Presenter Notes

Xeon Ivy Bridge, un core