MIMD

Presenter Notes

Resumen:

  • Mapa.
  • Dependencias.
  • Arquitectura de Multiprocesadores.

Nicolás Wolovick 20160421

Presenter Notes

Multiple Instruction Multiple Data

Flynn's taxonomy

Presenter Notes

Paralelismo en 3D

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!

Presenter Notes

Granularidad del Paralelismo

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.

Presenter Notes

Dependencias

Presenter Notes

Dependencias

El gran problema

Independiente

1 DO I = 1,N
2     A(I) = B(I) * 3.14159
3 ENDDO

Dependiente

1 DO I = 2,N
2     A(I) = A(I-1) + A(I)
3 ENDDO

Presenter Notes

Tipos de Dependencias

Dependencias de Control

HPC Figure 3.1

Dependencias de Datos

HPC Figure 3.4

RAW (read after write), WAR (write after read), WAW (write after write)

Presenter Notes

Dependencias en lazos

RAW (data&flow dependency)

1 DO I=2,N
2     A(I) = A(I-1) + B(I)
3 ENDDO

Desenrrollamos para ver la estructura

1 A(I) = A(I-1) + B(I)
2 A(I+1) = A(I) + B(I+1)
3 A(I+2) = A(I+1) + B(I+2)

Exponer un poco de independencia

1 DO I=2,N,2
2     A(I) = A(I-1) + B(I)
3     A(I+1) = A(I-1) + B(I) + B(I+1)
4 ENDDO

Pero acá solo exponemos un poco de paralelismo de grano fino para explotar con ILP y tal vez con DLP.

Presenter Notes

Dependencia en lazos

WAR (antidependency)

1 DO I = 1,N
2     A(I) = B(I)   * E
3     B(I) = A(I+2) * C
4 ENDDO

Puedo desenrollar una vez y lograr ILP.

Presenter Notes

Dependencia en lazos

WAW (output dependency)

1 DO I = 1,N
2     A(I) = C(I) * 2
3     A(I+2) = D(I) + E
4 ENDDO

No tiene mucho sentido la primera asignación.
No resulta un ejemplo real.

Presenter Notes

Dependencias dentro de una iteración

1 DO I = 1,N
2     D = B(I) * 17
3     A(I) = D + 14
4 ENDDO

Mhhh, medio facilón romper esto

1 DO I = 1,N
2     A(I) = B(I) * 17 + 14
3 ENDDO

Seguramente el compilador lo hace de manera automágica.

Presenter Notes

Referencias Ambiguas

1 DO I = 1,N
2     A(I) = B(I) * E
3     B(I) = A(I+K) * C
4 ENDDO

Si K no se conoce en tiempo de compilación, no se puede hacer nada.
( por eso usar constantes literales suele ayudar )

1 DO I = 1,N
2     A(K(I)) = A(K(I)) + B(J(I)) * C
3 ENDDO

Arreglos de índices (indirección), aun más complejo.

Presenter Notes

Punteros ambiguos

1 suma(float *a, float *b, float c, int n) {
2     int i;
3     for (i=0; i<n; ++i) {
4         a[i] = a[i]+ b[i]*c;
5     }
6 }

Podría haberlo llamado con:

  • suma(a, a-1, 2.0f, 1024), flow dependency.
  • suma(a, a+1, 2.0f, 1024), antidependency.
  • suma(a, b, 2.0f, 1024), ¡Por favor paralelizame!

¡Para eso sirve restrict!

En Fortran el aliasing queda muy expuesto, en C se puede esconder fácilmente.

Presenter Notes

Reducciones

1 SUM = 0.0
2 DO I = 1,N
3     SUM = SUM + A(I)
4 ENDDO

Tiene las 3 dependencias.
Si suponemos un + asociativo-conmutativo podemos escribir algo ILP o DLP (paralelismo fino)

1 SUM0 = SUM1 = 0.0
2 DO I = 1,N,2
3     SUM0 = SUM0 + A(I)
4     SUM1 = SUM1 + A(I+1)
5 ENDDO
6 SUM = SUM0+SUM1

ó algo TLP (paralelismo grueso).

1 SUM0 = SUM1 = 0.0
2 DO I = 1,N/2
3     SUM0 = SUM0 + A(I)
4 ENDDO
5 DO I = N/2,N
6     SUM1 = SUM1 + A(I)
7 ENDDO
8 SUM = SUM0+SUM1

Presenter Notes

SMP (Symmetric Multi Processing)

Presenter Notes

Multiprocesadores de Memoria Compartida

Conceptualmente:

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

HPC Figure 3.11

Dos tipos:

  • Memoria compartida centralizada.
  • Memoria compartida distribuida.

Presenter Notes

Comunicación y paralelismos

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

Esto es terrible y la implicancia es profunda.

Power Aware Architectures, Figure 4.1

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

Presenter Notes

Comunicación y paralelismos

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: 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 KNC, NVIDIA Pascal, etc.

Como un mantra

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

Presenter Notes

Memoria centralizada

Uniform memory access (UMA).

Memoria compartida centralizada

  • Poca escalabilidad.
  • Usado por Intel hasta Core2.

Presenter Notes

Memoria distribuída

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

Memoria distribuída

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

Presenter Notes

Direct Connect vs. FSB, circa 2006

Diferencias en

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

Presenter Notes

Caché

HPC Figure 3.14

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

Pero ...

Presenter Notes

Múltiples copias de una celda de memoria

HPC Figure 3.15

Inconsistencia o cache coherence problem

The cache coherence problem for a single memory location (X), read and written by two processors (A and B)

Presenter Notes

Coherencia y Consistencia

mini, lstopo

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

Coherencia: que valores retorna una lectura.
Consistencia: cuando una escritura será devuelta por una lectura.

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

Presenter Notes

Coherencia (definición)

1) Orden secuencial del programa

1 P1: write(X,d)
2 ...
3 P1: read(X) = d

2) Coherencia entre procesadores

Eventualmente se lee el valor nuevo. No se puede leer siempre un valor viejo.

1 P1: write(X,d)
2 ...
3         ... (suficientemente separados) ...
4 ...
5                                       P2: read(X) = d

3) Serialización de las escrituras

1 P1: write(X,d)
2 ...
3                         P2: write(X,e)
4 ...
5                                                 P3: read(X) = e

Acá no hay un "eventualmente".

Presenter Notes

Como lograr coherencia

Necesito un protocolo (algoritmo distribuído) 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.

Presenter Notes

MESI protocol

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.

WEPSHAM, MESI protocol

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.

Presenter Notes

Bibliografía

Presenter Notes

Bibliografía

Presenter Notes

Performance Paralela

Mostrar stream en jupiterace.

Presenter Notes

La clase que viene

  • Procesos e hilos.
  • OpenMP.

Presenter Notes