Post on 05-Jan-2016
description
Arquitecturas Avanzadas Curso 10/11
1 INTRODUCCIÓN
2 CONECTIVIDAD
3 MÁQUINAS MIMD
4 MÁQUINAS SIMD
5 AUMENTO DE PRESTACIONES
Horas
5
6
7
2
3
arqAva Clasificación de Flynn Ampliada Introducción-2
Arquitecturas Paralelas
SISD SIMD MISD MIMD
Multi-procesadores
Multi-computadores
MPP COW
Von Neumann
ProcesadoresVectoriales
Array de Procesadores
Sistólicos
UMA NUMACOMA
Distintas formas de organizar la memoria común
??
Beowulf
Symetric
Multi
Processor
Distributed Shared Memory
arqAva Temario SIMD-3
3 MÁQUINAS SIMD
1 Procesamiento Sistólico1 Introducción2 Metodología3 Ejemplos
2 Procesamiento Vectorial1 Definiciones y tipos de instrucciones2 Memorias entrelazadas3 Funciones vectoriales compuestas4 Encadenamiento Hardware
Bibliografía:“VLSI Array Processors” S.Y. Kung-1988 [119..149]
“Advanded Computer Architecture...” Kai Hwang-1993 [Capítulo 8]
arqAva Sistólicos (Introducción) SIMD-4
INTRODUCCIÓN
• Límites de MIMD para grano fino
• El modelo sistólico
• Ejemplo Vector x Matriz
• Algunos inconvenientes
• Ejemplos de máquinas
arqAva Introducción (Límites de MIMD para grano fino)SIMD-5
Problema: Multiplicar una secuencia muy grande de vectores poruna matriz
• Filtrado de imagen
• Generación de efectos de vídeo
• Conversión, cod/decod de vídeo
• Manipulación de imagen en 3D
• Procesado de imágenes médicas
• Reconocimiento de objetos detectando bordes
• Filtros FIR para sistemas de comunicaciones
Algunasaplicaciones
arqAva Introducción (Límites de MIMD para grano fino)SIMD-6
Problema: Multiplicar una secuencia muy grande de vectores poruna matriz
..... Xi4, ..... X2
4, X14 * A4x4 ==> ..... Yi
4, ..... Y24, Y1
4
(x1,x2,x3,x4)i *
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
= (y1,y2,y3,y4)i
x1a11+x2a21+x3a31+x4a41 x1a14+x2a24+x3a34+x4a44
¿Tiempo de cálculo de Yi4 en monoprocesador?
T(*) => 2 T(+) => 1T(Mem <==> Reg) => 1
T(Yi4) = 16*2+12*1+20*1+4*1 = 68
(*) (+) (r) (w)
arqAva Introducción (Límites de MIMD para grano fino)SIMD-7
Paralelización de X4*A4x4 con multiprocesadores
1 3 2 -1xx1 x2 x3 x4
.
.X2
X1
P11 . . P14
. P22 . . . . . .P41 . . P44
3 5 -1 4
2 7 3 -2
4 0 1 5
8 6 9 -3
0
0 => Cargar coeficientes y
P11 P12 P13 P14
9 20 1 11
y1 y2 y3 y4
2
2
2 => 4 P1i suman
Y1 Y2 . . . . . .
3 5 -1 4
6 21 9 -6
8 0 2 10
-8 -6 -9 3
1
1
1 => 16 Pij multiplican
¿Cada cuántotiempo obtengo Yi?
-- Código de P1irepeat
-- Multiplicar
-- Sumar
arqAva Introducción (Límites de MIMD para grano fino)SIMD-8
Hagamos los cálculos:repeat
[i,j] := X[i] * A[i,j] -- Los 16 Pij T1
Y[i] := [1,i]+[2,i]+[3,i]+[4,i] -- Los 4 P1i T2
forever
T1 = 1(r) + 2(*) + 1(w) = 4
T2 = 3(r) + 3(+) + 1(w) = 711 ¿SEGURO?
B(SP1i); B(SP1i); B(SP1i);
Subir (SNuevoY);
Bajar (SNuevoX);
¡ Sincronizar !
¿Conflictos de accesos paralelos a datos comunes?
• El tiempo puede dispararse 20 ....Barreras de sincronización Hw.
• ¿Mejorable con multicomputadores?
arqAva Introducción (Límites de MIMD para grano fino)SIMD-9
Paralelización de X4*A4x4 con multicomputadores
1 3 2 -1xx1 x2 x3 x4
3 5 -1 4
2 7 3 -2
4 0 1 5
8 6 9 -3
y 9 20 1 11
y1 y2 y3 y4
3 5 -1 4
2 7 -23
8 6 -39
4 0 51
S=I*A21+N
1
33
92
17-1
9
? ? * + ! !
Coste
2 1 9 • ¿Será alcanzable 4?
Sistólicos
12..
3
1 1 1
3
2
5 -1
26
26-1
2
3
8
4
D=I¿Flujo E/S?
Xi / Yi
arqAva Introducción (El modelo sistólico) SIMD-10
1978 (H.T. Kung y C.E. Leiserson) Mucho interés en los 80
Objetivo: Aprovechar el alto grado de paralelismo espacial y temporal de algunos algoritmos muy demandados y limitados por cómputo
....X43, X4
2, X41 *
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
= .... Y43, Y4
2, Y41
8 (E/S) vs 28 (*/+)
Aplicaciones: Computación científica, procesado de señal e imagen,análisis de datos biológicos, criptografía, etc.
Flujo
Datos
Yale, Carnegie Mellon, MIT
arqAva Introducción (El modelo sistólico) SIMD-11
Sistólicos: Máquinas paralelas de propósito específico:
• Paralelismo masivo y descentralizado (Pipeline)
• Peso del cómputo mucho mayor que el de E/S
• Comunicaciones locales
Arquitectura regular y modular organizada como una red de un gran número de unidades de proceso idénticas (celdas), conectadas localmente.
Sólo las celdas de los bordes pueden comunicarse con el exterior.
• Modo de operación síncrono
• Factores de posibilidad (VLSI, CAD) y muy escalables
HOSTARQUITECTURA
SISTÓLICA
Trabajos
Resultados
arqAva Introducción (El modelo sistólico) SIMD-12
Ejemplos de redes sistólicas
arqAva Introducción (El modelo sistólico) SIMD-13
Modo de operación síncrono
t0 t1 t2 t3 t4 ...........
3
Cada celda siempre hace lo mismo:
• Recibe datos de sus vecinos
• Realiza unos cálculos sencillos
• Transmite resultados a sus vecinosParalelo
• Recibe datos de sus vecinos
• Realiza unos cálculos sencillos
• Transmite resultados a sus vecinos
i
i+1
i+2
En cada ciclo (), dos fases:
1 Intercambio de datos 2 Cálculo
arqAva Introducción (Ejemplo Vector * Matriz) SIMD-14
¿Cómo utilizar esta arquitectura para multiplicar Vectores2 * Matriz2x2?
Recordar el intento de paralelización con multicomputadores
aij
N
S
DI1 ?I, ?N, !S, !D
2 S = (I*aij)+N, D = I
Propagación de las Xi
a22
a11 a12
a21
0 0t0
x11
Situación justo al
inicio del ciclo
x11a11
a22
a11 a12
a21
0 0t1
x12 x1
1
x21
arqAva Introducción (Ejemplo Vector * Matriz) SIMD-15
x11a11
x12 x1
1
x21
t1
x12a11
x13 x1
2
x22
t2
x21
y11
x11a12 x1
3a11
x14 x1
3
x23
t3
x22
y12
x12a12
y21
x14a11
x15 x1
4
x24
t4
x23
y13
x13a12
y22
x1ia11
x1i+1 x1
i
x2i
ti
x2i-1
Y1i-1
x1i-1a12
Y2i-2
arqAva Introducción (Ejemplo Vector * Matriz) SIMD-16
¿Tiempo de cálculo de Yi4 con este método?
x11x1
2
x21
x13
x22
x31
x14
x23
x32
x41
x15
x24
x33
x42
t0
x1i+1
x2i
x3i-1
x4i-2
ti
y11
y12 y2
1
y13 y2
2 y31
y14 y2
3 y32 y4
1
y15 y2
4 y33 y4
2
t4Obtenemos un resultado cada ciclo ()
Transferir datos => 1Multiplicar => 2Sumar => 1
Total => 4 ¿Tiempos creíbles?
arqAva Introducción (Ejemplo Vector * Matriz) SIMD-17
Posible aspecto de una celda:
* +
Ck
Ck
Ck
Ckaij
arqAva Introducción (Algunos inconvenientes) SIMD-18
• Dificultad algorítmica (Veremos una sistematización)
• Sincronismo de reloj (Sesgo de reloj | Clock Skew)
Ck
¿Soluciones?
Ck
Distribuciónregular de Ck
• Frente de Ola | Wave Front
Asíncronos
Flujo de Datos vs Flujo de Control
arqAva Introducción (Ejemplos de máquinas) SIMD-19
• iWarp (1988-1992)
Carnegie Mellon Univ. + Intel Supercomputing System Div.
Todavía la mejor en 1995 para algunas aplicaciones
µP RISC de 32 bits de 96bit LIW a 20MHz
Desde 4 a 1024 celdas. Típico un toro de 8x8 => 64µP
www-2.cs.cmu.edu/~iwarp
iPSC
“iWarp: Anatomy of a Parallel Computing System” 1998
arqAva Introducción (Ejemplos de máquinas) SIMD-20
• SAMBA (1993-1995) www.irisa.fr/SAMBA
Systolic Accelerator for Molecular Biological Applications
Laboratorio IRISA de Rennes
1994 => Chips con 4µP de 100MIPS (12bits) (Total 128µP)
1998 => “Speeding up genome computations with a systolic accelerator”
Estudio genético => 41’ en SAMBA y 127,5h en una WorkStation
1998 => Chips con 16..20µP más MIPS => Todo en una tarjeta PCI
arqAva Introducción (Ejemplos de máquinas) SIMD-21
GeneMatcher2:
192 P SIMD
Empresa comprada en junio 2000
por Celera Genomics Group.
www.celera.com
• … GeneMatcher2 … 2004]
www.paracel.com
Sistema de análisis de similitud de secuencias genéticas.
Acelerador => 3.072..221.184 P
arqAva Introducción (Ejemplos de máquinas) SIMD-22
• Procesador CSX700 [Hoy]
www.clearspeed.com
“Convierta su PC en un supercomputador”
96 GFlops y < 9 W
96 96
#9 Top500 11/06TSUBAMEGrid Cluster
#29 Top500 11/08#56 Top500 11/09
+ GPU’s
arqAva Introducción (Ejemplos de máquinas) SIMD-23
• DeCypher Engine G4 => SeqCruncher [Hoy]
www.timelogic.com
4
128 Xeon
arqAva Introducción (Ejemplos de máquinas) SIMD-24
• Cell [Hoy] www.blachford.info/computer/Cell/Cell0_v2.html
QS21
arqAva Introducción (Ejemplos de máquinas) SIMD-25
• GPU’s[Hoy] www.nVidia.com
240
Tesla C1060
*4
Tesla S1070
*170
TSUBAME
arqAva Vectoriales (Definiciones) SIMD-26
DEFINICIONES
Vector: Conjunto ordenado de unidades de datos escalares de un mismo tipo
Vectorización
Conversión de código escalar a vectorial
Proporción de vectorización
Grado de vectorización alcanzado
Compilador vectorial
Traductor diseñado para vectorizar código
Procesador vectorial: Conjunto de elementos hardware diseñado para procesar vectores
• Un resultado por ciclo
• Menor overhead control bucle por software
• Menos conflictos de accesos a memoria
arqAva Vectoriales (Definiciones) SIMD-27
Vector: Conjunto ordenado de unidades de datos escalares de un mismo tipo
short V1[5]; long V2[5]; tPersona V3[5];
V1[0]$1000
V1[2]V1[1]
V1[3]V1[4]
V2[0]$1000
V2[1]
V2[2]
V2[3]
V2[4]
$1006
$1002$1004
$1008
$1004
$1008
$100C
$1010Stride 2
Stride 4
$1004
V4[0]$1000
V4[2]
V4[1]
V4[3]
V4[4]
$1008
$100C
$1010
¿Vector V4?
Stride 4
Stride
tsize(tipo)
¿Utilidad?
arqAva Tipo / Fuentes (Control, Datos, Flujo) Introducción-28
• PARALELISMO DE DATOS (Espacial)
– Operaciones sobre datos regulares (vectores) aplicando la misma operación sobre cada elemento
En los procesadores vectoriales hay poca replicación hardware (pocas unidades de proceso que sumen). En su lugar, se apoyan
en una especialización mediante pipeline.
2 1 3 1 4 5 7 8
3 4 6 1 0 2 1 1
5 5 9 2 4 7 8 9
+ + + + + + + +
A
C
B
Suma de Vectores, etc.
¡LIMITACIONES!
Más datos que U.P.
Operaciones escalares
arqAva Vectoriales (Definiciones) SIMD-29
2 1 3 1 4 5 7 8
3 4 6 1 0 2 1 1 5 5 9 2 4 7 8 9
A
CB
8+1
8+1
8+1
8+1
8+1
7+1
8+1
7+1
8+1
5+2
7+1
8+1
5+2
4+0
98
7+1
1+1
5+2
4+0
7
3+6
1+1
5+2
4+0
Unidad FuncionalAritmética Segmentada
4 Etapas: Sumar ExponentesMultiplicar MantisasNormalizarRedondear
Un resultado por ciclo
Registros Vectoriales
TIPOS DE INSTRUCCIONES VECTORIALES
S x Vk Vi
Escalar-Vector Vi
Vk
S
M V
V M
Memoria-Vector, Vector-Memoria
VMemoria
arqAva Vectoriales (Tipos de instrucciones) SIMD-30
Vector-VectorVi Vj
Vj x Vk Vi
Vi
Vk
Vj
Unidad funcional segmentada
Vector reducciónVi S , Vj x Vk S S
Vk
Vj
130
410
56
20
etc.
Compresión (gather recoger)M Vj x Vk
410
769
130
49
46
20
56 200
201
202
206
203
205
204
etc.
etc.
memoriaVk
4
2004
3
0
6
etc.
VjVL
A0
arqAva Vectoriales (Tipos de instrucciones) SIMD-31
¿Utilidad?
Expansión (scatter esparcir)
4
200130
410
56
20
etc.
4
1
2
5
etc.
xx
56
130
410
20
xx
xx 200
201
202
206
203
205
204
etc.
etc.Vj Vk
memoriaVj x Vk M
VL
A0
arqAva Vectoriales (Tipos de instrucciones) SIMD-32
MPI_ScatterMPI_GatherMPI_Reduce
MPI
Máscara (masking)
7
230
0
91
66
etc.
VkVk x Vm Vi
0
56
0
VL
arqAva Vectoriales (Tipos de instrucciones) SIMD-33
1011001......6
3
xx
2
xx
xx
0 200
201
202
206
203
205
204
etc.
Vi
VM ¿Utilidad?
¿Utilidad VM?
arqAva Vectoriales (Memorias entrelazadas) SIMD-34
¿Memoria multipuerto?
Vectorial
M.P.
¿Un único pipe? Vectorial
Patrón de acceso a MP
¡ Demasiado secuencial !
Acceso a bloques:• Instrucciones• Arrays• Líneas de caché
¿ Acceso paralelo al vector V[16] ?
M0 M1 M7
V[0] V[1] V[7]
V[8] V[9]
palabra módulon 3 Entrelazado
ordeninferior
¿Cuántos bancos?
arqAva Vectoriales (Memorias entrelazadas) SIMD-35
Para acceder a un vector en memoria (longElemento = palabra):
DirInicio, NumElementos, Stride (Separación entre elementos)
Entrelazado de orden inferior: Acceso Concurrente
Memoria de 2a+b palabras, # de módulos: m=2a, Palabras por módulo: w=2b
palabra módulo
aDirección de memoria
b
0
m
m(w-1)
2m
RIM
M0
1
m+1
m(w-1)+1
2m+1
RIM
M1
m-1
2m-1
wm-1
3m-1
RIM
Mm-1
decodificador
RDM
arqAva Vectoriales (Memorias entrelazadas) SIMD-36
M0
M2
M1
M5
M4
M3
M6
M7
Módulos
Tiempo
t de acceso () t de transmisión ()
Stride=1 ¿Stride=2? Pérdida de eficiencia
¿Stride = 3? Sin pérdida de eficiencia
t total de un vector grande (m)
¡ Ojo al ubicar matrices en memoria !
0
m
m(w-1)
2m
RIM
M0
1
m+1
m(w-1)+1
2m+1
RIM
M1
m-1
2m-1
wm-1
3m-1
RIM
Mm-1
módulopalabra
bDirección de memoria
a
arqAva Vectoriales (Memorias entrelazadas) SIMD-37
Multiplexador
Ciclo debúsqueda
Ciclo deacceso
Entrelazado de orden inferior: Acceso Simultáneo
Memoria de 2a+b palabras, # de módulos: m=2a, Palabras por módulo: w=2b
arqAva Vectoriales (Memorias entrelazadas) SIMD-38
M0
M2
M1
M5
M4
M3
M6
M7
Módulos
Tiempo
‘m’ palabras (8)
Ciclo de búsqueda
Ciclo de acceso
Pérdida de eficiencia para Stride 1
arqAva Vectoriales (Funciones vectoriales compuestas)SIMD-39
FUNCIONES VECTORIALES COMPUESTAS
BUCLE I=1 HASTA 100
CARGA R1,X(I)
CARGA R2,Y(I)
MULTIPLICA R1,S
SUMA R2,R1
ALMACENA Y(I), R2
FIN BUCLE
Carga de Vector
Escalar x Vector
Carga de Vector
Suma vectorial
Almacenamiento de Vector
Y(I) = S * X(I) + Y(I)
Vectorización
IV1: CARGA VECTOR
IV2: CARGA VECTOR
IV3: MULTIPLICA VECTOR x ESCALAR
IV4: SUMA VECTOR, VECTOR
IV5: ALMACENA VECTOR
Si disponemos de2 U.F. (*,+)
¿Ociosa siempre una?
arqAva Vectoriales (Encadenamiento hardware) SIMD-40
ENCADENAMIENTO HARDWARE
S * X(I) + Y(I)Una vez extraídos X e Y, hay que realizar 2 operaciones vectoriales
Vx
Vy
S
Vector intermedioVector intermedio
SumadorMultiplicador
Etapa de procesamiento
Y(I) = S * X(I) + Y(I) Conflicto en los 3 accesos a memoria
Cuantos más pipelines de acceso a memoria tengamos, mejor podremos encadenar los procesamientos vectoriales
123456
654321
221
21
22
21
22
23
21
22
23
24
222
23
24
25
462
arqAva Vectoriales (Encadenamiento hardware) SIMD-41
Y(I) = S * X(I) + Y(I)
Conflicto en los 3 accesos a memoria
Disponiendo de un solo pipeline para acceso a memoria (Cray I):
memoria Vy
Carga de memoria
Carga de Y Etapa 1
memoriaV4
Almacenamiento en memoria
Almacenamiento de Y Etapa 3
memoria
Carga de memoria
Carga de X
Vx
Vy
S
V3
V4
SumadorMultiplicador
Etapa de procesamiento
Etapa 2
arqAva Vectoriales (Encadenamiento hardware) SIMD-42
Y(I) = S * X(I) + Y(I) Conflicto en los 3 accesos a memoria
Disponiendo de tres pipelines para acceso a memoria (Cray X-MP):
Encadenamiento completo
memoria
Carga de memoria
Carga de Y
memoriaV4 Almacenamiento
en memoria
Almacenamiento de Y
memoria
Carga de memoria
Carga de X
Vx
Vy
S
V3
SumadorMultiplicador
Etapa de procesamiento
arqAva Vectoriales (Encadenamiento hardware) SIMD-43
Carga X
Carga Y
S * X
Almacena YV + Y
t
Carga Y
Carga X
S * X
Almacena YV + Y
t
Carga X
Carga YS * X
Almacena YV + Y
Eficiencia sin utilizar encadenamiento:
Eficiencia utilizando encadenamiento con un solo pipe de acceso a memoria:
Eficiencia utilizando encadenamiento con 3 pipes de acceso a memoria:
t
Limitaciones:
# Unidades Funcionales
# Registros Vectoriales
arqAva Vectoriales (Encadenamiento hardware) SIMD-44
Cray Y-MP 1988
8 registros de64 elementos
Fujitsu VP200 1988
Fichero registros 64K: 8 x 1024 16 x 512 32 x 256 64 x 128128 x 64256 x 32
Earth Simulator 2001
72 registros de256 elementos
+ 17 registros máscara
FIN64 bits 128 bits