Introducción a las

Arquitecturas Paralelas

Arquitectura de Computadoras II
Fac. Cs. Exactas
UNCPBA
Prof. Marcelo Tosini
2015
 Procesamiento Paralelo
Uso de muchas unidades de proceso independientes para
ejecutar distintas partes de una tarea en simultáneo

Principal objetivo: Aumento del RENDIMIENTO. Aumento de la capacidad

para resolver problemas computacionales grandes

¿Cómo?
• División del trabajo en tareas mas pequeñas e independientes
• Asignación de las tareas a distintas unidades de proceso
• Resolución de las tareas en simultaneo.

Problemas:
• Sincronización de las tareas.
• control de ejecución simultanea
• conflictos debidos a dependencias
2
Procesamiento Paralelo
Limitaciones:
En algunos problemas el incremento del número de procesadores no
mejora el rendimiento global, incluso empeora la eficiencia del sistema.

La eficiencia se mejora cuando:

• se logra un balance de carga entre procesadores: igual

numero de tareas de igual tamaño

• Se minimiza la interacción entre tareas:

eficiencia
se minimiza la comunicación o, al menos,
se mejoran los canales de comunicación

elementos de proceso

3
 Sistema paralelo
Conjunto de elementos de proceso que, operando juntos, permiten
resolver problemas computacionales complejos de forma eficiente

Características de un sistema paralelo:

• Cantidad y potencia de los elementos de proceso

• Tipo y Tamaño de la memoria

• Forma de comunicación entre los elementos de proceso

• Rendimiento

• Escalabilidad del sistema

• Recursos de potencia requeridos

4
Niveles de paralelismo
El paralelismo puede estudiarse a varios niveles:

• Trabajo: Dos programas distintos pueden ejecutarse en paralelo

• Tarea: En este nivel se consideran varias tareas independientes
entre si formando parte de un programa determinado. Es
posible la interacción de las tareas
• Proceso: Varios procesos componen una tarea. Son bloques con
funcionalidad bien definida.
• Variable: El paralelismo puede darse a nivel de variables ya que
varias instrucciones pueden ser ejecutadas en paralelo
siendo el punto de conflicto las variables en común
• Bit: Todos los computadores usan paralelismo a nivel de bit

5
 Arquitecturas de procesadores
Complejidad del procesador:

Arquitectura característica y estructura de cada procesador del

sistema.

Íntimamente ligado con la funcionalidad

(variedad de operaciones y cantidad de instrucciones)

Arreglos sistólicos homogéneos complejidad baja

MIMD Heterogéneos complejidad alta

6
 Arquitecturas de procesadores
Modo de operación:
Forma de controlar la secuencia de operaciones a realizar para
llevar adelante la ejecución de una tarea
Control flow
Las instrucciones se ejecutan en el orden dispuesto por
el algoritmo
Data flow
Las operaciones se realizan según la disponibilidad de
datos
Demand flow
Los resultados parciales se calculan por demanda, o sea
cuando se los necesita

7
 Arquitecturas de procesadores
Organización de la memoria:
Tipo de memoria utilizada en el sistema

Direccionable
Accedida por referencias a los datos
Asociativa
Accedida por contenido
Interconectada
Accedida por cualidades de los datos
(redes neuronales)

8
 Arquitecturas de procesadores
Red de interconexión:
Conexionado de hardware entre procesadores y entre
procesadores y memorias

La arquitectura de conexionado debe ajustarse lo mejor

posible a la topología de un algoritmo para mejorar la
performance

9
 Arquitecturas de procesadores
Número de procesadores y tamaño de la memoria:
Potencia de cálculo del sistema y capacidad de almacenamiento
de datos del mismo

Clasificación:
Sistemas grandes: más de 1000 procesadores

Sistemas medios: de 100 a 1000 procesadores

Sistemas chicos: hasta 100 procesadores

10
 Organización de las arquitecturas
Nivel de trabajo Distribuido Redes de computadoras

Nivel de tarea Multicomputadoras Pasaje de mensajes

Nivel de proceso
Nivel de instrucción paralelo Memoria compartida
Nivel de variable multiprocesadores
Nivel de bit
HARDWARE

GRANULARIDAD GRADO DE MODO DE

DEL ALGORITMO ACOPLAMIENTO COMUNICACION

11
Ámbitos de uso de la computación
paralela
• Simulación de modelos complejos

