• Mapa.
• Dependencias.
• Arquitectura de Multiprocesadores.

ILP (instruction-level paralelism)

Paralelismo a nivel de instrucciones.
A cargo del µP.
Se lo puede ayudar.

DLP (data-level parallelism)

Paralelismo de datos.
A cargo del compilador o el programador.
50 % ayuda, 50 % a mano.

TLP (thread-level parallelism)

Paralelismo de hilos.
A cargo del programador (casi siempre).
10 % ayuda, 90 % a mano.

• Ordenados de grano fino a grano grueso.
• 3 dimensiones ortogonales de paralelismo.
  ¡Aprovecharlas a todas!

Granularidad: relación entre computación y comunicación.

• ILP: grano fino
• DLP: grano fino
• TLP: grano grueso (a menos que estemos en una GPU)

GPU junta TLP con DLP en una sola cosa y permite granularidad fina o media sobre un dominio restringido del paralelismo.

En realidad depende de la distancia.

Cuanto overhead de comunicación soy capaz de aguantar.

Se puede hacer paralelismo de grano fino en TLP,
pero la distancia a la memoria hace que sea IMPRACTICABLE.

ILP y DLP

Se comunican por registros, aka 1 clock.

TLP

Se comunican por DRAM, aka 100 clocks.

Conceptualmente

• Muchos µP.
• Todos ven toda la memoria.

Dos tipos

• Memoria compartida centralizada.
• Memoria compartida distribuida.

• ILP, DLP: a través de registros.
• TLP: a través de la memoria.

Esto es terrible y la implicancia es profunda.

FPU + acceso a registro = 75pJ, FPU + acceso a memoria = 1nJ

13x de diferencia.

Comparar

• GPU: forma explícita de comunicación en 3 niveles: registros (warp shuffle), memoria compartida (load/store shmem), memoria global (load/store glb)
• CPU: vector shuffles y horizontales, trucos para usar caché L1, L2, L3 como memorias de comunicación. Ejemplo: técnica de blocking usada en OpenBLAS, FFTW, etc.

El futuro es memoria controladada por software en cada uno de los niveles de la pirámide

Intel KNL, NVIDIA Pascal, A64FX, etc.

Como un mantra ॐ

• All performance is from parallelism
• Machines are power limited
  (efficiency IS performance)
• Machines are communication limited
  (locality IS efficiency, efficiency IS performance)

Uniform memory access (UMA).

• Poca escalabilidad.
• Usado por Intel hasta Core2.

Non-uniform memory access (NUMA) (todos son ccNUMA en realidad.)

• Buena escalabilidad.
• El programa tiene que saber que la memoria está distribuída (performance).
  • Sin embargo el espacio de direcciones es único.
• Intel reemplazó el FSB por Quickpath-QPI desde Nehalem, ¿2009?
• AMD la usa desde mucho antes (Hypertransport-HT en Direct Connect Architecture- DCA , desde Athlon 64 X2, 2006).

Frequently Asked Questions: NUMA, SMP and AMDs Direct Connect Architecture

Datos cerca de la CPU, reducen el tráfico por los buses.

Pero ...

Inconsistencia que resuelve el cache coherence problem

• Problema cachear memoria compartida, ≥2 copias de la misma información.
• Dar consistencia al acceso de datos compartidos.
• Mantener la coherencia entre las copias de datos.

Las máquinas actuales con más de una pastilla son ccNUMA,
caché coherent NUMA.

¡Modelo de memoria es una problemática muy compleja!

Necesito un protocolo (algoritmo distribuído) de coherencia entre caches y memoria que permita:

Migración: poner el dato lo más cerca de la memoria.

Replicación: copiar datos para que la lectura simultánea de datos compartidos esté cerca de todos.

Snooping (sniffing) protocols

• Write invalidation protocol.
  • Concurrent write arbitration.
• Write broadcast.

Todos los protocolos trabajan con una línea de cache de granularidad.
👆 utterly important!

Modified: la línea está solo acá y difiere de la memoria. El write-back la pasa a E.
Exclusive: la línea limpia solo está acá. Cambia a S cuando otro lee. Cambia a M si el µP la toca.
Shared: la línea está limpia, pero hay copias. Puede cambiar a I.
Empty/Invalid: la línea está sin usar.

Operaciones caras

Escribir una línea S es costoso, difundir un "¡Esta línea es inválida!".
Esto se llama RFO (request for ownership).

Tener una línea M es complejo. Snoop (interceptar) los reads, y transmitirles el dato.

A system on Earth, at sea level, with 4 GB of RAM has a 96% percent chance of having a bit error in three days without ECC RAM. With ECC RAM, that goes down to 1.67e-10 or about one chance in six billions.

Berke Durak, On the need to use error-correcting memory, 2010.

Try to live at or below sea level, or work under a mountain à la NORAD You might also try to live in the lower floors of high-rise buildings, but avoid being near windows.

Berke Durak, Updates on the need to use error-correcting memory, 2010.

Teórico

Según la cuentita:

BW = channels × 8 (64 bits) × F

bw(DDR4-2133) = 4×8×2133 = 68.256 GBps por pastilla!

• Es importante OMP_PROC_BIND=true OMP_PLACES=cores para ir ocupando todos los cores primero de una pastilla y luego de la otra.
• Para una sola pastilla satura en 5 cores.
• ¡El resto de los 14-7 = 7 cores no aportan más BW en la primera pastilla!
• Cuando se ocupa la segunda pastilla presenta un escalado más lineal.

• Charles Severance, Kevin Dowd, "High Performance Computing", Connexions, 2010, CC3.0.
• Ulrich Drepper, What Every Programmer Should Know About Memory, RedHat, 2007.
• Mario Nemirovsky, Dean Tullsen, Multithreading Architecture, 2013.
• Patterson, Hennessy Computer Organization and Design, Fifth Edition, Morgan Kaufmann, 2012.
• Hennessy, Patterson, Computer Architecture: A Quantitative Approach, Fourth Edition, Morgan Kaufmann, 2011.
• Magnus Själander, Margaret Martonosi, Stefanos Kaxiras, Power-Efficient Computer Architectures, Synthesis Lectures on Computer Architecture, 2014.

La clase que viene

• Procesos e hilos.
• OpenMP.