MC542
Organização de Computadores
Teoria e Prática
2007
Prof. Paulo Cesar Centoducatte
[email protected]
www.ic.unicamp.br/~ducatte
MC542
4.1
MC542
Arquitetura de Computadores
Micro-Arquitetura Pipeline
“DDCA” - (Capítulo 7)
“COD” - (Capítulo )
MC542
4.2
Micro-Arquitetura Pipeline
Sumário
•
Introdução
•
MIPS Pepilinig
•
•
– Execução Pepiline
–
–
–
–
–
5 estágios
MIPS Pipelined
Execução de Instruções no MIPS Pipeline
DataPath Single-Cycle e Pipelining
Controle do Pepiline
Limites de Pipelining
– Hazards
» Estrutura
» Dado
» Controle
Como Tratar os Hazards de Dados
MC542
4.3
Pipelining - Conceito
• Exemplo: Lavanderia
• 4 trouxas para serem lavadas
A
B
C
D
– Lavar: 30 minutos
– Secar: 40 minutos
– Passar: 20 minutos
MC542
4.4
Lavanderia Seqüencial
6
O
r
d
e
m
T
a
r
e
f
a
s
7
8
9
10
11
Horas
Tempo
30 40 20 30 40 20 30 40 20 30 40 20
A
B
C
D
• Lavanderia seqüencial: 6 horas para lavar 4 trouxas
• Se for usado pipelining, quanto tempo?
MC542
4.5
Lavanderia Pipelined
6
O
r
d
e
m
T
a
r
e
f
a
s
7
8
9
10
11
Horas
Tempo
30 40 40 40 40 20
A
B
C
D
• Lavanderia Pipelined: 3.5 horas para 4 trouxas
MC542
4.6
Pipelining
6
T
a
s
k
O
r
d
e
r
7
8
30 40 40 40
A
B
C
D
• O Pipelining não ajuda na
latência de uma tarefa, ajuda
no throughput de toda a carga
Time
de trabalho
40 20 • O período do Pipeline é
limitado pelo estágio mais
lento
• Múltiplas tarefas simultâneas
• Speedup potencial = Número
de estágios
• Estágios não balanceados
reduzem o speedup
• O Tempo de “preenchimento” e
de “esvaziamento“ reduzem o
speedup
9
MC542
4.7
CPU Pipeline
• Executam bilhões de instruções: throughput
• Características desejáveis em um conjunto de
instruções (ISA) para pipelining?
– Instruções de tamanho variável vs.
Todas instruções do mesmo tamanho?
– Operandos em memória em qq operação vs.
operandos em memória somente para loads
e stores?
– Formato das instruções irregular vs.
formato regular das instruções (ié.
Operandos nos mesmos lugares)?
MC542
4.8
Um RISC Típico
• Formato de instruções de 32-bit (3 formatos)
• Acesso à memória somente via instruções
load/store
• 32 GPR de 32-bits (R0 contém zero)
• Instruções aritméticas: 3-address, reg-reg,
registradores no mesmo lugar
• Modo de endereçamento simples para load/store
(base + displacement)
– Sem indireção
• Condições simples para o branch
• Delayed branch
SPARC, MIPS, HP PA-Risc, DEC Alpha, IBM PowerPC,
CDC 6600, CDC 7600, Cray-1, Cray-2, Cray-3
MC542
4.9
Exemplo: MIPS (Localização dos regs)
Register-Register
31
26 25
Op
21 20
Rs1
16 15
Rs2
11 10
6 5
Rd
0
Opx
Register-Immediate
31
26 25
Op
21 20
Rs1
16 15
Rd
immediate
0
Branch
31
26 25
Op
Rs1
21 20
16 15
Rs2
immediate
0
Jump / Call
31
26 25
Op
target
0
MC542
4.10
Processador MIPS Pipelined
• Paralelismo Temporal
• Divide o processador single-cycle em 5 estágios:
–
–
–
–
–
Fetch
Decode
Execute
Memory
Writeback
• Adicinar registradores de pipeline entre os estágios
MC542
4.11
Processador MIPS Pipelined
Single-Cycle
0
100
200
300
400
500
600
700
800
900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900
Instr
1
Fetch
Instruction
Decode
Read Reg
Execute
ALU
Time (ps)
Memory
Write
Read / Write Reg
Fetch
Instruction
2
Decode
Read Reg
Execute
ALU
Memory
Write
Read / Write Reg
Pipelined
Instr
1
2
3
Fetch
Instruction
Decode
Read Reg
Fetch
Instruction
Execute
ALU
Decode
Read Reg
Fetch
Instruction
Memory
Read/Write
Execute
ALU
Decode
Read Reg
Write
Reg
Memory
Read/Write
Execute
ALU
Write
Reg
Memory
Read/Write
Write
Reg
MC542
4.12
Processador MIPS Pipelined
Jump
31:26
5:0
MemtoReg
Control
MemWrite
Unit
Branch
ALUControl2:0
PCSrc
Op
ALUSrc
Funct RegDst
RegWrite
CLK
1
0
PC'
PC
1
A
RD
Instr
Instruction
Memory
25:21
20:16
WE3
A1
A2
RD2
A3
WD3
0 SrcB
1
Register
File
20:16
PCJump
+
WriteReg4:0
PCPlus4
27:0
WriteData
A
RD
Data
Memory
ReadData
0
Result
1
WD
1
SignImm
15:0
ALUResult
WE
0
15:11
4
Zero
SrcA
RD1
ALU
0
CLK
Sign Extend
<<2
+
CLK
PCBranch
31:28
25:0
<<2
MIPS single-cycle
MC542
4.13
Processador MIPS Pipelined
Instruction
Fetch
Instr. Decode
Reg. Fetch
Execute
Addr. Calc
Next SEQ PC
Adder
4
Zero?
RS1
L
M
D
MUX
Data
Memory
ALU
Imm
MUX MUX
RD
Reg File
Inst
Memory
Address
RS2
Write
Back
MUX
Next PC
Memory
Access
Sign
Extend
WB Data
MC542
4.14
Processador MIPS Pipelined
• Abstração da execução Pipeline
1
2
IM lw
$0
RF 40
3
4
5
6
7
8
9
10
Time (cycles)
lw
$s2, 40($0)
add $s3, $t1, $t2
sub $s4, $s1, $s5
and $s5, $t5, $t6
sw
$s6, 20($s1)
or
$s7, $t3, $t4
IM add
+
$t1
RF $t2
IM sub
DM
+
$s1
RF $s5
IM and
$s2
RF
DM
-
$t5
RF $t6
IM sw
$s3
RF
DM
&
$s1
RF 20
IM or
$s4
RF
DM
+
$t3
RF $t4
$s5
RF
DM
|
$s6
RF
DM
$s7
RF
MC542
4.15
Processador MIPS Pipelined
• DataPath Single-Cycle e Pipelining
CLK
0
PC'
PC
1
A
Instr
RD
Instruction
Memory
25:21
20:16
CLK
WE3
A1
A2
SrcA
RD1
RD2
0
A3
SrcB
1
WD3
+
Zero
ALU
CLK
0
15:11
1
ALUResult
WriteData
Register
File
20:16
WE
A
ReadData
RD
0
1
Data
Memory
WD
WriteReg4:0
PCPlus4
SignImm
15:0
<<2
Sign Extend
+
4
PCBranch
Result
CLK
CLK
CLK
PC'
PCF
1
A
RD
Instruction
Memory
InstrD
25:21
20:16
WE3
A1
A2
CLK
0
A3
WriteDataE
RtE
20:16
RdE
0
WriteDataM
A
RD
ReadDataW
0
1
Data
Memory
WD
WriteRegE4:0
1
+
15:11
ALUOutM
SrcBE
1
Register
File
WE
ZeroM
SrcAE
RD1
RD2
WD3
ALUOutW
CLK
4
PCPlus4F
SignImmE
15:0
Sign Extend
PCPlus4D
<<2
PCBranchM
+
0
CLK
ALU
CLK
PCPlus4E
ResultW
Fetch
Decode
Execute
Memory
Writeback
MC542
4.16
Processador MIPS Pipelined
Execute
Addr. Calc
Instr. Decode
Reg. Fetch
Next SEQ PC
Next SEQ PC
Adder
4
Zero?
RS1
MUX
MEM/WB
Data
Memory
EX/MEM
ALU
MUX MUX
ID/EX
Imm
Reg File
IF/ID
Memory
Address
RS2
Write
Back
MUX
Next PC
Memory
Access
WB Data
Instruction
Fetch
Sign
Extend
RD
RD
RD
MC542
4.17
Processador MIPS Pipelined
CLK
CLK
PC'
PCF
1
A
RD
Instruction
Memory
InstrD
25:21
20:16
A1
CLK
WE3
A2
CLK
RD2
0 SrcBE
1
A3
WD3
Register
File
RtE
20:16
RdE
15:11
+
PCPlus4F
WriteDataE
WriteDataM
WriteRegE4:0
WriteRegM4:0
A
RD
ReadDataW
0
1
Data
Memory
WD
WriteRegW4:0
<<2
Sign Extend
PCPlus4D
ALUOutM
1
SignImmE
15:0
4
0
WE
ZeroM
SrcAE
RD1
+
0
CLK
ALU
CLK
CLK
ALUOutW
PCBranchM
PCPlus4E
ResultW
Fetch
Decode
Execute
Memory
Writeback
MC542
4.18
Processador MIPS Pipelined
• Controle do Pepiline
CLK
RegWriteD
Control
MemtoRegD
Unit
31:26
5:0
0
PC'
PCF
1
A
RD
Instruction
Memory
RegWriteE
RegWriteM
RegWriteW
MemtoRegM
MemtoRegW
MemWriteD
MemWriteE
MemWriteM
BranchM
BranchD
BranchE
Op
ALUControlD
ALUControlE2:0
Funct
ALUSrcD
ALUSrcE
RegDstD
RegDstE
ALUOutW
CLK
InstrD
25:21
20:16
CLK
WE3
A1
A2
WD3
0 SrcBE
1
Register
File
15:11
RdE
0
15:0
PCPlus4F
Sign Extend
PCPlus4D
ALUOutM
WriteDataE
WriteDataM
WriteRegE4:0
WriteRegM4:0
A
RD
Data
Memory
ReadDataW
0
1
WD
WriteRegW4:0
1
+
20:16
RtE
WE
ZeroM
SrcAE
RD1
RD2
A3
4
PCSrcM
ALU
CLK
CLK
MemtoRegE
SignImmE
<<2
+
CLK
CLK
PCBranchM
PCPlus4E
ResultW
MC542
4.19
Limites de Pipelining
• Hazards: impedem que a próxima instrução seja
executada no ciclo de clock “previsto” para ela
– Structural hazards: O HW não suporta uma dada
combinação de instruções
– Data hazards: Uma Instrução depende do
resultado da instrução anterior que ainda está no
pipeline
– Control hazards: Causado pelo delay entre o
fetching de uma instrução e a decisão sobre a
mudança do fluxo de execução (branches e jumps).
MC542
4.20
Memória Única (D/I) - Structural Hazards
Time (clock cycles)
Reg
DMem
Reg
DMem
Reg
DMem
Reg
ALU
Instr 4
Ifetch
ALU
Instr 3
DMem
ALU
O
r
d
e
r
Instr 2
Reg
ALU
I Load Ifetch
n
s
Instr 1
t
r.
ALU
Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7
Ifetch
Ifetch
Reg
Ifetch
Reg
Reg
Reg
DMem
Reg
MC542
4.21
Memória Única (D/I) - Structural Hazards
Time (clock cycles)
Stall
Instr 3
DMem
Ifetch
Reg
DMem
Reg
ALU
Ifetch
Bubble
Reg
Reg
DMem
Bubble Bubble
Ifetch
Reg
Reg
Bubble
ALU
O
r
d
e
r
Instr 2
Reg
ALU
I Load Ifetch
n
s
Instr 1
t
r.
ALU
Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7
Bubble
DMem
Reg
MC542
4.22
Data Hazards
• Read After Write (RAW)
InstrJ lê o operando antes da InstrI escreve-lo
I: add r1,r2,r3
J: sub r4,r1,r3
– Causada por uma “Dependência” (nomenclatura de
compiladores).
MC542
4.23
Data Hazard em R1
Time (clock cycles)
and r6,r1,r7
or
r8,r1,r9
xor r10,r1,r11
Ifetch
DMem
Reg
DMem
Ifetch
Reg
DMem
Ifetch
Reg
DMem
Ifetch
Reg
ALU
sub r4,r1,r3
Reg
ALU
Ifetch
ALU
O
r
d
e
r
add r1,r2,r3
WB
ALU
I
n
s
t
r.
MEM
ALU
IF ID/RF EX
Reg
Reg
Reg
Reg
DMem
MC542
4.24
Reg
Data Hazards
• Write After Read (WAR)
InstrJ escreve o operando antes que a InstrI o
leia
I: sub r4,r1,r3
J: add r1,r2,r3
K: mul r6,r1,r7
• Chamada “anti-dependência” (nomenclatura de
compiladores). Devido ao reuso do nome “r1”.
• Não ocorre no pipeline do MIPS:
– Todas instruções usam 5 estágios, e
– Leituras são no estágio 2, e
– Escritas são no estágio 5
MC542
4.25
Data Hazards
• Write After Write (WAW)
InstrJ escreve o operando antes que a InstrI o
escreva.
I: sub r1,r4,r3
J: add r1,r2,r3
K: mul r6,r1,r7
• Chamada “dependência de saída” (nomenclatura de
compiladores). Devido ao reuso do nome “r1”.
• Não ocorre no pipeline do MIPS:
– Todas Instruções são de 5 estágios, e
– Escritas são sempre no 5 estágio
– (WAR e WAW ocorrem em pipelines mais sofisticados)
MC542
4.26
Como Tratar os Data Hazards
• Inserir instruções nops no código
• Rearranjar o código em tempo de compilação
• Stall o processador em tempo de execução (runtime)
• Forward data
MC542
4.27
Data Hazards – Solução por SW
• Compilador reconhece o data hazard e troca a ordem das
instruções (quando possível)
• Compilador reconhece o data hazard e adiciona nops
Exemplo:
sub R2, R1, R3
; reg R2 escrito por sub
nop
; no operation
nop
and R12, R2, R5
or
; resultado do sub disponível
R13, R6, R2
add R14, R2, R2
sw
100 (R2), R15
MC542
4.28
Data Hazard Control: Stalls
• Hazard ocorre quando a instr. Lê (no estágio ID) um
reg que será escrito, por uma instr. anterior (no
estágio EX, MEM, WB)
• Solução: Detectar o hazard e parar a instrução no
pipeline até o hazard ser resolvido
• Detectar o hazard pela comparação do campo read
no IF/ID pipeline register com o campo write dos
outros pipeline registers (ID/EX, EX/MEM,
MEM/WB)
• Adicionar bubble no pipeline
–
Preservar o PC e o IF/ID pipeline register
MC542
4.29
Processador MIPS Pipelined
• Data Forwarding
8
7
6
5
4
3
2
1
Time (cycles)
add $s0, $s2, $s3
and $t0, $s0, $s1
or
$t1, $s4, $s0
sub $t2, $s0, $s5
IM
add
$s2
RF $s3
IM
and
DM
+
$s0
RF
$s0
RF $s1
IM
or
DM
&
$t0
RF
$s4
RF $s0
IM
sub
DM
|
$t1
RF
$s0
RF $s5
-
DM
$t2
RF
MC542
4.30
Processador MIPS Pipelined
• Data Forwarding
1
2
3
4
5
6
7
8
Time (cycles)
add $s0, $s2, $s3
and $t0, $s0, $s1
or $t1, $s4, $s0
sub $t2, $s0, $s5
IM
add
$s2
RF $s3
IM
and
DM
+
$s0
RF
$s0
RF $s1
IM
or
DM
&
$t0
RF
$s4
RF $s0
IM
sub
DM
|
$t1
RF
$s0
RF $s5
-
DM
$t2
RF
MC542
4.31
Processador MIPS Pipelined
• HW para forwarding
NextPC
mux
MEM/WR
EX/MEM
ALU
mux
ID/EX
Registers
mux
Immediate
Data
Memory
MC542
4.32
Processador MIPS Pipelined
• HW para forwarding
CLK
Control
Unit
31:26
5:0
A
RD
Instruction
Memory
MemtoRegE
MemtoRegM
MemtoRegW
MemWriteD
MemWriteE
MemWriteM
ALUControlD2:0
ALUControlE2:0
Op
ALUSrcD
ALUSrcE
Funct
RegDstD
RegDstE
BranchD
BranchE
InstrD
CLK
WE3
25:21
A1
20:16
A2
RD2
A3
Register
WD3
File
RD1
25:21
20:16
15:11
15:0
4
PCSrcM
BranchM
Sign
Extend
SrcAE
00
01
10
00
01
10
RsD
RsE
RtD
RtE
RdD
RdE
WE
ZeroM
0 SrcBE
1
ALUOutM
WriteDataM
WriteDataE
A
RD
Data
Memory
WD
ReadDataW
ALUOutW
0
1
WriteRegE4:0
SignImmD
WriteRegM4:0
1
0
WriteRegW 4:0
SignImmE
+
<<2
PCPlus4D
PCPlus4E
PCBranchM
RegWriteW
ResultW
RegWriteM
PCPlus4F
ForwardBE
PCF
RegWriteW
MemtoRegD
ForwardAE
PC'
RegWriteM
CLK
+
0
1
CLK
RegWriteE
ALU
CLK
CLK
CLK
RegWriteD
Hazard Unit
MC542
4.33
Processador MIPS Pipelined
• Forward para o estágio Execute a partir de:
– Memory stage ou
– Writeback stage
• Lógica de Forwarding para ForwardAE:
((rsE != 0) AND (rsE == WriteRegM) AND RegWriteM) then
ForwardAE = 10
else if ((rsE != 0) AND (rsE == WriteRegW) AND RegWriteW) then
ForwardAE = 01
else
ForwardAE = 00
if
• Lógica de Forwarding para ForwardBE similar, trocando rsE com
rtE, e ForwardAE com ForwardBE
MC542
4.34
Processador MIPS Pipelined
• Data Hazard com Forwarding
and r6,r1,r7
or
r8,r1,r9
DMem
Ifetch
Reg
DMem
Reg
Ifetch
Ifetch
Reg
Reg
Reg
DMem
ALU
O
r
d
e
r
sub r4,r1,r6
Reg
ALU
lw r1, 0(r2) Ifetch
ALU
I
n
s
t
r.
ALU
Time (clock cycles)
Reg
Reg
DMem
MC542
4.35
Processador MIPS Pipelined
• Data Hazard com Forwarding
and r6,r1,r7
or r8,r1,r9
Reg
DMem
Ifetch
Reg
Bubble
Ifetch
Bubble
Reg
Bubble
Ifetch
Reg
DMem
Reg
Reg
DMem
ALU
sub r4,r1,r6
Ifetch
ALU
O
r
d
e
r
lw r1, 0(r2)
ALU
I
n
s
t
r.
ALU
Time (clock cycles)
Reg
DMem
MC542
4.36
Processador MIPS Pipelined
• Hardware para Stall
Control
Unit
31:26
5:0
1
InstrD
RD
A
Instruction
Memory
RegWriteM
RegWriteW
MemtoRegD
MemtoRegE
MemtoRegM
MemtoRegW
MemWriteD
MemWriteE
MemWriteM
ALUControlD2:0
ALUControlE2:0
Op
ALUSrcD
ALUSrcE
Funct
RegDstD
RegDstE
BranchD
BranchE
25:21
20:16
A1
CLK
WE3
WD3
RD1
20:16
15:11
+
00
01
10
Register
File
25:21
15:0
SrcAE
00
01
10
RD2
A2
A3
4
PCSrcM
BranchM
Sign
Extend
0 SrcBE
1
RsE
RtD
RtE
RdD
RdE
ALUOutM
WriteDataM
WriteDataE
RsD
WE
ZeroM
ALU
PCF
PC'
EN
RD
Data
Memory
WD
A
ReadDataW
ALUOutW
0
WriteRegE4:0
1
0
WriteRegW 4:0
WriteRegM4:0
1
SignImmE
SignImmD
EN
PCPlus4F
PCPlus4D
CLR
+
<<2
PCPlus4E
PCBranchM
RegWriteW
RegWriteM
MemtoRegE
ForwardBE
ForwardAE
FlushE
StallF
ResultW
StallD
0
RegWriteD
RegWriteE
CLK
CLK
CLK
CLK
CLK
CLK
Hazard Unit
MC542
4.37
Processador MIPS Pipelined
• Lógica para Stall:
lwstall = ((rsD == rtE) OR (rtD == rtE)) AND MemtoRegE
StallF = StallD = FlushE = lwstall
MC542
4.38
Processador MIPS Pipelined
• Load Hazards - Software Scheduling
Código para (a, b,
a = b + c;
d = e – f;
Slow_code:
LW
LW
ADD
SW
LW
LW
SUB
SW
c, d ,e, f na memória).
Rb,b
Rc,c
Ra,Rb,Rc
a,Ra
Re,e
Rf,f
Rd,Re,Rf
d,Rd
Fast_code:
LW
LW
LW
ADD
LW
SW
SUB
SW
Rb,b
Rc,c
Re,e
Ra,Rb,Rc
Rf,f
a,Ra
Rd,Re,Rf
d,Rd
MC542
4.39
Processador MIPS Pipelined
Control Hazard
• beq: o branch não é determinado até o 4 estágio do pipeline
• Definições:
– Branch delay slot(s): Instruções buscadas antes do branch ser
determinado
– Misprediction penalty: número de instruções flushed quando o branch
é taken
• Várias estratégias são usadas para lidar com control hazards:
– Stall o pipeline
– Rearranjar o código e por instruções “úteis” no(s) branch delay
slot(s)
– Reduzir o misprediction penalty (determinar o branch mais cedo no
pipeline)
– Flush pipeline quando o branch é taken
MC542
4.40
22: add r8,r1,r9
36: xor r10,r1,r11
Reg
DMem
Ifetch
Reg
DMem
Ifetch
Reg
DMem
Ifetch
Reg
ALU
r6,r1,r7
Ifetch
DMem
ALU
18: or
Reg
ALU
14: and r2,r3,r5
Ifetch
ALU
10: beq r1,r3,36
ALU
Processador MIPS Pipelined
Reg
Reg
Reg
Reg
DMem
MC542
4.41
Reg
Processador MIPS Pipelined
Execute
Addr. Calc
Instr. Decode
Reg. Fetch
Next SEQ PC
Next SEQ PC
Adder
4
Zero?
RS1
RD
RD
RD
MUX
Sign
Extend
MEM/WB
Data
Memory
EX/MEM
ALU
MUX MUX
ID/EX
Imm
Reg File
IF/ID
Memory
Address
RS2
Write
Back
MUX
Next PC
Memory
Access
WB Data
Instruction
Fetch
MC542
4.42
Processador MIPS Pipelined
Exemplo: Impacto do Branch Stall no Desempenho
• Se CPI = 1, 30% branches, 3-cycle stall
 CPI = 1.9!
