PDF de programación - Introduccion a las arquitecturas Paralelas

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:

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

a
i
c
n
e
i
c
i
f
e

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
Nivel de proceso
Nivel de instrucción
Nivel de variable
Nivel de bit

GRANULARIDAD
DEL ALGORITMO

Multicomputadoras

Pasaje de mensajes

paralelo

multiprocesadores

HARDWARE

Memoria compartida

GRADO DE

ACOPLAMIENTO

MODO DE

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

2000 MHz

1000 MHz

500 MHz

Bus CPU: 6 veces mas rápido

reloj CPU: 100 veces mas rápido

XEON 3 GHz

PIII 1,3 GHz

ATHLON GHz

PIII 1 GHz

ATHLON 600

P II 400

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

Nº transistores

DRAM bits/chip

Tamaño Die (mm2)

Frecuencia local de reloj (MHz)

Frecuencia global de reloj (MHz)

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

11M

21M

167M

1.07G

300

750

750

340

1250

1200

40M

1.7G

385

1500

1400

76M

200M

520M

1.4B

4.29G

17.2G

68.7G

275G

430

2100

1600

520

3500

2000

620

6000

2500

750

10000

3000

15

Evolución de las arquitecturas

=

T

N
P

*

1
IPC

*

Ct

1 Tflop/s

1 Gflop/s

1 Mflop/s

Multi
procesadore
s

Procesadores
vectoriales

Procesadores escalares

1975

1990

tc

tc

tc

IPC P

IPC>1 P

IPC→1 P=1

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)

Sp =

T1
Tp

Sp < P

Promedio entre el tiempo de
proceso secuencial y paralelo en
P procesadores

T1 : tiempo en 1 procesador

Tp : tiempo en P procesadores

18

Medidas de performance

Eficiencia (Ep - para P procesadores)

Ep =

Sp
P

0 < Ep < 1

Cociente entre Sp y P.
Medida de la relación costo/efectividad
de la computación

P : número de procesadores

Sp : Speedup con P procesadores

19

Medidas de performance

Redundancia (Rp - para P procesadores)

Rp =

Op
O1

Rp > 1

Promedio entre el número total de
operaciones ejecutadas con P proc.
y el número de operaciones
necesarias en 1 procesador

Op : número de operaciones en

P procesadores

O1 : Número de operaciones en

un procesador

20

Medidas de performance

Utilización (Up - para P procesadores)

Op
P.TP

Número de operaciones totales
ejecutadas con P procesadores
ponderada por la eficiencia de
trabajo en esos P procesadores

Op : número de operaciones en

P procesadores

Up =

Rp * Ep=

Up < 1

21

Medidas de performance

Calidad del paralelismo (Qp - para P procesadores)

Qp =

Sp * Ep

RP

Qp < 1

La calidad de paralelismo es
proporcional al Spedup y a la
Eficiencia.

La calidad de paralelismo decrece
al aumentar la Redundancia

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á:

SN,p =

T1
TN,p

=

N . t

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á:

EN,p =

SN,p
P

=

N . t

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

/ P

=

1

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

/ P

27

Límites de la computación paralela

Métrica

P fi

, N fijo

N fi

, 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

Not
locked

(MIPS
Multiproce