arquitecturas paralelas computación de altas prestaciones idoia cearreta idoia.cearreta@ehu.es
Post on 13-Jan-2016
43 Views
Preview:
DESCRIPTION
TRANSCRIPT
UPV-EHU / ATC Arquitecturas Paralelas 12-13 1
ARQUITECTURAS PARALELASComputación de altas prestaciones
Idoia Cearretaidoia.cearreta@ehu.es
www.sc.ehu.es/arpar
Konputagailuen Arkitektura eta Teknologia sailaInformatika Fakultatea – Euskal Herriko Unibertsitatea
UPV-EHU / ATC
0. Introducción.1. Computadores vectoriales.2. Computadores paralelos (conceptos básicos).3. Coherencia de los datos (SMP).4. Sincronización de procesos (SMP).5. Consistencia de la memoria.6. Red de comunicación. Paso de mensajes.7. Coherencia de los datos (DSM).8. Paralelización de bucles, reparto de tareas.9. Computadores paralelos de alta velocidad.
Programación paralela: OpenMP yMPI (introd.).
ARQUITECTURAS PARALELAS
UPV-EHU / ATC Arquitecturas Paralelas 12-13 3
0. Introducción
UPV-EHU / ATC Arquitecturas Paralelas 12-13 4
Introducción
La evolución de los computadores se basa principalmente en tres factores: avances en la tecnología electrónica
avances en el diseño de la arquitectura de sistemas
avances en el desarrollo de software de sistemas
UPV-EHU / ATC Arquitecturas Paralelas 12-13 5
Introducción
Avances en la tecnología electrónica número de transistores > 1.000
M
frecuencia del reloj > 1 GHz velocidad de conmutación
tecnología de empaquetamiento
capacidad de memoria
tiempos de comunicación entre elementos/chips
UPV-EHU / ATC Arquitecturas Paralelas 12-13 6
Introducción
Avances en la arquitectura de sistemas arquitecturas RISC jerarquía de memoria unidades funcionales específicas
segmentación (ILP)desorden (Tomasulo) superescalares - VLIW / ejecución
especulativamultithreading
registros
multicore on chip
UPV-EHU / ATC Arquitecturas Paralelas 12-13 7
Introducción
Avances en el software de sistemas
list scheduling
loop unrolling
software pipelining
trace scheduling
EPIC...
OpenMP
MPI
UPC
OpenCL / Cuda
...
UPV-EHU / ATC Arquitecturas Paralelas 12-13 8
Introducción
Velocidad de cálculo del procesador escalar:
> 1 Gflop/s 109 operaciones de coma flotante por segundo
Recordad:
Mega (M) 106 Giga (G) 109 Tera (T) 1012 Peta (P) 1015
micro (µ) 10-6 nano (n) 10-9 pico (p) 10-12 femto (f) 10-15
Dicha velocidad no es suficiente para algunas aplicaciones técnicas/científicas: meteorología, genética, astrofísica, aeronaútica, geofísica, bases de datos grandes...
UPV-EHU / ATC Arquitecturas Paralelas 12-13 9
IntroducciónHennessy – Patterson, 4. ed.
52% anual
20% anual
UPV-EHU / ATC Arquitecturas Paralelas 12-13 10
Introducción
Solución: paralelismo
- Multicore (2-8 procesadores por chip)- muchos (?) procesadores trabajando conjuntamente
P = 10.000 proc. >> 10.000 GF/s??
¿Cómo utilizar P procesadores?
una red / mera repetición /sistema paralelo
UPV-EHU / ATC Arquitecturas Paralelas 12-13 11
Introducción
Flujo de datos
1 n
1
n
Flujo de instrucciones
SISD
Clasificación de Flynn
SIMDProcesadores en array Computadores vectoriales
MIMDmemoria compartidamemoria privada
UPV-EHU / ATC Arquitecturas Paralelas 12-13 12
1. Computadores vectoriales
- Introducción- Dependencias de datos- Dependencias estructurales- Medidas de rendimiento
- Técnicas de compilación
UPV-EHU / ATC Arquitecturas Paralelas 12-13 13
CV: introducción
do i = 0, N-1
C(i) = A(i) + B(i)
enddo
TE ≈ 7N ciclos
buc: FLD F1,A(R1)
FLD F2,B(R1)
FADD F3,F2,F1
FST C(R1),F3
ADDI R1,R1,#8
SUBI R2,R2,#1
BNZ R2,buc
Código escalar
UPV-EHU / ATC Arquitecturas Paralelas 12-13 14
CV: introducción
do i = 0, N-1
C(i) = A(i) + B(i)
enddo
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V2,V1
SV C(R1),V3
Código vectorial
Vectores: - Dirección de
comienzo- longitud- paso (stride)2000 – 2008 – 2016 – 2024 – ... – 2120dir. com. = 2000 / longitud = 16 / paso = 8
UPV-EHU / ATC Arquitecturas Paralelas 12-13 15
CV: introducción
BD L AM M M M E
AM M M M E
AM M M M E
... ... ... ...
AM M M M E
LV V1,A(R1)
BD L AM M M M E E ... ... E
x N
UPV-EHU / ATC Arquitecturas Paralelas 12-13 16
CV: introducción
BD L AM . ... . L M M M E ... ... E
tiN
Tv ≈ ti + N ciclosTE ≈ 7 N ciclos
N = 128, ti = 14
TE = 896 ciclos
Tv = 142 ciclos≈ /6
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V2,V1
SV C(R1),V3
BD L AM M M M E ... ... E
BD L AM M M M E ... ... E
BD . . . . L A A E ... ... EBD L AM . . . L M M M E .... ... E
UPV-EHU / ATC Arquitecturas Paralelas 12-13 17
CV: introducción
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V2,V1
SV C(R1),V3
BD L AM M M M E ... ... E
BD L AM M M M E ... ... E
BD . . . . L A A E ... ... EBD L AM . . . L M M M E .... ... E
Problemas
Memoria: segmentada / núm. buses / módulos
Unidades funcionales: segmentadas / muchas
Reg. vectoriales: tamaño / cantidad / acceso
UPV-EHU / ATC Arquitecturas Paralelas 12-13 18
CV: introducción
Problemas
Programas: ¿Todo operaciones vectoriales? ¿Se pueden vectorizar siempre?
do i = 0, N-1
A(i) = A(i) + 1
enddo
escalarmente: L0 +0 S0 / L1 +1 S1 / ... / LN-1 +N-1 SN-1
vectorialmente: L0 L1 ... LN-1 / +0 +1 ... +N-1 / S0 S1 ... SN-1
¡Hay que desordenar el código original!
UPV-EHU / ATC Arquitecturas Paralelas 12-13 19
Reg.Unidad
funcional
Procesador escalar
(completo)
Memoria
CV: introducción
Esquema lógico de arquitectura vectorial (tomasulo)
Control del procesador vectorial
Unidad de direcciones
(datos)
(op.)
Reg.
UPV-EHU / ATC Arquitecturas Paralelas 12-13 20
CV: introducción
Lenguaje máquinaLV Vi,A(Rj) Vi := M(A+Rj)
SV A(Rj),Vi M(A+Rj) := Vi
VL → longitud del vector VS → paso del vector
OPV Vi,Vj,Vk Vi := Vj OP Vk
OPVS Vi,Vj,Fk Vi := Vj OP Fk
OPVI Vi,Vj,#k Vi := Vj OP #k
MOVI VL,#64
MOVI VS,#8
LV V1,A(R1)
UPV-EHU / ATC Arquitecturas Paralelas 12-13 21
CV: dependencias de datos
Cuando una instrucción necesita el resultado de una instrucción previado i = 0, N-1
A(i) = A(i) + 1
enddo
LV V1,A(R1)
ADDVI V2,V1,#1
SV A(R1),V2
- esperar a que el vector completo esté en un registro y leer a continuación
- hacer cortocircuito E → L, y leer los operandos tan pronto como se pueda: ENCADENAMIENTO (chaining)
UPV-EHU / ATC Arquitecturas Paralelas 12-13 22
CV: dependencias de datos
Sin encadenamiento
LV V1,A(R1)
ADDVI V2,V1,#1
SV A(R1),V2
BD L AM M M M E ... E
BD . . . . . ...L A A E ... E
BD L AM . . ... . . . . . . L M M M E .. . E
TV = 13 + 3N LV
N ADDVI
N SV
N
UPV-EHU / ATC Arquitecturas Paralelas 12-13 23
CV: dependencias de datos
Con encadenamiento
LV V1,A(R1)
ADDVI V2,V1,#1
SV A(R1),V2
BD L AM M M M E ... ... ... ...E
BD . . .
BD L AM . . .
Tv = 13 + NLV
ADDVI
SV
N
L A A E ... ... ... E
L M M M E ... ...E
UPV-EHU / ATC Arquitecturas Paralelas 12-13 24
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V2,V1
SV C(R1),V3
BD L AM M M M E ... ... ... ... E
BD L AM M M M E ... ... ... ... E
CV: dependencias de datos
BD . . . .
BD L AM . . . .
En general, un operando de la unidad funcional (bus) y el otro del banco de registros (se está escribiendo o está escrito)
L A A E ... ... ... E
L M M M E ... ...E
Encadenaminto con dos instrucc.: C = A + B
UPV-EHU / ATC Arquitecturas Paralelas 12-13 25
CV: dependencias de datos
Tablas de ejecución (A = A + 1)
inic. lat. dato 1 dato N
LV V1,A(R1)
ADDVI V2,V1,#1
SV A(R1),V2
Sin encadenamiento
Con encadenamiento
3 3 6+1 6+N
6+N+1 2 9+N+1 9+2N
9+2N+1 3 13+2N+1 13+3N
inic. lat. dato 1 dato N LV V1,A(R1)
ADDVI V2,V1,#1
SV A(R1),V2
3 3 6+1 6+N
[7] 2 9+1 9+N
[10] 3 13+1 13+N
UPV-EHU / ATC Arquitecturas Paralelas 12-13 26
Con
enca
denam
.
inic. lat. dato 1 dato N
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V2,V1
SV C(R1),V3
CV: dependencias de datos
Tablas de ejecución (C = A + B) inic. lat. dato 1 dato N
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V2,V1
SV C(R1),V3
Sin
enca
denam
.
3 3 6+1 6+N
7+N+1 2 10+N+1 10+2N
10+2N+1 3 14+2N+1 14+3N
3 3 6+1 6+N
[8] 2 10+1 10+N
[11] 3 14+1 14+N
4 3 7+1 7+N
4 3 7+1 7+N
UPV-EHU / ATC Arquitecturas Paralelas 12-13 27
CV: dependencias estructurales
¿Están libres los recursos?
- unidades funcionales
ej: se ocuparán N ciclos
Si están ocupados se perderán muchos ciclos (N)
- registros vectoriales
ej: suficientes buses de lectura/escritura- buses de memoria
- módulos de memoria
UPV-EHU / ATC Arquitecturas Paralelas 12-13 28
CV: dependencias estructurales
Buses de memoria¿Cuántos buses hay para acceder a memoria?
LV V1,A(R1)
ADDVI V2,V1,#1
SV A(R1),V2
BD L AM M M M E ... ... ... ... E
BD . . . L A A E ... ... ... . E
BD L AM . . . . ?
Tv ≈ 2 N
LV
ADDVI
SV
bus ocupado
... . L M M M E ...
UPV-EHU / ATC Arquitecturas Paralelas 12-13 29
CV: dependencias estructurales
Un único bus de memoria (A = A + 1)
Con encadenamiento
inic. lat. dato 1 dato N
LV V1,A(R1)
ADDVI V2,V1,#1
SV A(R1),V2
3 3 6+1 6+N
[7] 2 9+1 9+N
[6+N] 3 9+N+1 9+2N
UPV-EHU / ATC Arquitecturas Paralelas 12-13 30
CV: dependencias estructurales
inic. lat. dato 1 dato N
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V2,V1
SV C(R1),V3
Con
enca
denam
iento
3 3 6+1 6+N
[10+N] 2 12+N+1 12+2N
[9+2N] 3 12+2N+1 12+3N
6+N 3 9+N+1 9+2N
Tv ≈ 3 NLV
ADDV
SV
LV
Un único bus de memoria (C = A + B)
UPV-EHU / ATC Arquitecturas Paralelas 12-13 31
CV: dependencias estructurales
Con
enca
denam
iento
inic. lat. dato 1 dato N
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V2,V1
SV C(R1),V3
3 3 6+1 6+N
[8] 2 10+1 10+N
[6+N] 3 9+N+1 9+2N
4 3 7+1 7+N
Tv ≈ 2 NLV
ADDV
SV
LV
Dos buses de memoria (C = A + B)
UPV-EHU / ATC Arquitecturas Paralelas 12-13 32
CV: dependencias estructurales
Módulos de memoria
Conflictos:- una instrucción de memoria consigo misma- una instrucción de memoria con otra(s)
¿Están libres los módulos de memoria que tenemos que utilizar? Si no están libres, habrá que esperar antes de ejecutar las instrucciones LV/SV.
UPV-EHU / ATC Arquitecturas Paralelas 12-13 33
m0
m1m2
m3
4 5 6 7 8 9 10 11 12 13 14 15
CV: dependencias estructurales
Una única operación de memoria
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
¿Cuántos módulos se utilizan? Por lo tanto, no hay problemas, si
nm / MCD(nm,s) ≥ tm
tm = 3 ciclos
nm = 4s = 1
nm / MCD(nm,s)
UPV-EHU / ATC Arquitecturas Paralelas 12-13 34
CV: dependencias estructurales
Padding
A00 A01 A02 A03
- A10 A11 A12
A13 - A20 A21
A22 A23 - A30
A31 A32 A33 -
m0 m1 m2m3
Filass = 1, sin conflictosColumna
ss = 4, conflictos (mi)Diagonal
p. s = 5, sin conflictosDiagonal
m.s = 3, sin conflictos
s = 1, sin conflictoss = 5, sin conflictoss = 6, conflictos
s = 4, conflictos
m0 m1 m2m3A00 A01 A02 A03
A10 A11 A12 A13
A20 A21 A22 A23
A30 A31 A32 A33
UPV-EHU / ATC Arquitecturas Paralelas 12-13 35
CV: dependencias estructurales
Varias operaciones de memoria inic. lat. dato 1 dato N
LV V1,A(R1)
ADDVI V2,V1,#1
SV A(R1),V2
3 3 6+1 6+N
[7] 2 9+1 9+N
[10]
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19m0
m1
m2
m3
m4
m5
m6
m7
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M
M
-
- -M M M
M M M
M M M
M M
UPV-EHU / ATC Arquitecturas Paralelas 12-13 36
CV: dependencias estructurales
¿Cuántos ciclos hay que esperar hasta que se libere el módulo que se quiere utilizar? Hay que generar la lista de módulos ocupados:1. calcular qué módulo va a comenzar a
usar la instrucción j (en memoria desde el ciclo inij) en el ciclo inik :
(inik – inij) + módulo de inicioj2. añadir por delante y por detrás tm-1
módulos3. Si el módulo que va a utilizar la instrucción k está en la lista, esperar los ciclos indicados por la posición en la lista
UPV-EHU / ATC Arquitecturas Paralelas 12-13 37
CV: dependencias estructurales
inic. mod_ocup. t_esp. lat. dato 1 dato N
LV V1,A(R1)
ADDVI V2,V1,#1
SV A(R1),V2
3 3 6+1 6+N
[7] 2 9+1 9+N
[10] - 7 -5, 6 0, 1 3 17+1 17+N4
UPV-EHU / ATC Arquitecturas Paralelas 12-13 38
CV: dependencias estructurales
Longitud de los registros (Lmax)- ¿Qué hacemos si los vectores son más
largos?
do i = 0, N-1
A(i) = A(i) + 1
enddo
MOVI VS,#1
MOVI R1,#N
mas: MOV VL,R1
LV V1,A(R2)
ADDVI V2,V1,#1
SV A(R2),V2
ADDI R2,R2,#Lmax
SUBI R1,R1,#Lmax
BGTZ R1,mas
Tv = N/Lmax (ti + tbuc) + tv N
strip mining
TV = 30 + 3N; N = 500; Lmax = 64; tbuc= 10
→ 8×(30+10) + 1.500 = 1.820 (+19%)
UPV-EHU / ATC Arquitecturas Paralelas 12-13 39
Se utilizan tres parámetros para medir la “velocidad”:
- Tiempo de ejecución (en ciclos o en segundos).
- Velocidad de cálculo: número de operaciones de coma flotante que
se ejecutan por segundo.
- Factor de aceleración (speed-up): cuántas veces más rápida es la
ejecución vectorial que la escalar.
CV: velocidad de cálculo
UPV-EHU / ATC Arquitecturas Paralelas 12-13 40
0
50
100
150
200
250
300
0 25 50 75 100 125 150
N
TV = 30 + 2N
Tv
CV: velocidad de cálculo
Tiempo de ejecución
esc.: TE = te N
vect.: Tv = ti + tv N
ti
pendiente = tv
OJO: son ciclos!Para darlo en segundos hay que multiplicarlo por el periodo (T).
UPV-EHU / ATC Arquitecturas Paralelas 12-13 41
CV: velocidad de cálculo
Velocidad de cálculo RV = N / TV = RV = N / (ti + tvN)
N
R∞
R
R∞/2
N1/2
× OpCF × F MF/s
R∞ = 1 / tv × OpCF × F
N1/2 = ti / tv
N1/2 → R∞ / 2
UPV-EHU / ATC Arquitecturas Paralelas 12-13 42
CV: velocidad de cálculo
Factor de aceleración (speed-up)
KV = TE / TV = te N / (ti + tvN)
K∞ = te / tv
TE = TV
te NV = ti + tv NV → NV = N1/2 / (K∞– 1)
Longitud mínima de vectores
UPV-EHU / ATC Arquitecturas Paralelas 12-13 43
CV: velocidad de cálculo
Influencia del código escalar: ley de Amdahl.Una parte del código vectorialmente, f, y la otra, 1–f, escalarmente
TVE = f TV + (1-f) TE
KVE = TE / TVE
= TE / (f TV + (1–f) TE)
= KV / (KV – f (KV–1))
UPV-EHU / ATC Arquitecturas Paralelas 12-13 44
CV: velocidad de cálculo
Ley de Amdahl
KB = ∞ 16
8
4
2
0
2
4
6
8
10
12
14
16
0 0.2 0.4 0.6 0.8 1
Fac
tor
de
acel
erac
ión
(sp
eed
-up)
f (factor de vectorización)
Ley deAmdahl (KV = 2, 4, 8, 16)
KVE = KV / (KV – f (KV–1))
UPV-EHU / ATC Arquitecturas Paralelas 12-13 45
CV: velocidad de cálculo
Ley de Amdahl
Velocidad de cálculo:
RVE = N / TVE = N / (f TV + (1-f) TE) =
= N / (f (ti + tv N) + (1-f) te N) =
= N / (f (ti + tv N) + (1-f) K∞ tv N) [× OpCF × F]
UPV-EHU / ATC Arquitecturas Paralelas 12-13 46
CV: velocidad de cálculo
Ley de Amdahl
0
2
4
6
8
10
12
14
16
0 0.2 0.4 0.6 0.8 1
fac
tor
de
ac
ele
rac
ión
(no
rma
liza
do
)
ley de Amdahl
CRAY X-MP
tv = 10 ns
te = 66,6ns
tv = 5 ns
te = 66,6 ns
tv= 10 ns
te = 33,3 ns
f (factor de vectorización)
UPV-EHU / ATC Arquitecturas Paralelas 12-13 47
1. Computadores vectoriales
- Introducción- Dependencias de datos- Dependencias estructurales- Velocidad de cálculo
- Técnicas de compilación
- dependencias de datos
- vectorización- optimizaciones
UPV-EHU / ATC Arquitecturas Paralelas 12-13 48
Dependencias de datos
Para poder ejecutar vectorialmente un bucle hay que cambiar el orden original de las instrucciones
escalarmente: L0 +0 S0 / L1 +1 S1 / ... / LN-1 +N-1 SN-1
vectorialmente: L0 L1 ... LN-1 / +0 +1 ... +N-1 / S0 S1 ... SN-1
Ojo: se pueden desordenar las instrucciones, pero hay que respetar las dependencias de datos entre instrucciones!
UPV-EHU / ATC Arquitecturas Paralelas 12-13 49
Dependencias de datos
dependencia
RAW (Rango-Dominio)
(i) A =...
(j) = A
antidependencia
WAR (Dominio-Rango)
(i) = A
... (j) A =
dependencia de salida
WAW (Rango-Rango)
(i) A =...
(j) A =
i j i j i j
Recordad: una dependencia implica un determinado orden entre las operaciones.
dependencias reales dependencias de “nombres”
UPV-EHU / ATC Arquitecturas Paralelas 12-13 50
Dependencias de datos
Dado que trabajaremos con bucles las dependencias de datos se pueden dar entre instrucciones de cualquier iteración.
Si hay una dependencia entre las instrucciones de las iteraciones i1 e i2, diremos que hay una dependencia a distancia i2 – i1.
Las dependencias se representan mediante dos grafos: grafo de dependencias y espacio de iteraciones.
UPV-EHU / ATC Arquitecturas Paralelas 12-13 51
A(2) = B(2) + 2C(2) = A(0) + A(3)
A(3) = B(3) + 2C(3) = A(1) + A(4)
A(4) = B(4) + 2C(4) = A(2) + A(5)
A(5) = B(5) + 2C(5) = A(3) + A(6)
i=2
i=3
i=4
i=5
Dependencias de datos
do i = 2, N-21 A(i) = B(i) + 22 C(i) = A(i-2) + A(i+1)
enddo
1
2
A,2
A,1
Bucles de una dimensión
Grafo de dependencias
iEspacio de iteraciones
UPV-EHU / ATC Arquitecturas Paralelas 12-13 52
Dependencias de datos
Vectores de dos dimensiones
do i = 2, N-1 do j = 1, N-2 1 A(i,j) = A(i,j-1) * 2 2 C(i,j) = A(i-2,j+1) + 1 enddoenddo
1
2
A,(2,-1)
A(0,1)
i
j
UPV-EHU / ATC Arquitecturas Paralelas 12-13 53
Dependencias de datos
do i = 2, N-311 A(i) = B(i) + 22 C(i) = A(i-2)3 D(i+1) = C(i) + C(i+1)4 B(i+1) = B(i) + 15 D(i+30) = A(i)enddo
1
2
3
4
5
A,0
A,2
C,0 C,1
D,29
B,1
B,1
Otro ejemplo
UPV-EHU / ATC Arquitecturas Paralelas 12-13 54
Vectorización
do i = 0, N-1 A(i) = B(i) + C(i)enddo
MOVI VL,#NMOVI VS,#1
LV V1,B(R1)LV V2,C(R1)ADDV V3,V1,V2SV A(R1),V3
Ejemplo 1
Veamos mediante unos ejemplos cómo generar el código vectorial
UPV-EHU / ATC Arquitecturas Paralelas 12-13 55
Vectorización
do i = 0, N-1 A(i) = B(i) + C(i) D(i) = A(i)enddo
MOVI VL,#NMOVI VS,#1
LV V1,B(R1)LV V2,C(R1)ADDV V3,V1,V2SV A(R1),V3
LV V2,A(R1)SV D(R1),V3
Ejemplo 2
1
2
A,0
i
MOVI VL,#NMOVI VS,#1
LV V1,B(R1)LV V2,C(R1)ADDV V3,V1,V2SV A(R1),V3
SV D(R1),V3
UPV-EHU / ATC Arquitecturas Paralelas 12-13 56
Vectorización
do i = 1, N-1 A(i) = B(i) + C(i) D(i) = A(i-1)enddo
MOVI VL,#N-1MOVI VS,#1
LV V1,B+1(R1)LV V2,C+1(R1)ADDV V3,V1,V2SV A+1(R1),V3
LV V4,A(R1)SV D+1(R1),V4
Ejemplo 3
1
2
A,1
i
UPV-EHU / ATC Arquitecturas Paralelas 12-13 57
Vectorización
do i = 0, N-2 A(i) = B(i) + C(i) D(i) = A(i+1)enddo
Ejemplo 4
1
2
i
A,1
MOVI VL,#N-1MOVI VS,#1
LV V2,B(R1)LV V3,C(R1)ADDV V4,V2,V3SV A(R1),V4
LV V1,A+1(R1)
SV D(R1),V1
MOVI VL,#N-1MOVI VS,#1
LV V1,A+1(R1)SV D(R1),V1
LV V2,B(R1)LV V3,C(R1)ADDV V4,V2,V3SV A(R1),V4
UPV-EHU / ATC Arquitecturas Paralelas 12-13 58
Vectorización
do i = 1, N-1 A(i) = B(i-1) + 1 B(i) = A(i)enddo
Ejemplo 5
1
2
A,0
B,1
do i = 3, N-1 A(i) = A(i-3) * 3enddo
1
A,3
UPV-EHU / ATC Arquitecturas Paralelas 12-13 59
Vectorización
do i = 0, N-1 do j = 0, M-1 A(i,j) = B(i,j) + C(i,j) enddoenddo
Ejemplo 6: vectores de dos dimensiones (filas)
MOVI R2,#NMOVI VL,#MMOVI VS,#1
buc: LVV1,B(R1)LVV2,C(R1)ADDVV3,V1,V2SVA(R1),V3
ADDIR1,R1,#MSUBIR2,R2,#1BNZ R2,buc
0,0 0,1 ... 0,M-1
1,0 1,1 ... 1,M-1
... ... ... ...
N-1,0 N-1,1 ... N-1,M-1
As=1
UPV-EHU / ATC Arquitecturas Paralelas 12-13 60
Vectorización
do i = 0, N-1 do j = 0, M-1 A(i,j) = B(i,j) + C(i,j) enddoenddo
MOVI R2,#MMOVI VL,#NMOVI VS,#M
buc: LVV1,B(R1)LVV2,C(R1)ADDVV3,V1,V2SVA(R1),V3
ADDIR1,R1,#1SUBIR2,R2,#1BNZ R2,buc
0,0 0,1 ... 0,M-1
1,0 1,1 ... 1,M-1
... ... ... ...
N-1,0 N-1,1 ... N-1,M-1
A
s=M
Ejemplo 6: vectores de dos dimensiones (columnas)
UPV-EHU / ATC Arquitecturas Paralelas 12-13 61
Vectorización
Condición para poder vectorizar un bucle:
Las dependencias entre instrucciones no forman ciclos en el grafo de dependencias
En general, algunas instrucciones de un bucle se pueden ejecutar de manera vectorial pero puede que otras no (“fisión”):
UPV-EHU / ATC Arquitecturas Paralelas 12-13 62
Vectorización
do i = 1, N-1 A(i) = B(i) B(i) = B(i-1)enddo
1
2
B,0
B,1
MOVI VL,#N-1MOVI VS,#1
LVV1,B+1(R1)SVA+1(R1),V1
MOVI R3,#N-1
buc: LDF1,B(R2)STB+1(R2),F1ADDIR2,R2,#1SUBIR3,R3,#1BNZ R3,buc
UPV-EHU / ATC Arquitecturas Paralelas 12-13 63
Test de dependencias
¿Quién se encarga del análisis de dependencias? El programador o el compilador.
do i = L1, L2 X(a*i+b) = = X(c*i+d)enddo
L1 L2
i
a*i+b
c*i+d
Automáticamente, sólo funciones lineales de los índices de los bucles
d - bMCD(c,a)
Z → no hay depend.
UPV-EHU / ATC Arquitecturas Paralelas 12-13 64
Test de dependencias
iL1 L2
iL1 L2iL1 L2
UPV-EHU / ATC Arquitecturas Paralelas 12-13 65
Test de dependencias
do i = 1, 100 A(2*i) = ... ... = A(2*i+1)enddo
(1 – 0) / MCD(2, 2) = 1/2 → no
do i = 5, 100 A(i-5) = ... ... = A(2*i+90)enddo
(90 – (-5)) / MCD(2, 1) = 95 → ¿si?
wr: A0 ... A95
rd: A100 ... A290
UPV-EHU / ATC Arquitecturas Paralelas 12-13 66
Test de dependencias
do i = 1, 100 A(3*i+100) = ... ... = A(2*i-1)enddo
((-1) – 100) / MCD(2, 3) = 101 → ¿si?
do i = 1, 100 A(6*i+3) = ... ... = A(3*i+81)enddo
(81 – 3) / MCD(3, 6) = 26 → ¿si?
wr: A103 ... A400
rd: A1 ... A199
i=1, wr A103; i=52, rd A103
wr: A9 ... A603
rd: A84 ... A381
i=14, wr A84; i=1, rd A84
i=26, wr A159; i=26, rd A159
i=27, wr A165; i=28, rd A165
UPV-EHU / ATC Arquitecturas Paralelas 12-13 67
Test de dependencias
¡Ojo! el paso de los accesos a memoria puede indicarse en dos sitios: en la definición de los límites del bucle o en el índice de acceso al vector.Antes de aplicar la prueba MCD hay que normalizar los bucles (paso del bucle a 1).
do i = 1, 100, 2 A(i) = ... B(2*i+5) = ...enddo
do k = 1, 50 A(2*k-1) = ... B(4*k+3) = ...enddo
UPV-EHU / ATC Arquitecturas Paralelas 12-13 68
Vectorización
ResumiendoPara saber si los bucles se pueden ejecutar vectorialmente hay que analizar dependencias entre instruccionesEl análisis de dependencias lo hará el compilador vectorial cuando el paso de los accesos sea constanteSe puede utilizar la prueba MCD para saber si no puede haber dependenciaLas instrucciones se pueden vectorizar si no están dentro de un ciclo de dependencias
UPV-EHU / ATC Arquitecturas Paralelas 12-13 69
Optimizaciones
El análisis automático de dependencias no es sencillo. Si el compilador no puede decidir si existe o no dependencia, supondrá por si acaso que hay dependencia.
Por otro lado, es muy importante que el factor de vectorización sea alto (Amdahl).
Por lo tanto, se suelen aplicar diferentes transformaciones u optimizaciones para facilitar el proceso de vectorización.
Las optimizaciones principales son las siguientes:
UPV-EHU / ATC Arquitecturas Paralelas 12-13 70
Optimizaciones
1 Sustitución global hacia adelantePara facilitar el análisis de dependencias hay que sustituir todas las definiciones llevadas a cabo.
NP1 = L+1NP2 = L+2...do i = 1, L B(i) = A(NP1) + C(i) A(i) = A(i) – 1 do j = 1, L D(j,NP1) = D(j-1,NP2)*C(j) +1 enddoenddo
L+1
L+1 L+2
UPV-EHU / ATC Arquitecturas Paralelas 12-13 71
Optimizaciones
2 Variables de inducciónDentro del bucle hay que sustituir las variables que van modificándose en progresión aritmética.
j = 2k = 2do i = 1, L j = j + 5 R(k) = R(j) + 1 k = k + 3enddo
i = 1 2 3 4 5 ...
j = 7 12 17 22 27 ...
k = 2 5 8 11 14 ...
j = 5*i+2
k = 3*i-1
do i = 1, L R(3*i-1) = R(5*i+2) + 1enddo
¡Ojo!: valor final de i, j y k !!!
UPV-EHU / ATC Arquitecturas Paralelas 12-13 72
Optimizaciones
3 Antidependencias
do i = 0, N-2 A(i) = B(i) + C(i) D(i) = A(i) + A(i+1)enddo
1
2
A,0
A,1
do i = 0, N-2 [T(i)] = A(i+1) A(i) = B(i) + C(i) D(i) = A(i) + [T(i)]enddo
A,0
T,0
1
2
0
A,1
UPV-EHU / ATC Arquitecturas Paralelas 12-13 73
Optimizaciones
3 Antidependencias
do i = 0, N-2 A(i) = B(i) + C(i) D(i) = A(i) + A(i+1)enddo
1
2
A,0
A,1
MOVI VL,#N-1MOVI VS,#1
(2/0) LVV1,A+1(R1)
(1) LVV2,B(R1)LVV3,C(R1)ADDVV4,V3,V2SVA(R1),V4
(2) ADDVV5,V1,V4SVD(R1),V5
UPV-EHU / ATC Arquitecturas Paralelas 12-13 74
T,0
Optimizaciones
4 Dependencias de salida
do i = 0, N-3 A(i) = B(i) + C(i) A(i+2) = A(i) * D(i)enddo
T,0
1
2
01
2
A,0
A,2A,2
do i = 0, N-3 [T(i)] = B(i) + C(i) A(i+2) = [T(i)] * D(i) A(i) = [T(i)]enddo
UPV-EHU / ATC Arquitecturas Paralelas 12-13 75
Optimizaciones
4 Dependencias de salida
do i = 0, N-3 A(i) = B(i) + C(i) A(i+2) = A(i) * D(i)enddo
1
2
A,0
A,2
MOVI VL,#N-2MOVI VS,#1
(1) LVV1,B(R1)LVV2,C(R1)ADDVV3,V2,V1
(2) LVV4,D(R1)MULVV5,V3,V4SVA+2(R1),V5
(1/3) SVA(R1),V3
UPV-EHU / ATC Arquitecturas Paralelas 12-13 76
Optimizaciones
5 Intercambio de bucles
do i = 0, N-1 do j = 1, N-1 A(i,j) = A(i,j-1) + 1 enddoenddo
1
A,(0,1)
i
j
no
sí
do j = 1, N-1 do i = 0, N-1 A(i,j) = A(i,j-1) + 1 enddoenddo
UPV-EHU / ATC Arquitecturas Paralelas 12-13 77
Optimizaciones
5 Intercambio de bucles
do i = 1, N-1 do j = 1, N-2 A(i,j) = B(i-1,j+1) + 1 B(i,j) = A(i,j-1) enddoenddo
1
2
A (0,1)
B (1,-1)
i
j
UPV-EHU / ATC Arquitecturas Paralelas 12-13 78
Optimizaciones
5 Intercambio de bucles
Se pueden intercambiar los bucles si en los nuevos vectores de distancia de las dependencias, el primer componente que no es 0 es positivoPor ejemplo,
(0, 1)→ (1, 0) sí se puede(1, -1) → (-1, 1) no se puede
UPV-EHU / ATC Arquitecturas Paralelas 12-13 79
Optimizaciones
5 Intercambio de bucles
A veces hay que combinar el intercambio y la fisión:
do i = 1, N-1 do j = 1, N-1 A(i,j) = A(i-1,j) + 1 B(i,j) = B(i,j-1) * 2 enddoenddo
i
j
2
B,(0,1)
1
A,(1,0)
UPV-EHU / ATC Arquitecturas Paralelas 12-13 80
Optimizaciones
En otros casos merece la pena realizar el intercambio de bucles por cuestiones de eficiencia.
do i = 0, 99 do j = 0, 9 A(i,j) = A(i,j) + 1 enddoenddo
A0,0 ... A0,9
... ...
... ...
... ...
A99,0 .. A99,9
5 Intercambio de bucles
UPV-EHU / ATC Arquitecturas Paralelas 12-13 81
Optimizaciones
6 Expansión escalar
La utilización de escalares dentro del bucle impide vectorizarlo.
do i = 0, N-1 suma = A(i) + B(i) C(i) = suma * suma D(i) = suma * 2enddo
¡Ojo!, al final: suma = suma(N-1)
(i)(i) (i)(i)
UPV-EHU / ATC Arquitecturas Paralelas 12-13 82
Optimizaciones
7 Fusión de bucles
Si se puede, es conveniente juntar dos bucles en uno.
do i = 0, N-1 A(i) = B(i) + C(i)enddo
do i = 0, N-1 D(i) = E(i) * 5enddo
do i = 0, N-1 A(i) = B(i) + C(i) D(i) = E(i) * 5enddo
¡Ojo! hay que respetar el significado (dependencias!)
UPV-EHU / ATC Arquitecturas Paralelas 12-13 83
Optimizaciones
7 Fusión de bucles
do i = 0, N-2 A(i) = B(i) + C(i)enddo
do i = 0, N-2 D(i) = A(i+1) + 1enddo
do i = 0, N-2 A(i) = B(i) + C(i) D(i) = A(i+1) + 1enddo
No son iguales
UPV-EHU / ATC Arquitecturas Paralelas 12-13 84
Optimizaciones
8 Colapso de bucles
Convertir el bucle de dos dimensiones en un bucle de 1 sola dimensión para procesar vectores más largos
float A(10,10)
do i = 0, 9 do j = 0, 9 A(i,j) = A(i,j) * 2.0 enddoenddo
float A(10,10)
do i = 0, 99 A(i) = A(i) * 2.0enddo
UPV-EHU / ATC Arquitecturas Paralelas 12-13 85
Optimizaciones
Recordar que tras la finalización del bucle (aunque se haya utilizado alguna optimización) hay que restaurar:
Índices
Variables de inducción Variables temporales Escalares…
UPV-EHU / ATC Arquitecturas Paralelas 12-13 86
Registros de máscara
Ocurre a menudo que solo se procesan unos elementos del vector para hacer algunos cálculos
do i = 0, N-1 if (B(i)>5) A(i) = A(i) + 1enddo
Solución habitual: máscaras (VM, vector mask)
registro binario VM : 1 – hay que procesarlo
0 – hay que enmascarar
UPV-EHU / ATC Arquitecturas Paralelas 12-13 87
Registros de máscara
Primero se genera la máscara, normalmente tras una operación de comparación; luego, se ejecuta la operación vectorial teniendo en cuenta el registro de máscara.
- Para cargar VM (comparación):
SxxV V1,V2
SxxVS V1,F1
- Para inicializar VM (bits a 1)
CVM
- Para contar 1s en VM: POP R1,VM
MOVI VL,#NMOVI VS,#1
MOVI F1,#5LV V1,B(R1)SGTVS V1,F1
LV V2,A(R1)ADDVI V3,V2,#1SV A(R1),V3
CVM
UPV-EHU / ATC Arquitecturas Paralelas 12-13 88
Vectores de índice
Hasta el momento hemos procesado vectores de paso constante (VS).
LV V1,A(R1) VL componentes, a distancia VS, a partir de la dirección A+R1
En algunos casos hay que procesar vectores con paso variable.
s=3
5
14
4
1 8¿Cómo?
UPV-EHU / ATC Arquitecturas Paralelas 12-13 89
Vectores de índice
Para procesar vectores de paso variable, se utilizan vectores de índice (y como modo de direccionamiento el indexado):
LVI V1,A(V2) V2 es el registro de índices e indica las posiciones de los componentes que hay que procesar
SVI A(V2),V1
CVI V1,R1 0, R1,2R1... generar el vector de índices (accesos frecuentes)
UPV-EHU / ATC Arquitecturas Paralelas 12-13 90
Vectores de índice
do i = 0, M A(i*i) = B(i*i) + 1enddo
En general, el tiempo de ejecución de estas operaciones es mayor (no se llega a un componente por ciclo) que el de los accesos normales (paso constante).
MOVI VL,#M+1
MOVI R1,#1CVI V4,R1MULV V5,V4,V4
LVI V1,B(V5)ADDVI V2,V1,#1SVI A(V5),V2
UPV-EHU / ATC Arquitecturas Paralelas 12-13 91
Vectores de índice
Direccionamiento indexado mediante “maskaras”
MOVI VL,#NMOVI VS,#1MOVI F1,#5
LV V1,B(R1)SGTVS V1,F1
MOVI R2,#1CVI V2,R2POP R1,VMMOV VL,R1CVM
LVI V3,A(V2)ADDVI V4,V3,#1SVI A(V2),V4
do i = 0, N-1 if (B(i)>5) A(i) = A(i) + 1enddo
VM = 1 0 0 1 1 1 0 1V2 = 0 3 4 5 7R1 = 5
UPV-EHU / ATC Arquitecturas Paralelas 12-13 92
Resumen
Los procesadores vectoriales son arquitecturas para procesar vectores de manera eficiente. Tienen las siguientes características:
▪ Lenguaje máquina específico para procesar un vector mediante una única instrucción.
▪ Gran ancho de banda para lectura/escritura en memoria.
▪ Unidades funcionales segmentadas (muchas).
▪ La ejecución de las instrucciones se encadena.
▪ Buenos compiladores para generar código vectorial.
UPV-EHU / ATC Arquitecturas Paralelas 12-13 93
Resumen
Hasta hace “poco”, los supercomputadores eran computadores vectoriales, pero hoy las máquinas rápidas son de tipo MIMD.
Pueden ser nodos de sistemas paralelos MIMD especializados en calculo vectorial.
Todos los procesadores actuales cuentan con operaciones “vectoriales” en el conjunto de instrucciones. Por ejemplo (PA-RISC): FMAC, multiply-accumulate
top related