Download Paralelismo en computación secuencial

Computador secuencial
Paralelismo en computación
secuencial
Mario Medina C.
[email protected]
• Elementos
• Memoria
• Procesador
• Buses de interconexión
• Todos estos pueden ser cuellos de botella
del desempeño
• Solución? Paralelismo!
• A nivel de operaciones básicas
• A nivel de instrucciones
Ejemplo: multiplicación de enteros
• Multiplicar 2 números
enteros de n bits
• Realizar n sumas con
desplazamiento sucesivas
• Operación requiere
Ejemplo: multiplicación de enteros
• Diagrama muestra circuito para 4 bits
• n sumadores completos (FA)
• n compuertas AND
• 2 registros para almacenar
resultados
Ejemplo: multiplicación de enteros
• En cada ciclo, se multiplica 1 bit de a por
b, y se acumula el resultado
Ejemplo: multiplicación de enteros
• Multiplicador paralelo de 4 bits
• El LSB del resultado se almacena en un
registro de desplazamiento
• n-1 bits superiores se almacenan en registros
acumulador y se vuelven a sumar
• Multiplicación de n bits requiere n ciclos
de reloj
• Solución: Más hardware!
© 2014 Mario Medina C.
1
Ejemplo: multiplicación de enteros
• Multiplicador paralelo requiere más
hardware
• n2 compuertas AND y n(n – 1) FA
• Tserial = nTsuma = n2TFA
• Tparalelo = 2(n – 1)TFA
• Retardo del sumador limita velocidad del
reloj
• Sumador por propagación de acarreo
• Sumador por anticipación de acarreo
Tendencias en procesadores
•
Paralelismo implícito y explícito
• Paralelismo implícito
• Avances en hardware se traduce en
ejecución de instrucciones en paralelo
• Paralelismo invisible al programador y/o
usuario
• Paralelismo explícito
• Expuesto al programador
• Requiere de directivas para manejar
concurrencia
• Bibliotecas, lenguajes, etc.
Velocidad de reloj de CPU
Mayor velocidad de reloj de CPU
•
•
•
Enfoque principal de los últimos años
Desempeño limitado por la memoria
Mayor nivel de integración
•
•
Mayor número y densisdad de transistores
Qué hacer con ellos?
•
•
•
Mayor número de unidades funcionales
Múltiples instrucciones en ejecución
Paralelismo
Tendencias en CPUs Intel
Consumo de potencia de CPU
• Disipación dinámica de potencia de una
CPU es función de las capacitancias
parásitas C, la frecuencia de reloj f y el
voltaje de la fuente V
• Pd = CfV2
• Reducir tamaño del transistor reduce C
• Reducir voltaje de 5.0[V] a 2.2[V] a 1.2[V]
a 0.9[V]
• Aumenta susceptibilidad al ruido
© 2014 Mario Medina C.
2
Alternativas para aumentar
desempeño
•
Pipelining
•
•
Paralelismo a nivel de instrucción
Ejecución superescalar
•
•
•
Paralelismo a nivel de hebra
VLIW
•
• Técnica usada para aumentar el
throughput de instrucciones ejecutadas
por unidad de tiempo
• Dividir procesamiento de instrucción en serie
de pasos independientes
• Requiere almacenamiento intermedio
• Procesamiento de instrucciones avanza a la
velocidad de la etapa más lenta
Paralelismo a nivel de instrucción
Multithreading
•
Segmentación (Pipelining)
Paralelismo a nivel de instrucción
Sistema sin pipeline
Sistema con pipeline
• Dividir operación en 3 etapas A, B y C
Hardware sin pipeline
300 ps
20 ps
R
e Latencia = 320 ps
g Throughput = 3.12 GOPS
Lógica
combinacional
• Tres operaciones diferentes comparten el
hardware
• Agregar registros de pipeline entre etapas
• Almacenar resultados intermedios
• Operación demora ahora 3 ciclos de reloj
Reloj
Diagrama de tiempo
OP1
OP2
OP3
• Latencia operación: 360 ps
• Cada 120 ps termina una operación
• Aumento del throughput: 3 ops en 360 ps
Tiempo
Sistema con pipeline
Pipelining no uniforme
• Figura muestra pipeline ideal
Sistema con pipeline de 3 etapas
20 ps
100 ps
20 ps
100 ps
20 ps
Lógica
comb.
A
R
e
g
Lógica
comb.
B
R
e
g
Lógica
comb.
C
R
e
g
• Qué pasa si son de largos distintos?
Reloj
• Etapas que no pueden subdividirse:
Diagrama de tiempo
OP1
OP2
OP3
• 3 etapas independientes, del mismo largo
100 ps
A
B
A
C
B
A
Tiempo
© 2014 Mario Medina C.
C
B
C
Latencia = 360 ps
Throughput = 8.33 GOPS
• Desempeño limitado por etapa más larga
• Otras etapas tienen tiempo ocioso
• Acceso a memoria
• Accesos a tablas de consulta (Lookup
Tables)
3
Pipeline no uniforme
Profundidad del pipeline
• Profundidad del pipeline determina
aumento de desempeño
Hardware: Pipeline de 3 etapas, retardos no uniformes
50 ps
20 ps
150 ps
20 ps
100 ps
20 ps
Lógica
Comb.
A
R
e
g
Lógica
Comb.
B
R
e
g
Lógica
Comb.
C
R
e
g
• Dividir hardware en pipeline de 6 etapas
Diagrama de tiempos
OP1
OP2
OP3
A
• A más niveles, mayor latencia
• Retardos de registros limitan aumento
B
Clock
Latencia = 510 ps
Throughput = 5.88 GOPS
C
A
B
C
A
B
C
Tiempo
• Latencia es 420 ps
• Throughput es 14.29 GOPS
• Retardo de registros representa un 29%
Pipeline de 6 etapas
Ventajas de pipelining
Latencia = 420 ps
Throughput = 14.29 GOPS
50 ps 20 ps 50 ps 20 ps 50 ps 20 ps 50 ps 20 ps 50 ps 20 ps 50 ps 20 ps
Logica
Comb.
R
e
g
Logica
Comb.
R
e
g
Logica
Comb.
R
e
g
Logica
Comb.
R
e
g
Logica
Comb.
R
e
g
Logica
Comb.
Reloj
•Throughput y latencia aumentan
•Pentium 4 tiene pipeline de 20 etapas!
R
e
g
• Aumenta el throughput: más instrucciones
terminadas por unidad de tiempo
• Aprovecha mejor el hardware
• Todos los componentes de la CPU están
ocupados en un instante dado
• CPU con pipeline puede (en teoría)
ejecutar una instrucción cada ciclo
• Desempeño del pipeline se mide en CPI:
Ciclos por Instrucción
• Desempeño ideal: 1 ciclo por instrucción
Desventajas de pipelining
• Aumenta la latencia de una instrucción
• Programa supone que una instrucción se
inicia después de terminada la anterior
• No es verdad en CPU con pipeline
• Desempeño se ve perjudicado por
pipelines largos y saltos condicionales
• Cada 6 instrucciones hay un salto (típico)
• CPU con pipeline es más cara y compleja
de diseñar e implementar
Ejemplo de pipeline
• Pipeline RISC clásico de 5 etapas
•
•
•
•
•
Instruction Fetch (IF)
Instruction Decode (ID)
Execute (EXE)
Memory (MEM)
Write Back (WB)
1 2 3 4 5
Instr. 1
Instr. 2
Instr. 3
© 2014 Mario Medina C.
IF
ID
IF
6
7
EXE MEM WB
ID
IF
EXE MEM WB
ID
EXE MEM WB
4
Ejemplo de pipeline
• Instruction Fetch (IF): Se lee la instrucción
a ejecutar y se calcula la dirección de la
próxima instrucción
• Instruction Decode (ID): Decodifica la
instrucción y lee datos desde los registros
• Execute (EX): Se realiza la operación
• Memory (MEM): Se accede a memoria
• Writeback (WB): Se escriben los
resultados a los registros
Ejemplo de pipeline: STORE
• Instrucción STORE R2, M[1500]
• IF: Lee la instrucción STORE
• ID: Decodifica la instrucción STORE y lee
registro R2
• EX: No hay operación aritmética
• MEM: Escribe R2 en la posición de memoria
M[1500]
• WB: No hay escritura a registros
Peligros en pipelines
• Peligros estructurales
• Dos instrucciones consecutivas quieren usar
el mismo hardware
• A veces, se resuelven dividiendo el hardware
• En el ejemplo, la memoria es leída dos veces
por ciclo
• En el ciclo IF se lee la instrucción
• En el ciclo MEM se leen los datos
• Soluciones
• Memoria que soporta 2 accesos por ciclo
• Memoria de instrucciones y memoria de datos
© 2014 Mario Medina C.
Ejemplo de pipeline: LOAD
• Instrucción LOAD M[1000], R1
•
•
•
•
•
IF: Lee la instrucción LOAD
ID: Decodifica la instrucción LOAD
EX: No hay operación aritmética
MEM: Lee la posición de memoria M[1000]
WB: Escribe el dato leído en el registro R1
Ejemplo de pipeline: ADD
• Instrucción ADD R2, R3
• IF: Lee la instrucción ADD
• ID: Decodifica la instrucción ADD y lee
registros R2 y R3
• EX: Suma registros R2 y R3
• MEM: No hay acceso a memoria
• WB: Escribe resultado de la suma en el
registro R3
Peligros en pipelines
• Peligros de datos
• Producidos por dependencias entre los datos
de instrucciones consecutivas
• Tres tipos:
• Read-After-Write (RAW)
• Write-After-Read (WAR)
• Write-After-Write (WAW)
• Se resuelven con forwarding y stalling
• Peligros de control
• Producidos por saltos
5
Peligro de datos
• Dependencia de datos entre instrucciones
• Código a ejecutar
SUB R3, R4
AND R4, R6
• Este tipo de peligro se llama Read-AfterWrite (RAW)
Peligro de datos
• Resultado de resta se almacena en el
ciclo WB de instrucción SUB
• Valor de R4 se lee en el ciclo ID de AND
• Instrucción lee el valor equivocado de R4!
• El hardware debe asegurarse que R4 se lee
por instrucción AND sólo después de ser
escrito por instrucción SUB
Forwarding
• Forwarding redirige los resultados
intermedios de una instrucción a las
instrucciones siguientes que los necesitan
• En rigor, instrucción AND requiere valor de
R4 al comienzo de ciclo EXE
Forwarding
• Redirección de resultados permite que
instrucciones se ejecuten sin demoras
• CPI: un instrucción por ciclo
• Redirigir resultado R4 de instrucción SUB a la
ALU en ciclo EXE de instrucción AND
siguiente
Stalling
• No siempre es posible hacer forwarding
de resultados
• En ese caso, sólo se puede detener el
pipeline por uno o más ciclos
• Hay un ciclo ocioso en el pipeline
• Se introduce una burbuja en el pipeline
• El stalling aumenta el CPI de la CPU
• Impacto negativo en el desempeño
© 2014 Mario Medina C.
Stalling
• Ejemplo: usar un dato inmediatamente
después de su lectura
• LOAD Dato, R4
• AND R4, R6
• Dato se lee desde la memoria y está
disponible al final del ciclo MEM de LOAD
• Instrucción AND necesita el valor de R4 al
comienzo de ciclo EXE
6
Stalling
Stalling
• Instrucción AND no puede proceder!
• No puede hacerse forwarding
• Sólo es posible demorar el pipeline
Otros peligros de datos
• Write-After-Read (WAR)
• Solución: detener el pipeline por un ciclo
mientras dato llega desde la memoria
• Burbuja: ciclo ocioso en el pipeline
Otros peligros de datos
• Write-After-Write (WAW)
• Una instrucción trata de escribir un resultado
antes que sea leído por otra
ADD R1, R3, R4
SUB R1, R2, R3
• Una instrucción trata de escribir un resultado
antes que sea escrito por otra
ADD R4, R7, R2
SUB R1, R3, R2
• Instrucción SUB no puede ejecutarse si
instrucción ADD no ha leído R3
• Problema si hay ejecución concurrente o
cambio de orden de instrucciones
• Instrucción SUB no puede ejecutarse si
instrucción ADD no ha escrito R2
• Problema si hay ejecución concurrente o
cambio de orden de instrucciones
• No es el caso en nuestro pipeline simple
• No es el caso en nuestro pipeline simple
Peligros de control
• Se producen por la ejecución de saltos
condicionales
• En nuestro pipeline, los saltos se deciden al
final del ciclo EXE
• Pero la instrucción 2 es leída durante la etapa
Decode de la instrucción 1, y aún no se sabe
si el salto se realiza!
1
Instr. 1
Instr. 2
Instr. 3
IF
2
3
4
5
6
ID EXE MEM WB
IF
© 2014 Mario Medina C.
• Ejemplo de peligro de control
SUB R4, R6
JZERO OTROLUGAR
ADD R7, R6
• Resultado de SUB disponible al final de su ciclo EXE
• Decisión de dónde saltar se toma al final del ciclo 4
• Cuál instrucción debe ser leída en el ciclo 3?
1
7
ID EXE MEM WB
IF
Peligros de control
ID EXE MEM WB
SUB
JZERO
???
IF
2
3
4
5
6
7
ID EXE MEM WB
IF
ID EXE MEM WB
IF
ID EXE MEM WB
7
Peligros de control
Desempeño de un pipeline
• Para evitar el peligro de control, la lectura
de la siguiente instrucción se demora
hasta que se decide el salto al final del
ciclo 4
SUB
JZERO
???
1
2
IF
ID
IF
3
4
5
6
7
8
Ts
mN