• Diseño y automatización de proyectos de ingeniería

• Exploración petrolera y minera

• Medicina

• Área militar

• Cine: efectos visuales, animación 3D

• Realidad Virtual

• Comercio electrónico

• Mega bases de datos (google, youtube, rapidshare)

12
Evolución del rendimiento

13
 Incremento de velocidad
3000 MHz XEON 3 GHz

2000 MHz
Bus CPU: 6 veces mas rápido

reloj CPU: 100 veces mas rápido

PIII 1,3 GHz

ATHLON GHz

PIII 1 GHz
1000 MHz
ATHLON 600

P II 400

500 MHz
486 DX100

100 MHz 486 DX33

89 90 91 92 93 94 95 96 97 98 99 00 01 02 03

14
Límites tecnológicos
El feature size (d) determina el tamaño de las compuertas en la
tecnología CMOS de manera que:

• Un aumento de la velocidad de reloj es proporcional a λ=1/d

• Un aumento del número de transistores es proporcional a λ2

Hasta cuanto puede disminuir d??

característica / año 1997 1999 2001 2003 2006 2009 2012

Feature Size (µmm) 0.25 0.18 0.15 0.13 0.10 0.07 0.05

Voltaje 1.8-2.5 1.5-1.8 1.2-1.5 1.2-1.5 0.9-1.2 0.6-0.9 0.5-0.6

Nº transistores 11M 21M 40M 76M 200M 520M 1.4B

DRAM bits/chip 167M 1.07G 1.7G 4.29G 17.2G 68.7G 275G

Tamaño Die (mm2) 300 340 385 430 520 620 750
Frecuencia local de reloj (MHz) 750 1250 1500 2100 3500 6000 10000
Frecuencia global de reloj (MHz) 750 1200 1400 1600 2000 2500 3000

15
Evolución de las arquitecturas
N 1
T= * *t C
P IPC

Multi tc IPC P
1 Tflop/s procesadore
s

1 Gflop/s Procesadores tc IPC>1 P

vectoriales

1 Mflop/s
Procesadores escalares tc IPC→1 P=1

1975 1990

16
Medidas de performance
Tiempo promedio de ejecución

• Instrucciones por segundo

Útil en SISD y en MIMD, pero no en SIMD
• Operaciones por segundo
No considera tamaño de palabra
• Punto flotante por segundo
No es útil en compiladores y en AI
• Inferencias por segundo
Útil en inteligencia artificial

17
Medidas de performance
Speedup (Sp - para P procesadores)

Promedio entre el tiempo de

proceso secuencial y paralelo en
T1 P procesadores
Sp =
Tp
T1 : tiempo en 1 procesador

Tp : tiempo en P procesadores
Sp < P

18
Medidas de performance
Eficiencia (Ep - para P procesadores)

Cociente entre Sp y P.
Medida de la relación costo/efectividad
Sp de la computación
Ep =
P
P : número de procesadores

Sp : Speedup con P procesadores

0 < Ep < 1

19
Medidas de performance
Redundancia (Rp - para P procesadores)

Promedio entre el número total de

operaciones ejecutadas con P proc.
Op y el número de operaciones
Rp = necesarias en 1 procesador
O1
Op : número de operaciones en
P procesadores

Rp > 1 O1 : Número de operaciones en

un procesador

20
Medidas de performance
Utilización (Up - para P procesadores)

Número de operaciones totales

ejecutadas con P procesadores
Op ponderada por la eficiencia de
Up =Rp * Ep= trabajo en esos P procesadores
P.TP
Op : número de operaciones en
P procesadores
Up < 1

21
Medidas de performance
Calidad del paralelismo (Qp - para P procesadores)

La calidad de paralelismo es
Sp * Ep proporcional al Spedup y a la
Eficiencia.
Qp =
RP La calidad de paralelismo decrece
al aumentar la Redundancia

Qp < 1

22
Límites de la computación paralela
La idea es modelar lo más aproximadamente la operación en un
entorno multiprocesador

Premisas:
Un programa paralelo es una serie de instancias de tareas
de sincronización seguidas de cálculos reales (programa)
distribuidos entre los procesadores.

Debido al overhead el tiempo total de ejecución de las

tareas distribuidas en los procesadores es mayor que si se
hubiese ejecutado en un único procesador

