PDF de programación - INTRODUCCIÓN AL PROCESAMIENTO PARALELO

INTRODUCCIÓN AL

PROCESAMIENTO PARALELO

GRUPO DE ARQUITECTURA

DE COMPUTADORES

ARQUITECTURA E INGENIERÍA DE

COMPUTADORES

TEMA1

ÍNDICE

!! Procesamiento paralelo
!! Condiciones de paralelismo

"! Concepto de dependencia
"! Condiciones de Bernstein
"! Paralelismo hardware y software

!! Niveles de paralelismo
!!
!! Clasificaciones de arquitecturas paralelas

Importancia del procesamiento paralelo

"! Taxonomía de Flynn
"! Organización del sistema memoria: clasificación tradicional

de sistemas MIMD.
!! Medidas de rendimiento

AEC: TEMA1

2

Procesamiento paralelo
!! Más potencia de cálculo y más fiabilidad

"! Aumentar la velocidad de trabajo de los

procesadores y otros elementos
!! Depende de la tecnología, organización de los

componentes del computador, y de la
arquitectura del procesador.

!! Puede tener alto coste de diseño y de

fabricación.

"! Conectar varios procesadores y coordinar su

funcionamiento
!! Computadores paralelos
!! Distribución de computaciones entre sistemas

remotos: sistemas distribuidos

AEC: TEMA1

3

¿Cómo ser más rápidos?
!! Tres métodos (Pfister, 1998)

"! Trabajar más duro
"! Trabajar de forma más inteligente
"! Conseguir ayuda

!! Equivalente en computación

"! Usar hardware más rápido (incrementar la

frecuencia de reloj del procesador…)

"! Optimizar los algoritmos
"! Usar múltiples recursos (varios procesadores,

varias unidades de procesamiento de
instrucciones, …)para resolver una tarea en
particular --> paralelismo

AEC: TEMA1

4

ÍNDICE (I)

Procesamiento paralelo

!!
!! Condiciones de paralelismo
"! Concepto de dependencia
"! Condiciones de Bernstein
"!

Paralelismo hardware y software

!! Niveles de paralelismo
!!
!! Clasificaciones de arquitecturas paralelas

Importancia del procesamiento paralelo

Taxonomía de Flynn

"!
"! Organización del sistema memoria: clasificación tradicional de

sistemas MIMD.

!! Medidas de rendimiento

AEC: TEMA1

5

Condiciones de paralelismo
!! Concepto de dependencia:

"! La posibilidad de ejecutar diversos segmentos

de programa en paralelo requiere la
independencia de éstos.

"! Tipos de dependencias:

!! Dependencias de datos
!! Dependencias de control
!! Dependencias de recursos

Nota: por simplicidad, ejemplos de relaciones de dependencia entre

instrucciones

AEC: TEMA1

6

Dependencias de datos

!! Dependencia de flujo (o verdadera):

"! La instrucción S2 posee una dependencia de flujo

respecto de S1, si una variable generada por S1 es
utilizada como operando de S2.

"! Dependencia “inherente” al código.

!! Antidependencia:

"! S2 es antidependiente de S1, si S2 modifica una

variable utilizada como operando por S1.

!! Dependencia de salida:

"! S1 y S2 poseen una dependencia de salida entre

ambas si las dos generan la misma variable.

AEC: TEMA1

7

Dependencias de control
!! Aparecen en situaciones en las que el orden

de ejecución de las instrucciones no puede
ser determinado antes del tiempo de
ejecución.

!! Ejemplo característico: diferentes caminos

tomados después de una instrucción de
salto condicional pueden introducir o
eliminar dependencias de datos entre
instrucciones.

AEC: TEMA1

8

Dependencias de recursos
!! Conflictos de utilización de recursos

hardware compartidos por parte de los
eventos paralelos.

!! Los recursos compartidos pueden ser:

unidades funcionales, registros del
procesador, direcciones de memoria,…

AEC: TEMA1

9

Condiciones de Bernstein (I)

!! Condiciones para la detección de paralelismo entre

dos “segmentos” de código:
"! Son las condiciones que deben cumplir dos procesos

para poder ser ejecutados en paralelo

"! Entendemos por proceso una entidad software

correspondiente a la abstracción de un fragmento de
programa

"! Estas condiciones sólo son suficientes para la

detección de dependencias de datos, no para las
dependencias de control y dependencias de recursos

AEC: TEMA1

10

Condiciones de Bernstein (II)

!! Conjunto de entrada Ii de un proceso Pi: conjunto de todas
las variables de entrada necesitadas para ejecutar un proceso
Pi

!! Conjunto de salida Oi de un proceso Pi: conjunto de todas las

variables de salida generadas después de la ejecución de Pi.

