Superescalar

Presenter Notes

Resumen:

  • OoO
  • 1<IPC
  • Múltiples unidades de ejecución.

Nicolás Wolovick 20210330

Presenter Notes

Detectar Dependencias

Dependencia: clausura transitiva de la relación binaria depende-de.

Es una propiedad del programa.

Detección

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

Tipos de Dependencias

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

Presenter Notes

Ejemplos

RAW: read after write, true dependency.

1 *R2* <- R5 + R3
2 R4 <- *R2* + R3

WAR: write after read, output dependency.

1 R4 <- R1 + *R5*
2 *R5* <- R1 + R2

WAW: write after write, anti-dependency.

1 *R2* <- R4 + R7
2 *R2* <- R1 + R3

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 WAW en xmm1!!! Ah!?
  • Probar la versión no-desenrollada a mano 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.

  • (+) 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

Repensando el ejemplo del loop unrolling

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

Las ideas sons las mismas, pero la frontera de los algoritmos y las estructuras de datos que la implementan se corren del software al hardware+firmware.

Presenter Notes

Architectural Regs. vs. Physical Regs.

ARF: architecture register file << PRF: physical register file
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.

Exploración del tamaño del PRF

Henry Wong, Measuring Reorder Buffer Capacity, may 14th, 2013.

Presenter Notes

Ejecución Fuera de Orden (OoO)

  • Planificación dinámica de las operaciones.
  • Rellenar huecos que produce RAW mediante ejecución fuera de órden.
  • Esto también sirve para rellenar cualquier hueco!
    • Latencia memoria (L1, L2, L3, DRAM)
    • Latencia operaciones complejas como división
  • Evitar WAW y WAR mediante renombre de registros

Pros&Cons

  • (+) Se acerca al IPC ideal.
  • (-) Incrementa el área.
  • (-) Incrementa la potencia.

Presenter Notes

Notas históricas IBM "janitor letter"

Presenter Notes

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

Arquitectura BIG.little de ARM

Presenter Notes

¿Cuánto paralelismo puedo extraer?

Es increíble como todavía le pueden sacar jugo a la secuencialidad.

Koen Crijns, Intel five generation IPC test: Broadwell, Haswell, Ivy Bridge, Sandy Bridge and Nehalem, Hardware.Info, 2015

Presenter Notes

¡Aun más paralelismo!

Timothy Prickett Morgan, The Huge Premium Intel Is Charging For Skylake Xeons, Sep 1 2017.

Presenter Notes

Procesadores superescalares

  • Estamos limitados a IPC≤1, a menos que ...

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, Anandtech, 2012.

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, Anandtech, 2012.

Presenter Notes

Superescalar en Haswell

Haswell Execution Engine

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

Presenter Notes

Superscalar en Skylake-X

Ian Cutress, The Intel Skylake-X Review: Core i9 7900X, i7 7820X and i7 7800X Tested, Anandtech, June 2017.

Presenter Notes

Superscalar en Skylake-X

Presenter Notes

Discusión: the free lunch is over

Mucha área del µP destinada a descubrir paralelismo.

¡Ya no paga más! Law of diminishing returns.

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

Tick: die shrink.
Tock: new microarchitecture.

  • Gran crecimiento de instrucciones en el tock.
  • Pero también el en tick, pequeñas lavadas de cara.
    • Instrucción nueva para RNG RDRAND en Ivy Bridge.

Presenter Notes

Tick-tock model

Presenter Notes

Tick-tock-d'oh!

(Intel: Tick-Tock To Tick-Tock-Toe )

Presenter Notes

Nuevas instrucciones

New haswell instructions

Presenter Notes

Nuevas instrucciones, ¡Lío!

Presenter Notes

Tradeoff #instrucciones vs. complejidad

Michael Steil, Christian Hessmann, The Ultimate Apollo Guidance Computer Talk, 2017.

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

Bibliografía

Presenter Notes

Bibliografía

Presenter Notes

La clase que viene

  • Memory wall.

Presenter Notes