23
Límites de la computación paralela
Variables de cálculo:

• ts = tiempo de sincronización
• t = granularidad de tarea (tiempo de ejecución promedio de las tareas)
• to = overhead de tareas causado por la ejecución paralela
• N = cantidad de tareas entre puntos de sincronización
• P = número de procesadores

24
 Límites de la computación paralela
El tiempo de ejecución secuencial de N tareas de tiempo t será

T1 = N.t
En un ambiente paralelo cada tarea requiere (t + to) unidades de tiempo
Si hay N tareas en P procesadores, entonces el número de pasos
paralelos será N/P . Entonces el tiempo de ejecución paralelo será:

TN,P = ts + N/P . (t + to)

Si N en múltiplo de P no hay penalizaciones de balance de carga al final de
cada computación

25
Límites de la computación paralela
El Speedup del sistema será:

T1 N.t
SN,p = =
TN,p ts + N/P . (t + to)

1
=
ts/(N.t) + (1/N) N/P . (1 + to/t)

26
Límites de la computación paralela
La eficiencia del sistema será:

SN,p N.t
EN,p = = /P
P ts + N/P . (t + to)

1
= /P
ts/(N.t) + (1/N) N/P . (1 + to/t)

27
Límites de la computación paralela
Métrica P →∞ , N fijo N →∞ , P fijo

SN,p N/(1 + (ts + to)/t) P/(1 + to/t)

EN,p 0 1/(1 + to/t)

28
Límites de la computación paralela
Conclusiones:

• La primera columna muestra que el speedup resultante de

incrementar el número de procesadores está limitado por
el número de tareas N, mientras que la eficiencia tiende a
0.

• La segunda columna muestra que un Speedup igual a la

cantidad de procesadores puede ser logrado realizando un
gran número de tareas, siempre y cuando el overhead sea
ínfimo respecto a la granularidad de tareas

29
 Clasificación de las arquitecturas de
computadoras
Formas de paralelismo

Pipeline PLP TLP DLP ILP

(Process Level Paralelism) (Tread Level Paralelism) (Data Level Paralelism) (Instruction Level Paralelism)

Locked Multi core Coarse grain Short vector Superescalar

processors processing
Not Fine Grain (SIMD) VLIW
locked Multi processor
(MIPS
Multiprocessor systems (MIMD) SMT Vector EPIC
without Interlock
Pipeline Stages)
(Simultaneous processors
multithreading)
(SIMD)
Multi computer TTA
(MIMD)
Dataflow
30
PLP - Process level paralelism
Distintos procesos se ejecutan en diferentes procesadores paralelos o en
diferentes cores de un mismo procesador

Clasificados de acuerdo al modelo de Flynn

Modelo que permite clasificar a todas las computadoras basándose
en el estudio del paralelismo de los flujos de instrucciones y datos
exigidos por las instrucciones en los componentes más restringidos
de la máquina
• Flujo único de instrucciones, flujo único de datos.(SISD)
• Flujo único de instrucciones, flujo múltiple de datos.(SIMD)
• Flujo múltiple de instrucciones, flujo único de datos.(MISD)
• Flujo múltiple de instrucciones, flujo múltiple de datos.(MIMD)
31
SISD. Flujo único de instrucciones y datos

La CPU controla todas las operaciones que se realizan en la máquina

extrayendo secuencialmente las instrucciones de programa desde la memoria.

CPU: I/O
• Unidad de control: ejecuta una a
una las instrucciones de programa
• Unidad lógico/aritmética: realiza las ALU
operaciones sobre los datos UC
• Registros internos: se almacenan registros

datos parciales y direcciones.

Memoria

32
SIMD. Flujo único de instrucciones, flujo múltiple
de datos
Distintas operaciones
A[1] = 2 * a[0]; sobre
for (i = 1 ; i < MaxElem ; i ++) A[2] = 2 * a[1]; distintos datos
A[i] = 2 * a[i-1]; .
.
A[n-1] = 2 * a[n-2];
A[n] = 2 * a[n-1];

A[1] = 2 * b[1];
for (i = 1 ; i < MaxElem ; i ++) A[2] = 2 * b[2];
A[i] = 2 * b[i]; .
. Mismas operaciones
A[n-1] = 2 * b[n-1]; sobre
A[n] = 2 * b[n]; distintos datos

