

 Enumerar
los diferentes tipos de Arquitecturas SIMD,
naturaleza de la solución y nivel de paralelismo de
cada una de ellas.
 Describir el principio de diseño y funcionamiento de
los Procesadores Matriciales.
 Explicar el funcionamiento del Procesador en Arreglo
(Array Processor), el Procesador Sistólico, Procesador
en Frente de Onda y Procesador Asociativo.
 Valorar la importancia del legado de las arquitecturas
SIMD en la computación actual.
 Limitaciones
de desempeño en el
campo de la computación científica.
 Necesidad
de procesar gran volumen de
información.
 Necesidad
de procesar vectores y
Matrices, no solo escalares.
Algoritmos secuenciales para cálculo vectorial.
 Ejemplo: Multiplicación de Matrices: C[] = A[] x B[]
- Algoritmo costoso: O(n).

FOR I = 1 TO N
FOR J=1 TO M
C[I,J] = 0.0
FOR K=1 TO L
t
C[I,J] = C[I,J]+A[I,K]*B[K,J]
END FOR
END FOR
END FOR
N

Procesadores Vectoriales
o Arquitecturas Memoria a Memoria
o Arquitecturas Registro a Registro

Procesadores Matriciales
o Array Processor
o Systolic Processors
o Associative Processors
o Wavefront Processors

Emular el tipo de datos y sus operaciones: Procesador
como un arreglo de unidades de ejecución o Elementos
o Unidades de Procesamiento (EP).

Cada EP es una unidad de ejecución con ALU simple o
completa y almacenamiento: registros y a veces
memoria local.

Toda la red de EP gobernada por una Unidad de Control
o Procesador central.

Procesador en Arreglo o Array Processor.
Otras arquitecturas derivaron posteriormente.

 Procesador
en arreglo (Array Processor).
 Procesador
sistólico (Systolic Processor).
 Procesador
de frente de onda (Wavefront
 Procesador
Asociativo (Associative
Processor).
Processor)






Red o matriz de EP con una
Unidad de Control Central.
Todos los EP comunicados con
Memoria
EP comunicados entre sí.
Red Síncrona.
Ciclo de carga de datos +
ejecución de instrucción.
UC difunde (broadcast) la
instrucción a todos los EP.



Memoria común
accedida por los EP o
red de módulos de
memoria de EP
coordinada por control.
Los EPs pueden
Habilitarse o
deshabilitarse
(enmascararse) desde
la UC.
Enmascaramiento:
limitar estructura y
configurar operaciones.
Bus de Control
UC
Modo
EP
EP
PMEM
PMEM

Bus Común
Routing
EP
PMEM
Enrutamiento entre diferentes
EP para comunicar resultados
parciales en esquemas de
ejecución.
56
57
58
59
60
61
62
63
7
0
1
2
3
4
5
6
7
0
15
8
9
10
11
12
13
14
15
8
23
16
23
16
17
18
19
20
21
22
31
24
25
26
27
28
29
30
31
24
39
32
33
34
35
36
37
38
39
32
47
40
41
42
43
44
45
46
47
40
55
48
49
50
51
52
53
54
55
48
63
56
57
58
59
60
61
62
63
56
0
1
2
3
4
5
6
7
i-8
i-1
12
i+1
19
20
21
28
i+8



Concepto introducido por Kung y colegas (Carnegie-Mellon)
Sistólico porque la memoria funciona como el corazón,
inyectando datos al arreglo en cada pulso de reloj
Consigue mejoras de procesamiento sin necesidad de
incrementar el ancho de banda de la memoria
MEMORIA
P
Procesador convencional
MEMORIA
EP
EP
EP
Matriz Sistólica
EP



Cauce en formación matricial con múltiples flujos de datos.
Conjunto de celdas simples (Unas sola operación con
entradas y Registro).
Control e interconexión simples (No Broadcasting)
X0
X
0
Y
Z=W*X+Y
W2
0
W1
0
W0
W
2
Fig 1: Celda EP del procesador
sistolico
1
Fig 2: Estructura de Interconexion del
Procesador sistolico
0