•
Solução para minimizar os efeitos:
– Determinar branch taken ou não o mais cedo, e
– Calcular o endereço alvo do branch logo
• MIPS branch: testa se regs = ou 
• Solução MIPS:
– Zero test no estágio ID/RF
– Adder para calcular o novo PC no estágio ID/RF
– 1 clock cycle penalty por branch versus 3
MC542
4.43
Processador MIPS Pipelined
Instruction
Fetch
Memory
Access
Write
Back
Adder
Adder
MUX
Next
SEQ PC
Next PC
=
RS1
RD
RD
RD
MUX
Sign
Extend
MEM/WB
Data
Memory
EX/MEM
ALU
MUX
ID/EX
Imm
Reg File
IF/ID
Memory
Address
RS2
WB Data
4
Execute
Addr. Calc
Instr. Decode
Reg. Fetch
MC542
4.44
Processador MIPS Pipelined
CLK
Control
Unit
31:26
5:0
CLK
CLK
RegWriteD
RegWriteE
RegWriteM
RegWriteW
MemtoRegD
MemtoRegE
MemtoRegM
MemtoRegW
MemWriteD
MemWriteE
MemWriteM
ALUControlD2:0
ALUControlE2:0
Op
ALUSrcD
ALUSrcE
Funct
RegDstD
RegDstE
BranchD
PCF
EN
A
InstrD
RD
Instruction
Memory
25:21
20:16
A1
WE3
A2
A3
WD3
RD1
4
00
01
10
Register
File
15:11
Sign
Extend
WE
SrcAE
00
01
10
RD2
20:16
15:0
CLK
=
25:21
+
0 SrcBE
1
WriteDataE
RsD
RsE
RtD
RtE
RdE
RdE
ALUOutM
WriteDataM
A
RD
Data
Memory
WD
ReadDataW
ALUOutW
0
WriteRegE4:0
WriteRegM4:0
1
0
WriteRegW 4:0
1
SignImmD
SignImmE
+
<<2
PCPlus4D
CLR
CLR
EN
PCPlus4F
PCBranchD
RegWriteW
RegWriteM
MemtoRegE
ForwardBE
ForwardAE
FlushE
ResultW
StallD
1
PC'
StallF
0
PCSrcD
EqualD
CLK
ALU
CLK
CLK
Hazard Unit
MC542
4.45
Processador MIPS Pipelined
1
2
3
4
5
6
7
8
9
Time (cycles)
20
beq $t1, $t2, 40
24
and $t0, $s0, $s1
28
or
2C
sub $t2, $s0, $s5
30
...
IM
lw
$t1
RF $t2
IM
and
DM
-
$s0
RF $s1
&
DM
Flush
this
instruction
RF
$t1, $s4, $s0
...
slt $t3, $s2, $s3
IM
slt
$s2
RF $s3
slt
64
RF
DM
$t3
RF
MC542
4.46
Processador MIPS Pipelined
Alternativas para Branch Hazard
#1: Stall até a decisão se o branch será tomado ou não
#2: Predict Branch Not Taken
–
–
–
–
–
Executar a próxima instrução
“Invalidar” as instruções no pipeline se branch é tamado
Vantagem: retarda a atualização do pipeline
47% dos branches no MIPS não são tomados, em média
PC+4 já está computado, use-o para pegar a próxima instrução
#3: Predict Branch Taken
– 53% dos branches do MIPS são tomados, em média
– “branch target address” no MIPS ainda não foi calculado
» 1 cycle branch penalty
» Em outras máquinas esse penalty pode não ocorrer
MC542
4.47
Processador MIPS Pipelined
Alternativas para Branch Hazard
#4: Delayed Branch
– Define-se que o branch será tamado APÓS a uma dada
quantidade de instruções
branch instruction
sequential successor1
sequential successor2
........
sequential successorn
branch target if taken
Branch delay de tamanho n
(n delay slots)
– 1 slot delay permite a decisão e o calculo do “branch target
address” no pipeline de 5 estágios
– MIPS usa está solução
MC542
4.48
Processador MIPS Pipelined
Delayed Branch
• Qual instrução usar para preencher o branch delay
slot?
– Antes do branch
– Do target address ( avaliada somente se branch taken)
– Após ao branch (somente avaliada se branch not taken)
MC542
4.49
Processador MIPS Pipelined
MC542
4.50
Processador MIPS Pipelined
• Compilador: single branch delay slot:
– Preenche +/- 60% dos branch delay slots
– +/- 80% das instruções executadas no branch
delay slots são utéis à computação
– +/- 50% (60% x 80%) dos slots preenchidos são
utéis
MC542
4.51
Processador MIPS Pipelined
Tratando data e control hazards
CLK
Control
Unit
31:26
5:0
CLK
CLK
RegWriteD
RegWriteE
RegWriteM
RegWriteW
MemtoRegD
MemtoRegE
MemtoRegM
MemtoRegW
MemWriteD
MemWriteE
MemWriteM
ALUControlD2:0
ALUControlE2:0
Op
ALUSrcD
ALUSrcE
Funct
RegDstD
RegDstE
BranchD
PC'
PCF
EN
A
InstrD
RD
Instruction
Memory
25:21
20:16
A1
WE3
RD1
0
1
A2
RD2
A3
Register
WD3
File
0
1
+
4
00
01
10
0 SrcBE
1
RsD
RsE
RtD
RtE
RdD
RdE
ALUOutM
WriteDataM
WriteDataE
15:11
Sign
Extend
WE
SrcAE
00
01
10
20:16
15:0
CLK
=
25:21
A
RD
Data
Memory
WD
ReadDataW
ALUOutW
0
1
WriteRegE4:0
SignImmD
WriteRegM4:0
1
0
WriteRegW 4:0
SignImmE
+
<<2
PCPlus4D
CLR
CLR
EN
PCPlus4F
PCBranchD
RegWriteW
RegWriteM
MemtoRegE
RegWriteE
ForwardBE
ForwardAE
FlushE
ForwardBD
ForwardAD
BranchD
StallD
ResultW
StallF
0
1
PCSrcD
EqualD
CLK
ALU
CLK
CLK
Hazard Unit
MC542
4.52
Processador MIPS Pipelined
Control Forwarding e Stalling Hardware
• Lógica de Forwarding:
ForwardAD = (rsD !=0) AND (rsD == WriteRegM) AND RegWriteM
ForwardBD = (rtD !=0) AND (rtD == WriteRegM) AND RegWriteM
• Lógica de Stalling:
branchstall = BranchD AND RegWriteE AND (WriteRegE == rsD
OR WriteRegE == rtD) OR
BranchD AND MemtoRegM AND (WriteRegM == rsD
OR WriteRegM == rtD)
StallF = StallD = FlushE = lwstall OR branchstall
MC542
4.53
Processador MIPS Pipelined
Desempenho do MIPS Pipelined
Ideal: CPI = 1, IPC = 1
Porém devido aos stall (causados por loads e branches)
SPECINT2000 benchmark:
25% loads
10% stores
11% branches
2% jumps
52% R-type
Suponha que:
40% dos loads são usados pela próxima instrução
25% dos branches são mispredicted
Qual o CPI médio?
Average CPI = (0.25)(1.4) + (0.1)(1) + (0.11)(1.25) + (0.02)(2) +
(0.52)(1) = 1.15
MC542
4.54
Processador MIPS Pipelined
Desempenho do MIPS Pipelined
• Pipelined processor critical path:
Tc
= max {
tpcq + tmem + tsetup
2(tRFread + tmux + teq + tAND + tmux + tsetup )
tpcq + tmux + tmux + tALU + tsetup
tpcq + tmemwrite + tsetup
2(tpcq + tmux + tRFwrite) }
MC542
4.55
Processador MIPS Pipelined
Exemplo de Desempenho
Element
Parameter
Delay (ps)
Register clock-to-Q
tpcq_PC
30
Register setup
tsetup
20
Multiplexer
tmux
25
ALU
tALU
200
Memory read
tmem
250
Register file read
tRFread
150
Register file setup
tRFsetup
20
Equality comparator
teq
40
AND gate
tAND
15
Memory write
Tmemwrite
220
Register file write
tRFwrite
100 ps
Tc = 2(tRFread + tmux + teq + tAND + tmux + tsetup )
= 2[150 + 25 + 40 + 15 + 25 + 20] ps = 550 ps
MC542
4.56
Processador MIPS Pipelined
Exemplo de Desempenho
• Para um programa que executa 100 bilhões de instruções em um
processaddor MIPs pipelined,
• CPI = 1.15
• Tc = 550 ps
Execution Time = (# instructions) × CPI × Tc
= (100 × 109)(1.15)(550 × 10-12)
= 63 seconds
MC542
4.57
Processador MIPS Pipelined
Exemplo de Desempenho
Processor
Single-cycle
Multicycle
Pipelined
Execution Time
(seconds)
95
Speedup
(single-cycle is baseline)
1
133
0.71
63
1.51
MC542
4.58