Nicolás Wolovick 20180426
Paralelismo a nivel de instrucciones.
A cargo del µP.
Se lo puede ayudar.
Paralelismo de datos.
A cargo del compilador o el programador.
50 % ayuda, 50 % a mano.
Paralelismo de hilos.
A cargo del programador (casi siempre).
10 % ayuda, 90 % a mano.
Granularidad: relación entre computación y comunicación.
GPU junta TLP con DLP en una sola cosa y permite granularidad fina o media sobre un dominio restringido del paralelismo.
El gran problema
1 DO I = 1,N
2 A(I) = B(I) * 3.14159
3 ENDDO
1 DO I = 2,N
2 A(I) = A(I-1) + A(I)
3 ENDDO
RAW (read after write), WAR (write after read), WAW (write after write)
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.
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.
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.
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.
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.
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.
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
Conceptualmente:
Dos tipos:
Esto es terrible y la implicancia es profunda.
FPU + acceso a registro = 75pJ
FPU + acceso a memoria = 1nJ
El futuro es memoria controladada por software en cada uno de los niveles de la pirámide
Intel KNL, NVIDIA Pascal, etc.
Uniform memory access (UMA).
Non-uniform memory access (NUMA) (todos son ccNUMA en realidad.)
(Frequently Asked Questions: NUMA, SMP and AMDs Direct Connect Architecture)
Datos cerca de la CPU, reducen el tráfico por los buses.
Pero ...
Las máquinas actuales con más de una pastilla son ccNUMA,
caché coherent NUMA.
¡Modelo de memoria es una problemática muy compleja!
1 P1: write(X,d)
2 ...
3 P1: read(X) = d
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
1 P1: write(X,d)
2 ...
3 P2: write(X,e)
4 ...
5 P3: read(X) = e
Acá no hay un "eventualmente".
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.
Todos los protocolos trabajan con una línea de cache de granularidad.
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.
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.
Mostrar stream
en jupiterace
.
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 |