Circuitos Digitales II y LaboratorioFundamentos de Arquitectura de Computadores
Unidad 9: Pipelines Complejos
Prof. Felipe [email protected]
Circuitos Digitales II 2012 - 1
1
Departamento de Ingeniería Electrónica
Facultad de Ingeniería
2
Renombrar registros
• La etapa de decodificación renombra y añade las instrucciones a la etapa de Issue al buffer de reordenamiento (reorder buffer, ROB)
El renombramiento hace que los hazards WAR or WAW sean posibles
• Cualquier instrucción en el ROB para la cual se hayan solucionado los RAW hazards puede ser despachada
Se le llama ejecución fuera de orden o ejecución por flujo de datos (dataflow execution)
IF ID WB
ALU Mem
Fadd
Fmul
Issue
3
Estructuras para renombradoTabla de renombrado y banco de registros
Reorder Buffer (ROB)
Load Unit
FU FU Store Unit
< t, result >
Ins# use exec op p1 src1 p2 src2 t1
t2
.
.tn
La Plantilla de las instrucciones (es decir, tag t) se asigna en la etapa de decodificación, la cual además asocia el tag con el registro en regfile, cuando una instrucción termina su tag es desasignado
Cambiar el tag por su valor es una operación costosa
tags
4
Manejo del buffer de reordenamiento
Una entrada de instrucción es candidata a ejecutar cuando:
Tiene una instrucción válida (bit de “use” es 1)No ha comenzado ejecución (bit de “exec” es 0)Ambos operandos están disponibles (p1 y p2 son 1)
t1
t2
.
.
.
tn
puntero2
Próximo a desasignar
puntero1
Próximo disponible
Ins# use exec op p1 src1 p2 src2
Los registros destino son renombrados a la posición de la instrucción
El ROB es manejado circularmenteEl bit de “exec” se pone a 1 cuando la instrucción comienza ejecución. Cuando una instrucción termina se pone a 0 (libre)
5
Renombrado y despacho fuera de orden un ejemplo
¿Cuando se rempazan los tag de las fuentes por datos?
¿Cuando se puede reusar un nombre?
1 LD $2, 34($5)2 LD $4, 45($7)3 MULT $6, $4, F24 SUB $8, $2, F25 DIV $4, $2, F86 ADD $10, $6, F4
Renaming table Reorder bufferIns# use exec op p1 src1 p2 src2
t1
t2
t3
t4
t5
.
.
data / ti
p data$1$2$3$4$5$6$7$8
Cuando una unidad funcional produce datos
Cuando una instrucción termina
t1
1 1 0 LD
t2
2 1 0 LD
5 1 0 DIV 1 v1 0 t4 4 1 0 SUB 1 v1 1 v1
t4
3 1 0 MUL 0 t2 1 v1
t3
t5
v1
1 1 1 LD 0
4 1 1 SUB 1 v1 1 v1 4 0
v4
5 1 0 DIV 1 v1 1 v4
2 1 1 LD 2 0
3 1 0 MUL 1 v2 1 v1
6
EfectividadEl renombrado y la ejecución fuera de orden fueron implementados por primera vez en 1969 en el 360/91 de IBM (R. M. Tomasulo) pero no se volvió a usar hasta los modelos de la mitad de los 90¿Por qué?Razones
1. Efectivo solo en una clase pequeña de programas2. La latencia de memoria era un problema más grande3. Las excepciones no eran precisas!
Un problema más para resolver
Transferencia de control
7
Interrupciones precisas
Debe parecer que, en el caso de que suceda una interrupción entre dos instrucciones Ii y Ii+1,
Los efectos de todas las instrucciones hasta Ii (incluida) son permanentes ya que han terminadoNo debe haber ningún efecto relacionado con ninguna instrucción posterior a esta
El manejador de interrupciones puede abortar el programa o continuar con la instrucción Ii+1.
8
Efectos en la interrupcionesInstrucciones terminan fuera de orden
I1 DIV $6, $6, $4I2 LD $2, 45($3)I3 MULT $0, $2, $4I4 DIV $8, $6, $2I5 SUB $10, $0, $6I6 ADD $6, $8, $2
out-of-order comp 1 2 2 3 1 4 3 5 5 4 6 6 devolver f2 devolver f10
Considere la interrupciones
Las interrupciones precisas son difíciles de implementar a alta velocidad
- Porque se comienza a ejecutar instrucciones posteriores antes de que la excepción compruebe que se han terminado instrucciones anteriores
9
Manejo de excepciones(In-Order Five-Stage Pipeline)
• Conservar las banderas de excepción en el pipeline hasta el punto de commit (etapa Memoria).
• Las excepciones en etapas más tempranas rescriben excepciones de más adelantes.• Las excepciones externas sobre-escriben otras. • Si hay una excepción en el punto de commit: se actualizan los registros de Cause y EPC, se
“matan” las instrucciones de otras etapas y se actualiza el PC con la dirección de excepciones.
Asynchronous Interrupts
ExcD
PCD
PCInst. Mem D Decode E M
Data Mem W+
ExcE
PCE
ExcM
PCM
Cause
EPC
Kill D Stage
Kill F Stage
Kill E Stage
Illegal Opcode Overflow
Data Addr Except
PC Address Exceptions
Kill Writeback
Select Handler PC
Commit Point
10
Excepciones precisas en In-Order Commit
Las instrucciones son leídas y decodificadas y llevadas al reorder buffer en ordenLa ejecución fuera de orden ( se completan fuera de orden)Se hace Commit en orden (se escribe el estado de la arquitectura registros y memoria)
Se requiere almacenamiento temporal para guardar los resultados antes de hacer commit (Registros sombra--shadow registers-- y buffers de escritura--store buffers)
Fetch Decode
Execute
CommitReorder Buffer
In-order In-orderOut-of-order
Exception?
KillKill Kill
Inject handler PC
11
Reorder buffer
ptr2
next tocommit
ptr1
nextavailable
Añadir los campos <pd, dest, data, cause>, hacer commit de las instrucciones al banco de registros y a memoria en orden de programa el buffers es circular, en una excepción, se
borrar el ROB haciendo ptr1=ptr2(los stores tiene que esperar hasta commit para actualizar la memoria)
Inst# use exec op p1 src1 p2 src2 pd dest data cause
Extensiones al ROB para Excepciones precisas
12
Vuelta atrás (Rollback) y renombrado
El banco de registros ya no contiene los tag de renombrado.¿Cómo hace la etapa de decodificación para encontrar el tag de los registros fuente?
Buscar el campo “dest” en el reorder buffer
El banco de registros(solo instrucciones commited)
Reorderbuffer
Load Unit
FU FU FU Store Unit
< t, result >
t1
t2
.
.tn
Ins# use exec op p1 src1 p2 src2 pd dest data
Commit
13
Tabla de renombradoRegister
File
Reorder buffer
Load Unit
FU FU FU Store Unit
< t, result >
t1
t2
.
.tn
Ins# use exec op p1 src1 p2 src2 pd dest data
Commit
Rename Table
La tabla de renombrado es una cache para agilizar la búsqueda del nombre de registros. Se tiene que borrar después de que cada excepción sea tomada.
r1 t vr2
tagvalid bit
14
Recobrarse de un predicción de salto equivocada
Máquinas de ejecución en orden:– Se asume que ninguna instrucción despachada antes de resolver el salto
puede escribir en registros o memoria (write-back)– “Matar” todas las instrucciones en el pipeline detrás de la instrucción de
salto
Múltiples instrucciones después de la instrucción de salto podrían completar antes de que el salto se resuelva
Ejecución fuera de orden
15
Saltos mal predichos en el pipeline
Fetch Decode
Execute
CommitReorder Buffer
Kill
Kill Kill
BranchResolution
Inject correct PC
Pueden haber múltiples salto sin resolver en el ROBSe pueden resolver los salto fuera de orden, “matando” todas las instrucciones siguientes, en el ROB, al salto mal predicho
BranchPrediction
PC
Complete
16
t vt vt v
Recovering ROB/Renaming TableRegister File
Reorder buffer Load
UnitFU FU FU Store
Unit
< t, result >
t1
t2
.
.tn
Ins# use exec op p1 src1 p2 src2 pd dest data
Commit
Rename Table r1
t v
r2
Se toma una “foto ” (snapshot) de la tabla de renombrado cada que se hace una predicción de salto, se recupera la “foto” si se hace una mala predicción
Rename Snapshots
Ptr2 next to commit
Ptr1 next available
rollback next available
17
Diseño de “Data-in-ROB”(HP PA8000, Pentium Pro, Core2Duo, Nehalem)
En el momento de despachar del ROB, los registros fuente listos pueden estar en el banco de registros o en el “dest” del ROB (se deben copiar a src1/src2 si están listos antes de despachar)Cuando se completan, se escriben al campo “dest” y hacer un “broadcast” a los campos de fuente. Cuando se hace Issue, se leen las fuentes del ROB.
Banco de registros solo contiene estado terminado
Reorderbuffer
Load Unit
FU FU FU Store Unit
< t, result >
t1
t2
.
.tn
Ins# use exec op p1 src1 p2 src2 pd dest data
Commit
18
Banco de registros físicos unificado(MIPS R10K, Alpha 21264, Intel Pentium 4 & Sandy Bridge)
• Renombrar todos los registros de la arquitectura durante la etapa de decodificación, no se leen los valores de los registros
• Las unidades funcionales leen y escriben de un único banco de registros físicos unificado que guarda resultados terminados y registros temporales que están siendo calculados
• Se hace commit de las actualizaciones que se mapean de los registros arquitectónicos a los físicos, no hay movimiento de datos
Unified Physical Register File
Leer registos al despachar
Functional Units
Se escriben resultados al terminar
Committed Register Mapping
Decode Stage Register Mapping
19
Diseño del pipeline con registros físicos en el banco de registros
FetchDecode & Rename
Reorder BufferPC
BranchPrediction
Commit
BranchResolution
BranchUnit
ALU MEMStore Buffer
D$
Execute
In-Order
In-OrderOut-of-Order
Physical Reg. File
kill
kill
kill
kill
20
Tiempo de vida de los registros físicos
ld $1, ($3)addi $3, $1, #4sub $6, $7, $9add $3, $3, $6ld $6, ($1)add $6, $6, $3sd $6, ($1)ld $6, ($11)
ld P1, (P10)addi P2, P1, #4sub P3, P11, P12add P4, P2, P3ld P5, (P1)add P6, P5, P4sd P6, (P1)ld P7, (P13)
Rename
¿Cuando se puede reusar un registro físico?Cuando se vuelva a escribir en el mismo registro de la arquitectura
Los registros físicos guardan valores de instrucciones terminadas como valores especulativosLos registros físicos están separados del ROB (el ROB no contiene datos)
21
op p1 PR1 p2 PR2exuse Rd PRdLPRd
<x6>P5<x7>P6<x3>P7
P0
Pn
P1P2P3P4
x5P5x6P6x7
x0P8x1
x2P7x3
x4
ROB
Rename Table
Physical Regs Free List
ld x1, 0(x3)addi x3, x1, #4sub x6, x7, x6add x3, x3, x6ld x6, 0(x1)
ppp
P0P1P3P2P4
(LPRd requires third read port on Rename Table for each instruction)
<x1>P8 p
Manejo de los registros físicos
22
op p1 PR1 p2 PR2exuse Rd PRdLPRdROB
ld x1, 0(x3)addi x3, x1, #4sub x6, x7, x6add x3, x3, x6ld x6, 0(x1)
Free ListP0P1P3P2P4
<x6>P5<x7>P6<x3>P7
P0
Pn
P1P2P3P4
Physical Regs
ppp
<x1>P8 p
x ld p P7 x1 P0
x5P5x6P6x7
x0P8x1
x2P7x3
x4
Rename Table
P0
P8
Manejo de los registros físicos
23
op p1 PR1 p2 PR2exuse Rd PRdLPRdROB
ld x1, 0(x3)addi x3, x1, #4sub x6, x7, x6add x3, x3, x6ld x6, 0(x1)
Free ListP0P1P3P2P4
<x6>P5<x7>P6<x3>P7
P0
Pn
P1P2P3P4
Physical Regs
ppp
<R1>P8 p
x ld p P7 x1 P0
x5P5x6P6x7
x0P8x1
x2P7x3
x4
Rename Table
P0
P8P7
P1
x addi P0 x3 P1
Manejo de los registros físicos
24
op p1 PR1 p2 PR2exuse Rd PRdLPRdROB
ld x1, 0(x3)addi x3, x1, #4sub x6, x7, x6add x3, x3, x6ld x6, 0(x1)
Free ListP0P1P3P2P4
<x6>P5<x7>P6<x3>P7
P0
Pn
P1P2P3P4
Physical Regs
ppp
<R1>P8 p
x ld p P7 x1 P0
x5P5x6P6x7
x0P8x1
x2P7x3
x4
Rename Table
P0
P8P7
P1
x addi P0 x3 P1P5
P3
x sub p P6 p P5 x6 P3
Manejo de los registros físicos
25
op p1 PR1 p2 PR2exuse Rd PRdLPRdROB
ld x1, 0(x3)addi x3, x1, #4sub x6, x7, x6add x3, x3, x6ld x6, 0(x1)
Free ListP0P1P3P2P4
<x6>P5<x7>P6<x3>P7
P0
Pn
P1P2P3P4
Physical Regs
ppp
<x1>P8 p
x ld p P7 x1 P0
x5P5x6P6x7
x0P8x1
x2P7x3
x4
Rename Table
P0
P8P7
P1
x addi P0 x3 P1P5
P3
x sub p P6 p P5 x6 P3P1
P2
x add P1 P3 x3 P2
Manejo de los registros físicos
26
op p1 PR1 p2 PR2exuse Rd PRdLPRdROB
ld x1, 0(x3)addi x3, x1, #4sub x6, x7, x6add x3, x3, x6ld x6, 0(x1)
Free ListP0P1P3P2P4
<x6>P5<x7>P6<x3>P7
P0
Pn
P1P2P3P4
Physical Regs
ppp
<x1>P8 p
x ld p P7 x1 P0
x5P5x6P6x7
x0P8x1
x2P7x3
x4
Rename Table
P0
P8P7
P1
x addi P0 x3 P1P5
P3
x sub p P6 p P5 x6 P3P1
P2
x add P1 P3 x3 P2x ld P0 x6 P4P3
P4
Manejo de los registros físicos
27
op p1 PR1 p2 PR2exuse Rd PRdLPRdROB
x ld p P7 x1 P0x addi P0 x3 P1x sub p P6 p P5 x6 P3
x ld p P7 x1 P0
ld x1, 0(x3)addi x3, x1, #4sub x6, x7, x6add x3, x3, x6ld x6, 0(x1)
Free ListP0P1P3P2P4
<x6>P5<x7>P6<x3>P7
P0
Pn
P1P2P3P4
Physical Regs
ppp
<x1>P8 p
x5P5x6P6x7
x0P8x1
x2P7x3
x4
Rename Table
P0
P8P7
P1
P5
P3
P1
P2
x add P1 P3 x3 P2x ld P0 x6 P4P3
P4
Execute & Commitp
p
p<x1>
P8
x
Manejo de los registros físicos
28
op p1 PR1 p2 PR2exuse Rd PRdLPRdROB
x sub p P6 p P5 x6 P3x addi P0 x3 P1x addi P0 x3 P1
ld x1, 0(x3)addi x3, x1, #4sub x6, x7, x6add x3, x3, x6ld x6, 0(x1)
Free ListP0P1P3P2P4
<x6>P5<x7>P6<x3>P7
P0
Pn
P1P2P3P4
Physical Regs
ppp
P8
x x ld p P7 x1 P0
x5P5x6P6x7
x0P8x1
x2P7x3
x4
Rename Table
P0
P8P7
P1
P5
P3
P1
P2
x add P1 P3 x3 P2x ld P0 x6 P4P3
P4
Execute & Commitp
p
p<x1>
P8
x
p
p<x3>
P7
Manejo de los registros físicos
29
El buffer de reordenamiento contiene información de las excepciones para el commit.
La ventana de instrucciones contiene las instrucciones que han sido decodificadas y renombradas pero que no han sido despachadas para ejecución. Contiene los tag de los registros, bits de presencia y puntero a la posición del ROB.
op p1 PR1 p2 PR2 PRduseex ROB#
El ROB normalmente es varias veces más grande que la ventana de instrucciones – ¿por qué?
Rd LPRd PC Except?Ptr2 next to commit
Ptr1 next available
Done?
Separar la ventana de instrucciones pendientes del ROB
30
…ld x1, (x3)add x3, x1, x2sub x6, x7, x9add x3, x3, x6ld x6, (x1)add x6, x6, x3sd x6, (x1)ld x6, (x1)…
(Older instructions)
(Newer instructions)
Cycle t
…ld x1, (x3)add x3, x1, x2sub x6, x7, x9add x3, x3, x6ld x6, (x1)add x6, x6, x3sd x6, (x1)ld x6, (x1)…
Commit
Fetch
Cycle t + 1
Execute
El ROB contiene instrucciones activas(Decodificadas pero no Committed)
31
sd x1, (x2)ld x3, (x4)
¿Se puede ejecutar el load?
Dependencias de memoria
32
• Ejecutar todos los loads y stores en orden de programa
=> Los Loads y stores no pueden ser despachados para ejecución desde el ROB hasta que todos los loads y estores previos hayan completado ejecución
• Sin embargo se pueden ejecutar fuera de orden, respecto a otro tipo de instrucciones
• Se requiere una estructura para manejar el orden de las instrucciones de memoria
Cola de memoria en orden
33
sd x1, (x2)ld x3, (x4)
• Dividir la ejecución de los store en dos faces: cálculo de las direcciones y escritura de datos
• Se puede ejecutar el load antes de que un store, si sus direcciones son conocidas y diferentes x4 != x2
• Cada dirección de los loads se compara con las direcciones de todos los stores que no han sido committed
• No ejecutar load si cualquiera de las direcciones de los stores anteriores no se conocen
(MIPS R10K, cola de direcciones de 16 entradas)
Ejecución conservativa de loads O-o-O
34
Diseño del pipeline con registros físicos en el banco de registros
FetchDecode & Rename
Reorder BufferPC
BranchPrediction
Commit
BranchResolution
BranchUnit
ALU MEMStore Buffer
D$
Execute
In-Order
In-OrderOut-of-Order
Physical Reg. File
kill
kill
kill
kill
35
Flujo de instrucciones en un pipeline con un banco de registro físicos unificado
• Fetch– Tomar los bits de la instrucción del PC actual y ponerlos en el buffer de
fetch– Actualizar el PC usando la siguiente dirección o el predictor de saltos
(BTB)• Decode/Rename
– Tomar la instrucción del buffer de fetch– Asignar recursos para ejecutar la instrucción:
• Registro físico de destino, si la instrucción escribe registro• Entrada en el ROB para permitir commit en orden• Entrada en la ventana de instrucciones para esperar ejecución• Entrada en el buffer de memoria, si es load o store
– Decode hará stall si los recursos no están disponibles– Renombra registros fuente y destino– Comprueba si los registros fuente están disponibles– Inserta la instrucción en el los buffer de ventana, ROB y memoria
36
Instrucciones de Memoria• Dividir los stores en dos piezas durante decodificación:
– Cálculo de la dirección– Movimiento de datos
• Asignar espacio en orden de programa en el buffer de memoria durante decodificación
• Stores:– Calculo de la dirección y guardarla en el buffer de stores– Movimiento de datos copia el valor en el buffer de stores– Estas dos etapas se ejecutan independientemente desde la ventana de
instrucciones– Los Stores solo hacen commit de los datos en el punto de commit
• Loads:– El cálculo de las direcciones de los loads se ejecutan desde la ventana– Los load una vez calculan la dirección efectiva buscdan en el buffer de
memoria– Los loads puede que tengan que esperar en el buffer de memoria hasta que
algunos store se resuelvan
37
Etapa de Issue
• La escritura de resultados cuando terminan las instrucciones, puede “despertar” algunas instrucciones de la ventana de Instrucciones poniendo sus registros fuente como listos
• Debe seleccionar algunas instrucciones para ser despachadas– Un árbitro selecciona un subconjunto de instrucciones listas para
ejecución– Ejemplo de políticas: aleatorio, más vieja primero, crítica primero
• Las instrucciones listas en la etapa de Issue son enviadas a ejecución
38
Etapa de ejecución• Leer los registros listos del banco de registros
y/o de las unidades de forwarding desde otras unidades funcionales
• Ejecutar en una unidad funcional• Escribir los resultados en los registros físicos (o
en el buffer de store)• Producir excepciones, escribir en el ROB• Liberar instrucciones en la ventana de
instrucciones
39
Etapa de Commit• Leer las instrucciones completadas en orden
desde el ROB– (puede requerir esperar por la próxima instrucción más vieja que
termine)
• Si hay una excepción– Vaciar el pipeline, saltar al manejador de excepciones
• De lo contrario, liberar recursos:– Liberar registros físicos cuando se vuelva a escribir en el mismo
registro físico– Liberar espacio en el ROB– Liberar espacio en buffer de memoria
Fuentes de Información• Parte de este material fue tomado de
– Krste Asanovic (UC Berkeley, curso cs152)– Este a su vez da el siguiente Acknowledgment:
• These slides contain material developed and copyright by:– Arvind (MIT)– Krste Asanovic (MIT/UCB)– Joel Emer (Intel/MIT)– James Hoe (CMU)– John Kubiatowicz (UCB)– David Patterson (UCB)
• MIT material derived from course 6.823• UCB material derived from course CS252
Circuitos Digitales II 2012 - 1
40