33
Arquitectura SIMD
Unidad Flujo de
funcional datos 1
1

Unidad Flujo de
Unidad funcional datos 2
de 2 Memoria
control

Unidad Flujo de
funcional datos k
k

Flujo de
instrucciones

34
 Arquitectura SIMD
for (i = 1 ; i < MaxElem ; i ++)
A[i] = 2 * a[i-1];

Unidad funcional 1 A[1]=2*A[0] A[2]=2*A[1] A[3]=2*A[2] A[4]=2*A[3] A[5]=2*A[4]

Unidad funcional 2 idle idle idle idle idle
. . . . . . . . . . . . . . .
Unidad funcional k idle idle idle idle idle

Ciclo 0 1 2 3 4

35
 Arquitectura SIMD
for (i = 1 ; i < MaxElem ; i ++)
A[i] = 2 * a[i];

Unidad funcional 1 A[1]=2*A[1] A[k+1]=2*A[k+1] A[2k+1]=2*A[2k+1] A[3k+1]=2*A[3k+1] A[n]=2*A[n]

Unidad funcional 2 A[2]=2*A[2] A[k+2]=2*A[k+2] A[2k+2]=2*A[2k+2] A[3k+2]=2*A[3k+2] idle

. . . . . . . . . . . . . . .
Unidad funcional k A[k]=2*A[k] A[2k]=2*A[2k] A[3k]=2*A[3k] A[4k]=2*A[4k] idle

Ciclo 0 1 2 3 4

36
MISD. Flujo múltiple de instrucciones, flujo único
de datos
Conceptualmente, varias instrucciones ejecutándose
paralelamente sobre un único dato.

Arquitecturas desacopladas y los arreglos sistólicos

Funcionan con el principio de ‘bombear’ los datos a través de una
hilera de procesadores escalares donde en cada uno de ellos se
realizan paralelamente operaciones sobre distintos datos.
Desde el punto de vista de cada dato, éste pasa de un procesador
al siguiente para transformarse de acuerdo a la operación que
realice cada procesador.

37
Arquitecturas clásicas MISD
• La información circula entre las celdas como en un pipeline
• La comunicación con el exterior se produce en las celdas frontera

Memoria

Salida Entrada
de datos
PE PE PE PE PE PE PE de datos

38
Arquitecturas clásicas MISD
Ejemplo
M[i] = ((((M[i] * 256 + 70) mod 512 - 5) and 0x7f) or 0x80) shl 2

Memoria

Salida or and mod Entrada

Shl 2 -5 +70 *256
de datos 0x80 0x7f 512 de datos

39
MIMD. Flujo múltiple de instrucciones, flujo
múltiple de datos

• Es la mejor estrategia de diseño orientada a obtener el más alto

rendimiento y la mejor relación costo/rendimiento.

• Idea general: conectar varios procesadores para obtener un

rendimiento global lo más cercano a la suma de rendimientos
de cada procesador por separado.

• La filosofía de trabajo plantea la división de un problema en

varias tareas independientes y asignar a cada procesador la
resolución de cada una de estas tareas.

40
MIMD. Flujo múltiple de instrucciones, flujo
múltiple de datos
int suma (int x, int y)
{ Procesador
return x + y; 1
}

int prom (int x, int y) Procesador

2 memoria
{
return (x + y) >> 2;
}
........................ Procesador
3

........................
a = Func (suma(Oper1, Oper2) , prom(10, Oper1));

41
 TLP – Thread level paralelism
En TLP las unidades de ejecución de un procesador se comparten entre los threads
Independientes de un proceso (o threads de diferentes procesos)

COARSE GRAIN: En coarse grain multi-threading los threads son desalojados

del procesador con baja frecuencia, usualmente cuando el thread realiza alguna
I/O, o ante un fallo de cache.

FINE GRAIN: En fine grain multi-threading el thread en ejecución es cambiado

(thread swaping) en cada ciclo de reloj

SMT: Simultaneous multi-threading es similar a fine grain, pero permite ejecutar

múltiples threads en cada ciclo de reloj.
SMT permite concurrencia física, a diferencia de los anteriores que solo manejan
Concurrencia virtual (multiplexado por división de tiempo)

42
TLP – Thread level paralelism
A A A A A A A A A A A A
A A A B B B
A B B C
A C C C C
A A D D C C C D

B B B A A A A D B D
B B
B A A C
B B C C C
C C C C D D D D C C C

