Nicolás Wolovick 20160421
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 KNC, 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 ...
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.
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) 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 |