!! Dados dos procesos P1 y P2 con conjuntos de entrada I1 e I2,
y conjuntos de salida O1 y O2 respectivamente, ambos pueden
ejecutarse en paralelo (P1//P2), si verifican todas las
condiciones siguientes:
"!

I1 intersec O2 = conjunto_vacío (WAR-antidependencia)
I2 intersec O1 = conjunto_vacío (RAW-dep_flujo)

"!
"! O1 intersec O2 = conjunto_vacío (WAW-dep_salida)
!! En general, un conjunto de procesos P1, P2,…,Pk pueden

ejecutarse en paralelo P1//P2//…//Pk si y sólo si:
"! Pi//Pj para todo i ! j

AEC: TEMA1

11

Paralelismo hardware y software
!! Paralelismo hardware: posibilidades que ofrece

el hardware de un sistema computador para
ejecutar “segmentos” de código en paralelo.
"! Paralelismo temporal (segmentación)
"! Paralelismo espacial (replicación)

!! Paralelismo funcional.

!! Paralelismo software: posibilidades que ofrece

un código para que algunas de sus partes se
ejecuten en paralelo.
"! Determinado por las dependencias de datos y de

control del código.

AEC: TEMA1

12

ÍNDICE (I)

Procesamiento paralelo

!!
!! Condiciones de paralelismo

"! Concepto de dependencia
"! Condiciones de Bernstein
"!

Paralelismo hardware y software

!! Niveles de paralelismo
!!
!! Clasificaciones de arquitecturas paralelas

Importancia del procesamiento paralelo

Taxonomía de Flynn

"!
"! Organización del sistema memoria: clasificación tradicional de

sistemas MIMD.

!! Medidas de rendimiento

AEC: TEMA1

13

Niveles de paralelismo (I)
!! Granularidad: magnitud de la tarea

(número de operaciones) candidata a ser
ejecutada en paralelo.

"! Granularidad hardware: tamaño del tipico del

hardware replicado en el sistema paralelo.

"! Granularidad sofware: tamaño tipico del

software que es ejecutado en paralelo.

"! Denominaciones típicas: grano fino, grano

medio, grano grueso.

AEC: TEMA1

14

Niveles de paralelismo (II)

!! Niveles de paralelismo software en una aplicación (I)

"! Nivel de programas: grano grueso

!! Normalmente poca dependencia entre ellos

"! Nivel de funciones: grano medio

!! Es paralelismo de tareas

"! Nivel de bucles: grano medio-fino

!! Se pueden ejecutar en paralelo las iteraciones
!! Es paralelismo de datos

"! Nivel de operaciones: grano fino

!! Operaciones independientes se pueden ejecutar

en paralelo

AEC: TEMA1

15

Niveles de paralelismo (III)

!! Paralelismo software a nivel de ejecución(II)

"! Nivel de instrucciones
"! Nivel de proceso

!! Cada proceso en ejecución tiene su propia asignación de

memoria.

"! Nivel de hebra (thread)

!! Un proceso puede componerse de varias hebras
!! Cada hebra tiene su propia pila, contenido de registros

(entre ellos el IP) pero comparte código, variables locales y
otros recursos (archivos abiertos, cache,…) con las hebras
del mismo proceso.

!! La creación, destrucción, comunicación, sincronización y

conmutación de hebras son más rápidas que la de procesos
(procesos ligeros)

NOTA: actualmente, en algunos textos y documentación de fabricantes de computadores se habla de

procesos y threads indistintamente sin exigir a los threads la compartición de recursos.

AEC: TEMA1

16

Niveles de paralelismo (III)

!! Paralelismo implementado a nivel

hardware en sistemas computador
"! Multiprocesadores/Multicomputadores: grano

grueso, grano medio.

"! Procesadores Multihebra (Multithreading): grano

medio.

"! Paralelismo a nivel de instrucción: grano fino.

!! Segmentación
!! Replicación de unidades funcionales
!! Replicación de unidades de procesamiento de

instrucciones.

AEC: TEMA1

17

Paralelismo y arquitecturas (I)

!! Relación entre paralelismo a nivel software y arquitecturas/procesadores

(nivel hardware) paralelos
"! Paralelismo entre programas: a nivel de procesos

!! Multiprocesador/Multicomputador

"! Paralelismo entre funciones: a nivel de procesos o de hebras (threads)

!! Multiprocesador/Multicomputador, procesadores multihebra, procesadores

multinúcleo (multicores)

"! Paralelismo de bucles: a nivel de procesos o de hebras

!! Multiprocesador/Multicomputador, procesadores multihebra, procesadores

multinúcleo (multicores)

!! Instrucciones vectoriales: extensiones multimedia, procesadores vectoriales,

GPUs

"! Paralelismo de operaciones/instrucciones:

!! Segmentación
!! Procesadores superescaleres y VLIW
!! Paralelimo funcional: diferentes unidades funcionales especializadas o

replicadas.

!! Instrucciones vectoriales: extensiones multimedia, procesadores vectoriales,

GPUs

AEC: TEMA1

18

Paralelismo y arquitecturas (II)
!! Utilización, implementación y detección del paralelismo

ILP: Instruction Level Parallelism, paralelismo a nivel de instrucción

AEC: TEMA1

19

ÍNDICE (I)

Procesamiento paralelo

!!
!! Condiciones de paralelismo

"! Concepto de dependencia
"! Condiciones de Bernstein
"!

Paralelismo hardware y software

!! Niveles de paralelismo
!!
!! Clasificaciones de arquitecturas paralelas

Importancia del procesamiento paralelo

Taxonomía de Flynn

"!
"! Organización del sistema memoria: clasificación tradicional de

sistemas MIMD.

!! Medidas de rendimiento

AEC: TEMA1

20

Motivación del procesamiento
paralelo

!! Motivación al estudio de los sistemas

con uno o varios niveles de paralelismo:
"! Aplicaciones que requieren estas

arquitecturas

"! Accesibilidad al hardware y al software
"! Necesidad de estudiar diferentes facetas
de diseño de sistemas computador que
incluyan algún tipo de paralelismo

AEC: TEMA1

21

Motivación: aplicaciones

!! Aplicaciones que requieren computadores

paralelos
"!