C C C A
D D D B
C B B
D B A
D D C
D D D D D D D A D D D
D D D A A
D D

SMT
Coarse grain Fine grain

43
DLP – Data level paralelism
• La operación se aplica a varios ítems de dato en lugar de uno

• Implementado con rutas de datos divisibles

• Por ejemplo: una ruta de 64 bits permite realizar 1 operación de 64 bits;

2 de 32 bits; 4 de 16 bits; etc.

Tipos:
• Short vector processing: uso de operadores de M bits para realizar N
operaciones de M/N bits.

• Vector processors: la ruta de datos se multiplexa en tiempo entre los

elementos del vector de operandos. No ahorra tiempo de proceso, solo
permite disminuir el tamaño del código por el uso de instrucciones
vectoriales.
44
ILP – instruction level paralelism
Ejecución paralela e instrucciones completas u operaciones

Aproximaciones: Superescalar
VLIW (Very Long Instruction Word)
EPIC (Explicit parallel Instruction Computer)
TTA (Transport Triggered Architecture)
DataFlow

Si bien todas se basan en la paralelización de instrucciones para su ejecución

difieren en la forma de emisión de las mismas

45
 ILP - Superescalar
Los procesadores superescalares leen varias instrucciones a la vez en su cola de
instrucciones y dinámicamente emiten cierto número de ellas en cada ciclo de reloj.
El número y tipo de instrucciones emitidas depende de cada arquitectura.

Ventaja:
fetching
• Ejecución masiva en paralelo
buffer de
instrucciones Desventajas:
• Perdida de orden secuencial
• Problemas de dependencias
emisión
• Problemas con los saltos

unidad unidad unidad

funcional funcional funcional

46
ILP - Dataflow
Controlada por el flujo de los datos en lugar del orden de las instrucciones

• Las operaciones se almacenan en un buffer a la espera de los datos para operar

• Los resultados viajan en paquetes (tags) que contienen el valor y la lista de
operaciones destino (que usan ese valor como operando)
• Cuando una operación tiene todos sus operandos, se dispara y ejecuta.

unidad funcional
memoria de
unidad funcional
operaciones
unidad funcional

tags

47
 ILP - VLIW
Ejecuta grupos de operaciones empaquetadas en instrucciones compuestas
• Las instrucciones dentro de cada
paquete son independientes entre si.
fetching
instrucción VLIW
• Todas las instrucciones de un (de 3 operaciones)
paquete se ejecutan en paralelo y las
despacho
más rápidas deben esperar la
finalización de las más lentas.
unidad unidad unidad
• La selección de instrucciones de funcional funcional funcional
cada paquete la realiza el compilador.
Desventajas:
• Mayor ancho del bus de datos desde memoria de instrucciones.
• Banco de registros con varios puertos de lectura/escritura.
• Desperdicio de espacio de memoria por instrucciones VLIW
incompletas debido a dependencias.
48
 ILP - EPIC
Mejora de VLIW para evitar el desperdicio de espacio debido a dependencias
• Los paquetes siempre están
completos (no hay NOOP´s)
fetching
instrucción VLIW
• Las operaciones dentro de un paquete (de 3 operaciones)
tienen información adicional de
emisión
dependencia entre ellas

• Hay una unidad de emisión que unidad unidad unidad

decide que instrucciones se emiten y a funcional funcional funcional
que unidades
Desventajas:
• Mayor ancho del bus de datos desde memoria de instrucciones.
• Banco de registros con varios puertos de lectura/escritura.
• La planificación se realiza en el compilador (como en VLIW)
49
 ILP - TTA
La idea básica de TTA es permitir a los programas el control total de los caminos
internos de movimiento de datos dentro del procesador.

La arquitectura se compone básicamente de unidades funcionales, buses y registros.

Las entradas de las unidades funcionales tienen puertos disparables (triggering ports)
que permiten activar una operación determinada cuando todos los puertos tienen
datos válidos para la instrucción a realizar.

Una palabra de instrucción TTA esta compuesta de múltiples slots, uno por bus.

TTA es similar a VLIW pero con mayor control sobre el hardware.

50
 ILP - TTA
ejemplo:

En RISC

add r3, r1, r2

En TTA

r1 -> ALU.operand1
r2 -> ALU.add.trigger
ALU.result -> r3

51