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

Xeon E5 core

Gran porcentaje de la superficie para extraer paralelismo y mitigar el memory wall.

Presenter Notes

SMT, aka Hyperthreading™

Symmetric Multithreading

Four threads using superscalar in different ways, COaD5 Figure 6.5

Presenter Notes

SMT, ¿Vale la pena?

Speedup and energy efficiency of using one core with SMT on Core i7, COaD5 Figure 6.6

En promedio

  • Desempeño: 1.31x
  • Eficiencia energética: 1.07x

Presenter Notes

Nuevas instrucciones

Growth of x86 instruction set over time. COaD5

Modelo tick-tock de Intel

Tock: die shrink.
Tick: new microarchitecture.

  • Gran crecimiento de instrucciones en el tock.
  • Pero también el en tick:
    • Instrucción nueva para RNG RDRAND en Ivy Bridge.

Presenter Notes

Nuevas instrucciones

New haswell instructions

Presenter Notes

Resumen: Trucos para una CPU rápida

  • Paralelismo de instrucciones: ILP
    • Pipelining.
    • Branch prediction.
    • Superscalar.
    • Out-of-Order (OoO) Execution.
  • Nuevas instrucciones.
  • Jerarquía de Memoria.
  • Paralelismo de Datos: DLP
    • Operaciones Vectoriales.
  • Paralelismo de Hilos: TLP
    • SMT.
    • Multicore.

Presenter Notes

Los tres niveles de paralelismo

  • Instrucciones: ILP
  • Datos: DLP
  • Hilos: TLP

Por ahora solo uno.

Presenter Notes

Jerarquía de Memoria

Presenter Notes

Memory Wall

Wulf, McKee, Hitting the Memory Wall: Implications of the Obvious, 1995.

if the microprocessor/memory performance gap continues to grow at a similar rate, in 10-15 years each memory access will cost, on average, tens or even hundreds of processor cycles. Under each scenario, system speed is dominated by memory performance.

PowerEdge CPU vs. Memory

(Memory Wall -- HPBD 070809 HIGH PERFORMANCE COMPUTING - WIKI, Dell Inc.)

Presenter Notes

Jerarquía de Memoria

Jerarquía de Memoria

(Penn CIS565)

Presenter Notes

Números crudos de los niveles

Trade-off entre: latencia, ancho de banda, tamaño, precio.

Latencia, ancho de banda y tamaño de la jerarquía de memoria

(Penn CIS565)

Falta un nivel más arriba: registros.

Presenter Notes

4 preguntas de Jerarquía de Memoria

  • (Q1) ¿Dónde pongo un bloque en la caché?
  • (Q2) ¿Cómo encuentro un bloque en la caché?
  • (Q3) ¿Qué bloque reemplazo en un fallo?
  • (Q4) ¿Qué pasa en una escritura?

Presenter Notes

(Q1) Caché: mapa de muchos a n-way

Asociatividad de Caché

(Hennessy, Patterson, Computer Architecture ...)

Presenter Notes

(Q1) Caché: mapa de muchos a n-way (2)

Típicamente 8 o 16-way, más no paga:

Miss rate versus cache size on the Integer portion of SPEC CPU2000

(Wikipedia, CPU Cache)

Presenter Notes

Línea de caché

Se trae mucho más que una palabra (4 u 8 bytes).

Típicamente 64 bytes.

Favorece la localidad espacial.

1 unsigned int i = 0, s = 0;
2 for (i=s=0; i<size; ++i) {
3     s +=a[i];
4 }

Presenter Notes

(Q2) ¿Cómo distingo el uno en muchos?

Cache address

(Hennessy, Patterson, Computer Architecture ...)

Comparación n-way en paralelo.

  • Cache miss.
  • Cache hit.

Presenter Notes

(Q3) ¿Qué bloque reemplazo en un fallo?

Estrategia de reemplazo least-recently used (LRU), o alguna aproximación.

Favorece la localidad temporal.

1 unsigned int i = 0, s = 0;
2 for (i=s=0; i<size; ++i) {
3     s +=a[i];
4 }

Presenter Notes

(Q4) ¿Qué pasa en una escritura?

Dos estrategias:

  • Write through.
  • Write back (dirty bit).

Dos estrategias en write miss:

  • Write allocate.
  • No-write allocate.

Presenter Notes

Optimizaciones avanzadas

  • Way-prediction (predicción del índice).
  • Cache multibanco (acceso simultáneo a 2 o más bancos).
  • Write merging write buffers.
  • Prefetching.

Presenter Notes

Memoria Virtual

Cada acceso a memoria consulta la tabla de página.

Virtual a física

(Hennessy, Patterson, Computer Architecture ...)

Tabla de página

  • Árbol multinivel.
  • Típicamente 2 o 3 niveles.
  • ¿Recorrer un árbol de 3 niveles en cada acceso a memoria?

Presenter Notes

TLB

Caché completamente asociativo.

Opteron TLB

("Opteron TLB", Hennessy, Patterson, Computer Architecture ...)

Ahora hay TLB multi-niveles, uno en L1 y otro en L2.

Presenter Notes

Bibliografía

Presenter Notes

Bibliografía

Presenter Notes

La clase que viene

Ayudando al compilador:

  • Que cosas NO vale la pena hacer.
  • Que cosas vale la pena hacer.

Presenter Notes