MIMD

Presenter Notes

Resumen:

  • Mapa.
  • Dependencias.
  • Arquitectura de Multiprocesadores.

Nicolás Wolovick 20140421

Presenter Notes

Multiple Instruction Multiple Data

Flynn's taxonomy

Presenter Notes

Granularidad del paralelismo

ILP (instruction-level paralelism)

Paralelismo a nivel de instrucciones.
A cargo del µP.

DLP (data-level parallelism)

Paralelismo de datos.
A cargo del compilador o el programador.

TLP (thread-level parallelism)

Paralelismo de hilos.
A cargo del programador (casi siempre).

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

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

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

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.

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

¡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 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

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

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

La clase que viene

  • Procesos e hilos.
  • OpenMP.

Presenter Notes