Tpipe N  m  1
9
EXE MEM WB
ID
• El desempeño (Throughput) es
N
1

Tpipe 1  m  1
N
EXE MEM WB
IF
IF
IF
EXE MEM WB
ID
Desempeño pipeline
Procesamiento superescalar
• Otra alternativa para mejorar el
desempeño de procesador secuencial
Desempeño del pipeline en función de profundidad M
M=5
M=10
M=30
M=100
1
• Paralelismo a nivel de instrucción
• Ejecución simultánea de dos o más
instrucciones del mismo código en un mismo
ciclo (hoy en día 3 a 6)
• Requiere duplicación de unidades
funcionales en la CPU (hoy en día 2 a 6)
• Independiente de la segmentación de la CPU
0.9
0.8
0.7
Razón N/T(pipe)
• En pipelines de profundidad m, ejecutar
N operaciones independientes requiere
de N + m – 1 ciclos
• La aceleración obtenida es
0.6
0.5
0.4
0.3
0.2
0.1
0
1
10
100
1000
N
Ejecución superescalar
• Se quiere sumar 4 enteros a partir de
M[1000]
LOAD M[0x1000], R1
LOAD M[0x1008], R2
ADD M[0x1004], R1
ADD M[0x100C], R2
ADD R1, R2
STORE R1, M[0x2000]
© 2014 Mario Medina C.
//
//
//
//
//
//
Lee d0 a R1
Lee d2 a R2
Suma d1 y d0
Suma d2 y d3
Suma todos
Escribe suma
Ejecución superescalar
• Supongamos un procesador super-escalar
de 2 vías
• Una CPU con
• 2 pipelines de acceso a memoria
• 2 unidades de instrucción y control
• Puede ejecutar 2 instrucciones a la vez
• siempre y cuando éstas no tengan
dependencias entre ellas
• y que ellas no utilicen recursos que están
ocupados
8
Ejecución superescalar
• Ciclo Fetch transfiere múltiples
instrucciones desde RAM a buffers de
instrucción de CPU
• Despachador de instrucciones de la CPU
revisa el flujo de instrucciones y determina
si pueden ejecutarse en paralelo
• Dependencias de datos entre registros
• Disponibilidad de unidades funcionales
Ejecución superescalar
LOAD
Hardware de
despacho de
instrucciones
LOAD
ADD
ADD
ADD
STORE
Colas de
instr.
Buffer de
instrucciones
Unidad
superescalar
Ejecución superescalar
1
2
LOAD
IF
ID
EX MEM WB
LOAD
IF
ID
EX MEM WB
ADD
IF
ID
EX MEM WB
ADD
IF
ID
EX MEM WB
IF
ID
EX MEM WB
IF
ID
ADD
3
STORE
4
5
6
7
8
EX MEM WB
Dependencia de datos
• En el programa anterior, existen
dependencias de datos en el uso de
registro R1
• Esto impide la ejecución paralela de
instrucciones
• Soluciones
• Reescribir código para usar otros registros
• Hardware renombra registros
automáticamente para evitar conflicto
• Intel Pentium fue el primer procesador x86
superescalar
© 2014 Mario Medina C.
Unidad
superescalar
Dependencia de datos
• Se quiere sumar 4 enteros a partir de
M[1000]
• Código siguiente es equivalente al anterior, y
hasta más corto
LOAD M[0x1000], R1 // Lee d0 a R1
ADD M[0x1004], R1
// Suma d1 a R1
ADD M[0x1008], R1
// Suma d2 a R1
ADD M[0x100C], R1
// Suma d3 a R2
STORE R1, M[0x2000] // Escribe suma
Otras dependencias
• Dependencias de recursos
• Instrucciones que acceden a un solo recurso
común no pueden ejecutarse en paralelo
• Puede resolverse con reordenamiento de
instrucciones
• Dependencias de saltos
• Destino del salto se conoce sólo al ejecutar
la instrucción
• Predicción de saltos
• Ejecución especulativa y rollbacks
9
Reordenamiento de instrucciones
• Sumar 4 números a partir de M[1000]
LOAD M[0x1000], R1
ADD M[0x1004]. R1
LOAD M[0x1008], R2
ADD M[0x100C], R2
ADD R1, R2
STORE M[0x2000], R1
//
//
//
//
//
//
Lee d0 en R1
Suma d0 y d1
Lee d2 en R2
Lee d3 en R2
Suma datos
Escribe suma
Despacho dinámico de
instrucciones
• Procesador puede despachar
instrucciones fuera de orden para
aumentar paralelismo
• Explota al máximo paralelismo del código
• Si instrucciones usan diferente número de
etapas del pipeline, pueden también finalizar
fuera de orden
• Estado del procesador consistente con
ejecución secuencial
• Aparece en procesador Intel Pentium Pro
Uso de recursos en CPU
superescalar
• Supongamos CPU superescalar con 2
ALUs
• En el 1er. ejemplo, éstas se usan sólo en
3 ciclos de 8 posibles
• Difícil llenar todos los ciclos
• Procesador subutilizado
• Superescalar ≤ 4 vías
4
5
6
7
© 2014 Mario Medina C.
Reordenamiento de instrucciones
• Caso similar al primer ejemplo, pero
• Hay dependencia de datos entre
instrucciones 1 y 2
• Limita paralelismo
• Procesador inteligente podría examinar
instrucciones y reordenarlas en tiempo de
ejecución, o bien
• Compilador inteligente podría reordenar
instrucciones en tiempo de compilación
Despacho dinámico de
instrucciones
• Consistencia con ejecución secuencial
• Ejemplo: ejecución de
DIV R1, R2, R3
ADD R4, R5, R6
• Ambas instrucciones son independientes
• Orden de ellas podría ser intercambiado
• Qué pasa si la primera genera una
división por cero?
• Estado final de la CPU será distinto
Limitaciones de procesador
superescalar
• Paralelismo es extraído por hardware
• Detección de paralelismo está limitada por
espacio ocupado en el chip
• Puede ser entre el 5 y 10% del chip!
• Limitado por cuántas instrucciones futuras
son revisadas por el hardware
• Complejidad aumenta cuadráticamente con
número de instrucciones
• Es necesario revisar n2 posibles conflictos
entre n instrucciones
10
Simultaneous Multi-Threading
(SMT)
• CPU ejecuta simultáneamente
instrucciones de diferentes hebras
• Extensión de procesador superescalar
• Evita conflictos por dependencia de datos
• Requiere lectura paralela de instrucciones de
2 ó mas hebras
• Requiere más bancos de registros
• Requiere más unidades de control de acceso
a memoria
Simultaneous Multi-Threading
(SMT)
• CPU mantiene múltiples copias de
• Registros de control, datos y estado
• Punteros a la pila y de instrucción
• CPU puede ejecutar múltiples hebras de
código, que comparten recursos
• Pipelines
• Colas y caches
• SMT aprovecha mejor el hardware
• HW de control es más complejo
Simultaneous Multi-Threading
(SMT)
Simultaneous Multi-Threading
(SMT)
• Diagrama muestra operación de CPU con
múltiples pipelines
• Diagrama muestra operación de CPU con
múltiples pipelines y SMT de dos vías
• Burbujas debido a dependencias, latencias
de memoria, lazos muy cortos, errores en la
predicción de saltos, etc
• Flujos de instrucciones comparten caches y
pipelines, teniendo sus propios registros y
unidades de control
Intel Hyper-Threading
Problemas con SMT
• Intel implementa SMT de dos vías (HyperThreading) a partir del Pentium 4
• No mejora el desempeño de un hebra
• Aumenta consumo de potencia por CPU
• Puede demorar ejecución de códigos si un
recurso compartido es cuello de botella
• Puede degradar desempeño de cache
• Han habido instancias en que una hebra
lee datos criptográficos de la otra hebra,
desde la cache compartida
• Aumenta el costo de sincronización
• Intel dice que obtiene en promedio 30% de
aumento de desempeño a un costo de 5%
más de área en el chip
• CPU con HT es vista como 2 CPUs por el
sistema operativo y hace balance de carga
• Para Multi-Core con Hyper-Threading,
sistema operativo debe ser “HT-Aware”
© 2014 Mario Medina C.
11
Very Long Instruction Word (VLIW)
• Alternativa para explotar el paralelismo al
nivel de instrucción
• Programador debe indicar explícitamente
las instrucciones que se pueden ejecutar
en paralelo
• Hardware es más simple que superescalar,
pero el compilador es mucho más complejo
Very Long Instruction Word (VLIW)
• Múltiples unidades funcionales
• Instrucciones deben tener al menos una
operación para cada unidad funcional
• Instrucciones se despachan juntas en VLIW y
se ejecutan en paralelo
• Análisis de compilación identifica y agrupa
instrucciones independientes
• Resuelve dependencias al compilar
Very Long Instruction Word (VLIW)
Ejecución superescalar
Compilador para VLIW
LOAD
LOAD
ADD
• Transformaciones de código mucho más
complejas
ADD
ADD
STORE
VLIW
Buffer de
instrucciones
• Hardware de despacho es más simple
• Compilador puede revisar más código
para aumentar concurrencia
Instrucción
Instrucción
Instrucción
Unidad
Funcional HW
Unidad
Funcional HW
Unidad
Funcional HW
• Instrucciones para ejecución especulativa
de código
• VLIW actual: procesadores embebidos y
procesadores digitales de señales
• 4 a 8 instrucciones concurrentes
Críticas a VLIW
• Compilador no tiene información sobre
estado dinámico del programa
• En memoria jerárquica, tiempo de acceso
a memoria no es constante
• Tiempo de acceso a memoria no uniforme
interfiere con planificación hecha por el
compilador
• Código puede crecer mucho
• Muchas unidades funcionales
desocupadas
© 2014 Mario Medina C.
12