Datos fluyen de forma encauzada, estructurada y son
accesibles sólo en las fronteras.
Interconexión en matriz o árbol.
EP
EP
EP
EP
EP
EP
EP
EP
EP
EP
EP
EP
EP
EP
Matriz Cuadrada
EP
EP
EP
EP
EP
EP
EP
EP
EP
EP
Matriz Hexagonal
Arbol sistólico
EP

Empleado para Aritmética Matricial de alto nivel:
o Multiplicación
o Inversión de Matrices
o Descomposición L - U


Fácil de expandir mediante VLSI debido a la simplicidad de
diseño de la celda o EP.
Desventaja: Limitado por la velocidad de memoria y/o
Entrada Salida.
o Requiere aún gran ancho de banda pues la red es todavía
síncrona.
o Memorias especializadas.

Redes sincrónicas vs. redes asíncronas
o Los Array Processor emplean broadcasting síncrono.
o Los Systolic processor no usan broadcasting pero su red es
síncrona.
o Requieren Memorias de alta velocidad.
o Altos costos de construcción.

¿ Es una red asíncrona factible?
o Proceder hasta que el dato esté disponible.
o Esperar a que memoria entregue datos.
o Celdas o EP calculan por “eventos”  Disaparan



Procesador basado en red de EP asíncrona.
Celdas simples y comunicación simple (similar al sistólico).
Cuando hay datos válidos en las entradas, la celda de
dispara (computa) y expande entradas o resultado a las
salidas.
Yi
Yi
Xi
s
Xo
Xi
Si +1 = Si + Xi * Yi
Reset S
R/W S
Selección
Yo
Yo
Xo




Los datos entran por las celdas
de la frontera y generan
disparos.
Los disparos activan las celdas
contiguas.
Nuevos datos generan nuevos
disparos: tren de disparos
similar a un frente de ondas:
sonido, perturbación en agua,
etc.
De esta analogía su nombre.
B21
B22
B11
B12
A12
A11
0
0
A22
A21
0
0



Procesadores paralelos basados en estructuras de datos
asociativas (Memorias asociativas)
Aplican la instrucción sobre todos los datos cuya clave
satisface los parámetros o argumentos de búsqueda.
Problema de la construción de memoria asociativas
grandes:
o Comparación en paralelo de todos los bits de todas las palabras de
la memoria (bit-paralelo, palabra-paralela)
o Comparación en serie de los i-ésimos bits (bitslice) de todas las
palabras (bit-serie, palabra-paralela)

Taxonomía de Feng desarrollada sobre este paradigma para
definir el nivel de paralelismo: bit-{serie|paralelo},palabra{serie|paralela}

En la actualidad estas arquitecturas han dado pie a nuevos
paradigmas computacionales con soporte de hardware
para bases de datos y aplicaciones que demandan
procesamiento paralelo de conjuntos de datos.

Ejemplos:
o PEPE (Burrogs Corp., 1972)
o STARAN (Goodyear, 1972). Construído para la Marina USA,
orientado al procesamiento de objetos de radar.
o Posteriormente: procesadores asociativos masivamente paralelos
para apoyo en campos y aplicaciones específicos tales como
RDBMS (RAP, Neocore LCC) e Inteligencia Artificial (AM3, IXM2).


Necesaria una estructura que interconecte todos los EPs.
Decisiones de diseño:
o Modo de operación: Sincrónica – Asíncrona
o Estrategia de Control: Centralizado o Distribuido.
o Metodología de Comunicación: Conmutación de Circuitos o
Conmutación de Paquetes.
o Topología de Red: Estáticas – Dinámicas

Son más complejos pero con mejor rendimiento.
Reproducen el comportamiento natural de la operación.
Ganancia significativa sobre homólogo secuencial.

Ejemplos:


o Multiplicación de matrices.
• Secuencial es O(n3)
o Con VP
• O(n2) Carga de vectores, barrer filas por columnas.
o Con Array Processor basado en hipercubos:
• O(n log2 n)

Procesamiento de multimedia presenta mismos
requerimientos de procesamiento en flujo continuo.

Principios y técnicas aplicadas son apropiadas para el
procesamiento de streams de multimedia.

Extensiones multimedia en procesadores actuales las
emplean:
o Intel’s MMX
o AMD’s 3DNow!
o Intel’s SSE
Descargar

Unidad 3. Procesmiento SIMD