Arquitecturas Modernas de CPU

Presenter Notes

Resumen:

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

Nicolás Wolovick $Date: 2012-04-04 10:45:06 -0300 (Wed, 04 Apr 2012) $, $Revision: 3362 $

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 }

Luego de gcc -march=native -S -o - 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

Luego de gcc -march=native -O2 -S -o - 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 pasado por `clang -O2 -S -o`

 1 max_dist:                               # @max_dist
 2 .Ltmp0:
 3     .cfi_startproc
 4 # BB#0:
 5     pxor    %xmm0, %xmm0
 6     testl   %esi, %esi
 7     je  .LBB0_3
 8 # BB#1:                                 # %.lr.ph.preheader
 9     addq    $8, %rdi
10     pxor    %xmm1, %xmm1
11     .align  16, 0x90
12 .LBB0_2:                                # %.lr.ph
13                     # =>This Inner Loop Header: Depth=1
14     movsd   -8(%rdi), %xmm0
15     movsd   (%rdi), %xmm2
16     mulsd   %xmm2, %xmm2
17     mulsd   %xmm0, %xmm0
18     addsd   %xmm2, %xmm0
19     sqrtsd  %xmm0, %xmm0
20     addq    $16, %rdi
21     decl    %esi
22     maxsd   %xmm1, %xmm0
23     movaps  %xmm0, %xmm1
24     jne .LBB0_2
25 .LBB0_3:                                # %._crit_edge
26     ret
27 .Ltmp1:
28     .size   max_dist, .Ltmp1-max_dist
29 .Ltmp2:
30     .cfi_endproc

compilar esto con gcc y ver que hace.

Presenter Notes

Entender `x86_64`

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

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: la más común.
WAW: puede ocurrir en ciertos pipelines.
WAR: muy raro.

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.

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

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

Sandy Bridge

(Core i7 3960X, Sandy Bridge Elostcircuit.com)

Presenter Notes

Superescalar en Sandy Bridge

Superscalar in Sandy Bridge

(Penn CIS565)

Presenter Notes

Resumen: Trucos para una CPU rápida

Extracción de ILP
- Pipelining.
- Branch prediction.
- Superscalar.
- Out-of-Order (OoO) Execution.
Jerarquía de Memoria.
Paralelismo de Datos.
- Operaciones Vectoriales.
Paralelismo de Hilos.
- SMT.
- Multicore.

Presenter Notes

Jerarquía de Memoria

Presenter Notes

Memory Wall

PowerEdge CPU vs. Memory

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

Presenter Notes

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

Bryant, O’Hallaron, x86-64 Machine-Level Programming.
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.
Herb Sutter, The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software, Dr. Dobb's Journal, 30(3), Marzo 2005.
Penn CIS565.
Penn CIS501.

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

Requiere un stall

Soluciona con un forwarding

Dependencia con acceso ordenado

Detección

Tipos de Dependencias

CPUs

Predicción de saltos

Copia condicional

Incrementar la profundidad

Superescalar

Solución

Tabla de página

Table of Contents

Help