Ingeniería de los

Computadores
Unidad 1. Introducción al paralelismo
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Evolución de la informática Necesidades computacionales

 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

60 70 80 90 00

Mainframes Servidores
Grandes
computadores para
aplicaciones de
Minicomputadores
negocios y científicas
de gran volumen. Aplicaciones científicas
en laboratorios y WWW
pequeñas
organizaciones.
Redes

PCs y
Microprocesadores Estaciones de
Trabajo

Computadores
Rápido crecimiento (tecnología y herramientas de diseño): Embebidos
electrónica digital de altas prestaciones, videojuegos,
teléfonos móviles, tarjetas inteligentes, conmutadores,…
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Mejora de prestaciones
➢ Avances en tecnologías (límites físicos: calor, ruido, etc.)

Aumento de la velocidad de
los dispositivos O(a)
Reducción de tamaño Aumento de la capacidad de
de dispositivos (a) procesamiento O(a3)
Aumento del número de
dispositivos O(a2)

Aumento de tamaño de Aumento del número de Aumento de la capacidad de

los CI (b) dispositivos O(b2) procesamiento O(b2)

Cambio de la tecnología Aumento de la velocidad de Aumento de la capacidad de

(Ej. CMOS a GaAs los dispositivos procesamiento ??
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Mejora de prestaciones
➢ Avances en arquitecturas
➢ Paralelismo:
➢ Segmentación de cauces.
➢ Repetición de elementos: Utilizar varias unidades funcionales,
procesadores, módulos de memoria, etc. para distribuir el trabajo.
➢ Localidad: Acercar datos e instrucciones al lugar donde se necesitan para
que el acceso a los mismos sea lo más rápido posible (jerarquía de
memoria).
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Desarrollo de las arquitecturas de computadores - Objetivo

MAYOR CAPACIDAD COMPUTACIONAL

Iniciativas mayor peso software

➢ Repertorio de instrucciones (RISC, CISC, …)

➢ Arquitecturas VLIW
➢ Extensiones SIMD (MMX, SSE, 3DNOW, …)
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Desarrollo de las arquitecturas de computadores - Objetivo

MAYOR CAPACIDAD COMPUTACIONAL

Iniciativas mayor peso hardware

➢ Arquitecturas segmentadas
➢ Arquitecturas vectoriales
➢ Arquitecturas superescalares
➢ Arquitecturas paralelas o de alto rendimiento
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Arquitectura de Computadores

“Conjunto de instrucciones, recursos y características del procesador

que son visibles al software que se ejecuta en el mismo. Por tanto, la
arquitectura determina el software que el procesador puede ejecutar
directamente, y esencialmente define las especificaciones a las que
debe ajustarse la microarquitectura” [Ortega, 2005]

• En Ingeniería de Computadores veremos:

➢ Arquitecturas superescalares
➢ Arquitecturas paralelas: multicomputadores y multiprocesadores
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Ámbito de la arquitectura de computadores

➢ El lenguaje máquina del computador, la microarquitectura del
procesador y la interfaz para los programas en lenguaje máquina
(lenguaje máquina y arquitectura concreta del procesador).
➢ Los elementos del computador y como interactúan (es decir la
arquitectura concreta del computador, la estructura y
organización).
➢ La interfaz que se ofrece a los programas de alto nivel y los
módulos que permiten controlar el funcionamiento del
computador (sistema operativo y la arquitectura abstracta del
computador).
➢ Los procedimientos cuantitativos para evaluar los sistemas
(benchmarking).
➢ Las alternativas posibles y las tendencias en su evolución
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Niveles estructurales de Bell y Newell

➢ Descripción del computador mediante una aproximación por
capas.
➢ Cada capa utiliza los servicios que proporciona la del nivel inferior.
➢ Propone 5 niveles:
➢ De componente
➢ Electrónico
➢ Digital
➢ Transferencia entre registros (RT)
➢ Procesador-Memoria-Interconexión (PMS)
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Niveles de interpretación de Levy

• Contemplan al computador desde un punto de vista funcional.
• Constituido por una serie de máquinas virtuales superpuestas.
• Cada máquina interpreta las instrucciones de su nivel,
proporcionando servicios a la máquina de nivel superior y
aprovechando los de la máquina de nivel inferior.
• Se distinguen 5 niveles:
➢ Aplicaciones
➢ Lenguajes de alto nivel
➢ Sistema Operativo
➢ Instrucciones máquina
➢ Microinstrucciones
➢ Estos niveles son similares a los niveles funcionales de
Tanenbaum
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Niveles de abstracción de un computador

SW Niv. Soft. Superiores
Llamadas al Sistema, Comandos,…

ARQUITECTURA
Sistema Operativo
Sistemas de cómputo, Ensamblador,…

Sist. Computador IC
Integra la orientación estructural
de los niveles de Bell y Newell y Procesadores, Interfaces E/S, Datapath

el punto de vista funcional de los Nivel RT

niveles de Levy y Tanenbaum. ALUs, registros, memorias, MUX,…

TECNOLOGÍA Digital

Puertas lógicas, inversores, biestables

Electrónica
Uniones P N, Metal, Polisilicio

Componente
HW
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Taxonomía de Flynn
➢ SISD
FI

UC FI UP FD UM
E/S

FI
➢ SIMD UP1 UM1
FI FD

UC UP2 UM2
FI FD
. .
. .
UPn UMm
FI FD
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Taxonomía de Flynn
➢ MISD
FI1
FI2
FD

UC1 FI1 UP1 UM1

FD
UC2 UM2
FI2 UP2

. . FD .
. . .

UCn UPn UMm

FIn

FD

FIn
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Taxonomía de Flynn
➢ MIMD
FI2

FI1

UC1 UP1 UM1

FI1 FD

UC2 UP2 UM2

FI2 FD
. .
. .
UCn UPn UMm
FIn FD

FIn
 Unidad 1. Introducción al paralelismo
1.1 Introducción y motivación
¿Qué?

• Taxonomía de Flynn-Johnson
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
Tipos de paralelismo

• Tipos de paralelismo
➢ Paralelismo de datos: La misma función, instrucción, etc. se
ejecuta en paralelo pero en cada una de esas ejecuciones se
aplica sobre un conjunto de datos distinto.
➢ Paralelismo funcional: Varias funciones, tareas, instrucciones,
etc. (iguales o distintas) se ejecutan en paralelo.
➢ Nivel de instrucción (ILP) – se ejecutan en paralelo las instrucciones de un
programa. Granularidad fina.
➢ Nivel de bucle o hebra (Thread) – se ejecutan en paralelo distintas
iteraciones de un bucle o secuencias de instrucciones de un programa.
Granularidad fina/media.
➢ Nivel de procedimiento (Proceso) –distintos procedimientos que
constituyen un programa se ejecutan simultáneamente. Grano medio.
➢ Nivel de programa – la plataforma ejecuta en paralelo programas
diferentes que pueden corresponder, o no, a una misma aplicación.
Granularidad gruesa.
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
ILP

• Segmentación: ILP
Procesador no segmentado
Inst. 1 IF ID EX MEM WB 1/(5T)
Inst. 2 5T IF ID EX MEM WB

Inst. 1 IF ID EX MEM WB Procesador segmentado

Inst. 2 IF ID EX MEM WB 1/(T)

Inst. 3 IF ID EX MEM WB

Inst. 4 IF ID EX MEM WB

Inst. 1 IF ID EX MEM WB Procesador supersegmentado

1/(T/2)=2/T
Inst. 2 IF ID EX MEM WB

Inst. 3 IF ID EX MEM WB

Inst. 4 IF ID EX MEM WB
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
ILP

• Segmentación
➢ Identificación de fases en el procesamiento de una tarea.
➢ Rediseño para implementar cada fase de forma independiente al resto.
➢ Paralelismo por etapas (el sistema procesa varias tareas al mismo tiempo
aunque sea en etapas distintas).
➢ Se aumenta el número de tareas que se completan por unidad de tiempo.

...
S1 S2 Sk

Clk t t1 ti
r
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
ILP

• Segmentación
Ganancia. Suponemos que TLI (tiempo de latencia de inicio) = T, tiempo que tarda
en ejecutarse una operación en una unidad sin segmentar.
TLI = k·t, siendo k el nº de etapas del cauce, y t la duración de cada etapa

T1 k·n·t
Gk = = =
Tk k· t + (n − 1)·t
k·n
=
k + n-1

lim Gk = k
n→
Normalmente, ¿TLI>T ó TLI<T?
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
ILP

• Ganancia real

Gk

Gmax
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
ILP

• Tipos de riesgos (detección del cauce)

➢ Riesgos de datos. Se producen por dependencias entre
operandos y resultados de instrucciones distintas.
➢ Riesgos de control. Se originan a partir de instrucciones de salto
condicional que, según su resultado, determinan la secuencia de
instrucciones que hay que procesar tras ellas.
➢ Riesgos estructurales o colisiones. Se producen cuando
instrucciones diferentes necesitan el mismo recurso al mismo
tiempo
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
ILP

• Riesgos de datos
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
ILP

• Soluciones a los riesgos de datos

➢ Reorganización de código (intercambio de instrucciones e inserción de NOP)
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
ILP

• Soluciones a los riesgos de datos

➢ Forwardings
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
ILP

• Soluciones a los riesgos de control

➢ Abortar operaciones
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
ILP

• Soluciones a los riesgos de control

➢ Bloqueos o uso de NOP
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
ILP

• Soluciones a los riesgos de control

➢ Delayed branch
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
Rendimiento

• Tiempo de ejecución de un programa

➢ Tiempo de CPU (usuario y sistema)
➢ Tiempo de E/S (comunicaciones, acceso a memoria, visualización,
etc.)
Ciclos_del_Programa
Tiempo de CPU (TCPU)= Ciclos_del_Programa x TCICLO =
Frecuencia_de_Reloj

Ciclos_del_Programa
Ciclos por Instrucción (CPI) =
Número_de_Instrucciones (NI)

TCICLO=1/F
TCPU = NI x CPI x TCICLO F=frecuencia
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
Rendimiento

• Tiempo para arquitecturas capaces de emitir a ejecución varias

instrucciones por unidad de tiempo

TCPU = NI x (CPE / IPE) x TCICLO

CPI

CPE = ciclos entre inicio de emisión de instrucciones.

IPE = instrucciones que pueden emitirse (empezar la ejecución) cada vez que se
produce ésta.
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
Rendimiento

Ejemplo: CPI = CPE/IPE

No segmentado
CPE=5 IPE=1 CPI=5
Inst. 1 IF ID EX MEM WB
Inst. 2 5T IF ID EX MEM WB

T Segmentado
Inst. 1 IF ID EX MEM WB
CPE=1 IPE=1 CPI=1
Inst. 2 IF ID EX MEM WB

Inst. 3 IF ID EX MEM WB

Inst. 4 IF ID EX MEM WB

Inst. 1 T
IF ID EX MEM WB Superescalar o VLIW
CPE=1 IPE=2 CPI=0.5
Inst. 2 IF ID EX MEM WB
Inst. 3 IF ID EX MEM WB
IF ID EX MEM WB
Inst. 4
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
Rendimiento

• Procesadores que codifican varias operaciones en una instrucción

(VLIW)

TCPU = (Noper / Op_instr) x CPI x TCICLO

NI

Noper = número de operaciones que realiza el programa.

Op_instr = número de operaciones que puede codificar una instrucción.
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
Rendimiento

Ejemplo:
NI = Noper/Op_instr
Ejemplo paralelismo datos
Procesador Matricial Noper=12 Op_instr=4 NI=3

UC EP1 EP2 EP3 EP4

C=A+B C[1]=A[1]+B[1] C[2]=A[2]+B[2] C[3]=A[3]+B[3] C[4]=A[4]+B[4]

F=D–E F[1]=D[1]-E[1] F[2]=D[2]-E[2] F[3]=D[3]-E[3] F[4]=D[4]-E[4]

G= K*H G[1]=K[1]*H[1] G[2]=K[2]*H[2] G[3]=K[3]*H[3] G[4]=K[4]*H[4]

Flujos de Instrucciones Flujos de Datos

Ejemplo paralelismo instrucciones
 Unidad 1. Introducción al paralelismo
1.2 Paralelismo
Rendimiento

• Medidas de rendimiento:
➢ Ganancia T1
GP = ; GP  P
TP

➢ Eficiencia
Gp
EP = ; EP  1
P

➢ Productividad
 Unidad 1. Introducción al paralelismo
1.3 Arquitecturas vectoriales
Vectoriales

• Arquitecturas vectoriales: ILP y paralelismo de datos

El procesamiento de
Unidad Escalar
instrucciones está Reg. Escalares

segmentado y se utilizan Datos Escalares

múltiples unidades Control
Cauces Esc.
funcionales. E/S
Flujo Instr.
IF ID OF Cauces Vector.

Paralelismo de datos: Unidad

cada instrucción vectorial LOAD/STORE

Datos Vectoriales
codifica una operación Reg. Vectoriales
sobre todos los Procesador Unidad Vectorial
Vectorial
componentes del vector.
Memoria
Principal
b4
b3 Registro Vectorial
b2
b1 a8 a7 a6 a5 a4 a3
b8 b7 b6 b5 b4 b3 a2+b2
a4 a1+b1 Unidades funcionales
a3 Cauce Vectorial
a2 segmentadas
a1
Registros
Vectoriales
 Unidad 1. Introducción al paralelismo
1.3 Arquitecturas vectoriales
Vectoriales

• Arquitectura orientada al procesamiento de vectores (suma de

vectores, productos escalares, etc.)
• Repertorio de instrucciones especializado
• Características
➢ Cálculo de los componentes del vector de forma independiente
(buenos rendimientos)
➢ Cada operación vectorial codifica gran cantidad de cálculos (se
reduce el número de instrucciones y se evitan riesgos de control)
➢ Se optimiza el uso de memoria (entrelazado de memoria y
organizaciones S y C)
 Unidad 1. Introducción al paralelismo
1.3 Arquitecturas vectoriales
Vectoriales

Ejemplo: Sumar dos vectores de 100 elementos.

Pseudo-código escalar
for i:= 1 to 100 do c(i)=b(i)+a(i)
Ensamblador escalar (con bucle de 100 iteraciones)
LOADI R5, BASEa
LOADI R6, BASEb
LOADI R7, BASEc
LOADI R1, 0
INI ADDRI R5, R5, 1
ADDRI R6, R6, 1
ADDRI R7, R7, 1
ADDMR R8, R5, R6
STORE R7, R8
INC R1
COMP R1, 100
JUMP [Link] INI
Pseudo-código vectorial
c([Link]) = a([Link]) + b([Link])
Ensamblador vectorial
ADDV c, a, b, 1, 100
 Unidad 1. Introducción al paralelismo
1.3 Arquitecturas vectoriales
Vectoriales
 Unidad 1. Introducción al paralelismo
1.3 Arquitecturas vectoriales
Vectoriales

• Entrelazado de memoria
 Unidad 1. Introducción al paralelismo
1.3 Arquitecturas vectoriales
Vectoriales

• Acceso a memoria simultáneo o tipo S

 Unidad 1. Introducción al paralelismo
1.3 Arquitecturas vectoriales
Vectoriales

• Acceso a memoria concurrente o tipo C

 Unidad 1. Introducción al paralelismo
1.3 Arquitecturas vectoriales
Vectoriales

• Operaciones gather-scatter
 Unidad 1. Introducción al paralelismo
1.3 Arquitecturas vectoriales
Vectoriales

• Enmascaramiento (gestión de matrices dispersas)

 Unidad 1. Introducción al paralelismo
1.3 Arquitecturas vectoriales
Vectoriales

• Rendimiento: encadenamiento de cauce

 Unidad 1. Introducción al paralelismo
1.3 Arquitecturas vectoriales
Vectoriales

• Rendimiento: encadenamiento de cauce

 Unidad 1. Introducción al paralelismo
1.3 Arquitecturas vectoriales
Vectoriales
Proc. Supersegmentado
con coproc. Vectoriales

Proc. Vectorial

Proc. Matricial