Pipelining - Organização e Arquitetura de Computadores

Prévia do material em texto

Universidade de BrasUniversidade de Brasíílialia
Pipelining
OrganizaOrganizaçãção e Arquitetura deo e Arquitetura de
ComputadoresComputadores
Objetivo
n Apresentar a utilização de uma técnica
para aumento de desempenho de
arquiteturas de processadores:
n Pipeline :
n O que facilita o pipeline:
n Todas instruções têm o mesmo comprimento.
n Poucos formatos de instruções.
n Operandos em memória só aparecem em loads e
stores.
Objetivo
n Pipeline :
n O que complica (hazards):
n Propriedades estruturais: memória única, p.ex..
n Controle de fluxo: instruções de desvio.
n Dependências (de dados): uma instrução
depende do resultado de outra anterior.
Montagem de uma Bicicleta
tempo
1 2 3 4 5
 uma pessoa leva 5 unidades de tempo para montar uma bicicleta
Linha de Montagem (pipeline)
tempo/ espaço
1 2 3 4 5
Linha de Montagem (pipeline)
tempo/ espaço
1 2 3 4 5
Linha de Montagem (pipeline)
n A latência do pipeline é o tempo que uma
bicicleta leva para ser montada
n Neste exemplo, a latência é 5 unidades de tempo
n A taxa de produção (ou vazão) do pipeline é de
uma bicicleta por unidade de tempo
n O pipeline só começa a produzir nessa taxa uma
vez que linha esteja cheia
n Primeira bicicleta produzida em 5 UT
n Após a primeira, o pipe produz uma bicicleta por
UT
Balanceamento do Pipeline
n Suponha que a operação Montagem da Roda
Trazeira requeira duas unidades de tempo
n Uma unidade para montar a correia
n Uma unidade para montar a roda
n O que ocorre com a latência do pipeline ?
n O que ocorre com a vazão ?
n Como otimizar o pipeline neste caso ?
Balanceamento do Pipeline
n O pipeline não funciona se as tarefas não requerem o
mesmo tempo
n Se uma tarefa leva 2 UT, todas tem que trabalhar
neste período
n Latência do pipeline seria 10 UT
n Vazão seria uma bicicleta / 2 UT
n Dividindo a tarefa em duas subtarefas de 1 UT cada,
teríamos:
n Latência de 6 UT
n Vazão de 1 Bici / UT
Pipelining em Hardware
n Pipelining é uma técnica de projeto onde o
hardware processa mais de uma instrução
de cada vez sem esperar que uma
instrução termine antes de começar a
próxima.
Pipelining
n Numa máquina sem pipeline os quatro
estágios básicos de uma instrução
compreendem:
n busca
n decodificação
n execução
n atualização
Pipelining
n Os mesmos estágios existem numa
máquina com pipeline, porém são
executados em paralelo: assim que um
estágio termina, passa o resultado para o
próximo e começa a trabalhar a próxima
instrução.
Pipelining
n Num projeto de pipeline RISC típico, cada
instrução toma um ciclo de clock para cada
estágio de modo que o processador pode
aceitar uma nova instrução a cada ciclo de
clock.
Pipelining
n O pipeline não alivia o tempo de latência
das instruções. Cada instrução continua
necessitando da mesma quantidade de
tempo para ser terminada.
n O pipeline melhora o throughput global.
Contém somente:
• instruções de referência à memória: lw,sw
• instruções aritméticas/lógicas: add,sub,and,or,slt
• instruções de controle de fluxo: beq,j
Exemplo: arquitetura MIPS
 Jumpdresstarget adopFormato J
 Transferência, desvios, imediatoiatess/immedaddrertrsopFormato I
 Instruções aritméticasfunctshamtrdrtrsopFormato R
 Todas instruções têm 32 bits6 bits5 bits5 bits5 bits5 bits6 bitsTamanho
ComentáriosposCamNome
MIPS Uniciclo
A
L
UPCPC Endereço Instrução
Memória de
instruções
Dados
Registro #
Registro #
Registro #
Registros
Endereços
Dados
Memória
de dados
Busca de Instruções
PCPC Endereço Instrução
Memória de
instruções
A
d
d
4
Instruções do Tipo-R
ALU
WriteData
ReadReg1
ReadReg2
WriteReg
Registros
Instrução
Read
data1
Read
data2
Zero
result
RegWrite
3 Operação da UAL
Instruções load e store
ALU
WriteData
ReadReg1
ReadReg2
WriteReg
Registros
Instrução
Read
data1
Read
data2
Zero
result
RegWrite
3 Operação da UAL
Endereços
Write
Data
Memória
de dados
Extensão
de sinal
Extensão
de sinal
16 32
MemWrite
MemRead
Read
data
Instruções de desvio
ALU
WriteData
ReadReg1
ReadReg2
WriteReg
Registros
Instrução
Read
data1
Read
data2
Zero
RegWrite
3 Operação da UAL
Extensão
de sinal
Extensão
de sinal
16 32
Add
Shift
left 2
Shift
left 2
branch control logic
endereço de desvio
PC + 4
Juntando as partes
ALU
WriteData
ReadReg1
ReadReg2
WriteReg
Registros
Read
data1
Read
data2
Zero
RegWrite
3 Operação da UAL
Extensão
de sinal
Extensão
de sinal
16 32
Add
Shift
left 2
Shift
left 2
PC
PC
Endereço
Instrução
Memória de
instruções
A
d
d
4
Endereços
Write
Data
Memória de
dados
MemWrite
MemRead
Read
dataM
U
X
M
U
X
M
U
X
M
U
X
M
U
X
M
U
X
PCSrc
ALUSrc
MemtoReg
Controle
Controle
Branch
M
U
X
M
U
X
ALU
WriteData
ReadReg1
ReadReg2
WriteReg
Registros
Read
data1
Read
data2
Zero
RegWrite
Extensão
de sinal
Extensão
de sinal
16 32
Add
PC
PC Endereço
Instrução
Memória de
instruções
A
d
d
4
Endereços
Write
Data
Memória de
dados
MemWrite
MemRead
Read
dataM
U
X
M
U
X M
U
X
M
U
X
M
U
X
M
U
X
PCSrc
ALUSrc
MemtoReg
ALU
control
ALU
control
ALUOp
RegDst
[15 - 0]
[15 - 11]
[20 - 16]
[25 - 21]
[31 - 26]
[31 - 0]
Incluindo controle
[5 - 0]
Shift
left 2
Shift
left 2
MIPS: Projetado para Pipeline
n Todas instruções de mesmo comprimento.
n Busca no primeiro estágio, execução no segundo.
No 80x86 instruções de 1 a 17 bytes.
n Poucos formatos de instruções, com o campo do
registro de origem na mesma posição em todas
instruções.
n O segundo estágio pode ler o registro ao mesmo
tempo que decodifica a instrução.
MIPS: Projetado para Pipeline
n Operandos na memória só aparecem nas instruções
load e store. O estágio de execução pode ser
utilizado para calcular um endereço de memória, para
ser acessado no próximo estágio.
n Operandos alinhados na memória. Facilita
transferência de dados que ocupam mais de um
endereço.
Pipeline na arquitetura MIPS
n As instruções do processador MIPS necessitam
cinco etapas:
1. Busca instrução na memória
2. Lê registros e decodifica instrução
3. Executa operação ou calcula endereço
4. Acessa operando na memória (de dados)
5. Escreve o resultado num registro
n Pode ser utilizado um pipeline de cinco
estágios
Classe de instrução Busca de 
instrução 
Leitura 
registro 
Operação 
da ULA 
Acesso a 
dado 
Escrita 
registro 
Tempo 
total 
Load word (lw) 2 ns 1 ns 2 ns 2 ns 1 ns 8 ns 
Store word (sw) 2 ns 1 ns 2 ns 2 ns 7 ns 
R-format (add, sub, and, or, slt) 2 ns 1 ns 2 ns 1 ns 6 ns 
Branch (beq) 2 ns 1 ns 2 ns 5 ns 
Jump (j) 2 ns 2 ns 
 
Tempo de execução das
Instruções
24% loads
12% stores
44% tipo R
18% branches
2% jumps
Ciclomédio = 8x24% + 7x12% + 6x44% + 5x18% + 2x2% = 6.3 ns
Desempenho = 8/6.3 = 1.27
Execução sem pipeline
Busca de
instrução RegUAL
Acesso
a dadosReglw $1, 100($0)
lw $2, 200($0)
lw $3, 300($0)
Busca de
instrução RegUAL
Acesso
a dadosReg
Busca de
instrução
Tempo
 2 4 6 8 10 12 14 16 18
8 ns
8 ns
8 ns
...
Execução com pipeline
Tempo
 2 4 6 8 10 12 14
Busca de
instrução
RegUAL Acesso
a dados
Reglw $1, 100($0)
lw $2, 200($0)
lw $3, 300($0)
Busca de
instrução
RegUAL Acesso
a dados
Reg
Busca de
instrução
2 ns 2 ns 2 ns
RegUAL Acesso
a dados
Reg
2 ns 2 ns 2 ns 2 ns
.
.
.
Melhora o desempenho com o aumento do
throughput de instruções.
Controle do pipeline
n Temos 5 estágios. O que deve ser controlado
em cada estágio?
n IF: Instruction Fetch e PC Increment
n ID: Instruction Decode / Register Fetch
n EX: Execution
n MEM: Memory Stage
n WB: Write Back
Idéia básica. Fluxo de dados
Instruction
memory
Address
4
32
0
Add Addresult
Shift
left 2
Instruction
M
u
x
0
1
Add
PC
0
Write
data
M
u
x
1
Registers
Read
data 1
Read
data 2
Read
register 1
Read
register 2
16
Sign
extend
Write
register
Write
data
ReaddataAddress
Data
memory
1
ALU
result
M
u
x
ALU
Zero
IF: Instruction Fetch ID: Instruction decode /
register file read
EX: Execute /
Address Calculation
MEM: Memory 
Access
WB: Write Back
Fluxo de dados e registros
pipeline
Instruction
memory
Address
4
32
0
Add Addresult
Shift
left 2
In
st
ru
ct
io
n
IF/ID EX/MEM MEM/WB
M
u
x
0
1
Add
PC
0
Write
data
M
u
x
1
Registers
Read
data 1
Read
data 2
Read
register 1
Read
register 2
16
Sign
extend
Write
register
Write
data
Read
data
1
ALU
result
M
u
x
ALU
Zero
ID/EX
Data
memory
Address
Busca de instrução
Instruction
memory
Address
4
32
0
Add Addresult
Shift
left 2
In
st
ru
ct
io
n
IF/ID EX/MEM MEM/WB
M
u
x
0
1
Add
PC
0
Write
data
M
u
x
1
Registers
Read
data 1
Read
data 2
Read
register 1
Read
register 2
16
Sign
extend
Write
register
Write
data
Read
data
1
ALU
result
M
u
x
ALU
Zero
ID/EX
Data
memory
Address
Decodificação/leitura de registros
Instruction
memory
Address
4
32
0
Add Addresult
Shift
left 2
In
st
ru
ct
io
n
IF/ID EX/MEM MEM/WB
M
u
x
0
1
Add
PC
0
Write
data
M
u
x
1
Registers
Read
data 1
Read
data 2
Read
register 1
Read
register 2
16
Sign
extend
Write
register
Write
data
Read
data
1
ALU
result
M
u
x
ALU
Zero
ID/EX
Data
memory
Address
Execução/cálculo de endereço
Instruction
memory
Address
4
32
0
Add Addresult
Shift
left 2
In
st
ru
ct
io
n
IF/ID EX/MEM MEM/WB
M
u
x
0
1
Add
PC
0
Write
data
M
u
x
1
Registers
Read
data 1
Read
data 2
Read
register 1
Read
register 2
16
Sign
extend
Write
register
Write
data
Read
data
1
ALU
result
M
u
x
ALU
Zero
ID/EX
Data
memory
Address
Acesso à memória
Instruction
memory
Address
4
32
0
Add Addresult
Shift
left 2
In
st
ru
ct
io
n
IF/ID EX/MEM MEM/WB
M
u
x
0
1
Add
PC
0
Write
data
M
u
x
1
Registers
Read
data 1
Read
data 2
Read
register 1
Read
register 2
16
Sign
extend
Write
register
Write
data
Read
data
1
ALU
result
M
u
x
ALU
Zero
ID/EX
Data
memory
Address
Write back
Instruction
memory
Address
4
32
0
Add Addresult
Shift
left 2
In
st
ru
ct
io
n
IF/ID EX/MEM MEM/WB
M
u
x
0
1
Add
PC
0
Write
data
M
u
x
1
Registers
Read
data 1
Read
data 2
Read
register 1
Read
register 2
16
Sign
extend
Write
register
Write
data
Read
data
1
ALU
result
M
u
x
ALU
Zero
ID/EX
Data
memory
Address
Controle do Pipeline
PC
Instruction
memory
Address
In
s t
ru
ct
io
n
Instruction
[20– 16]
MemtoReg
ALUOp
Branch
RegDst
ALUSrc
4
16 32
Instruction
[15– 0]
0
0
Registers
Write
register
Write
data
Read
data 1
Read
data 2
Read
register 1
Read
register 2
Sign
extend
M
u
x
1
Write
data
Read
data M
u
x
1
ALU
control
RegWrite
MemRead
Instruction
[15– 11]
6
IF/ID ID/EX EX/MEM MEM/WB
MemWrite
Address
Data
memory
PCSrc
Zero
Add
Add
result
Shift
left 2
ALU
result
ALU
Zero
Add
0
1
M
u
x
0
1
M
u
x
Controle do pipeline
n Os registradores do pipeline não necessitam
sinais de controle, pois são carregados a
cada ciclo de clock
n Como deveria ser feito o controle numa
fábrica de automóveis?
n uma central imaginária dizendo a cada um o que deve ser
feito?
n deveríamos utilizar uma máquina de estados finitos?
Controle do Pipeline
n Sinais de controle são transmitidos da mesma forma que os dados
Execution/Address Calculation 
stage control lines
Memory access stage 
control lines
Write-back 
stage control 
lines
Instruction
Reg 
Dst
ALU 
Op1
ALU 
Op0
ALU 
Src Branch
Mem 
Read
Mem 
Write
Reg 
write
Mem to 
Reg
R-format 1 1 0 0 0 0 0 1 0
lw 0 0 0 1 0 1 0 1 1
sw X 0 0 1 0 0 1 0 X
beq X 0 1 0 1 0 0 0 X
Control
EX
M
WB
M
WB
WB
IF/ID ID/EX EX/MEM MEM/WB
Instruction
Fluxo de dados com controle
P C
In s tru c tio n
m e m ory
In
s
tr
u
c
ti o
n
Ad d
In st ru c tio n
[2 0– 1 6]
M
e
m
to
R
e
g
A L U O p
B r an ch
R e g D s t
A L U S rc
4
16 3 2
In st ru c tion
[1 5 – 0 ]
0
0
M
u
x
0
1
A dd
A d d
re su lt
R eg iste rs
W rite
re g is ter
W rite
d a ta
R ea d
d ata 1
R ea d
d ata 2
R e ad
re g is ter 1
R e ad
re g is ter 2
S ig n
ex ten d
M
u
x
1
A L U
re su l t
Z e ro
W rite
d a ta
R e a d
d ata
M
u
x
1
A LU
co n tr o l
S h ift
le ft 2
R
e
g
W
ri
t e
M e m R e ad
C o n tro l
A L U
In st ru ctio n
[1 5– 1 1]
6
E X
M
W B
M
W B
W B
IF /ID
P C S rc
ID /E X
E X /M E M
M E M /W B
M
u
x
0
1
M
e
m
W
rit
e
A dd re ss
D a ta
m e m o ry
A d d re ss
Simplificando
Reg
MD
RegMI
U
L
Aadd $s0, $t0, $t1
 IF ID EX MEM WB
Execução com pipeline
Reg MD RegMI
U
L
A
Reg
MD
RegMI
U
L
A
Reg
MD
RegMI
U
L
A
CC1 CC2 CC3 CC4 CC5 CC6 CC7
lw $1, 100($0)
lw $2, 200($0)
lw $3, 300($0)
Desempenho.
O que pode dar errado.
n Um processador com pipeline pode pausar
por várias razões, incluindo atrasos na
leitura da memória, conjunto de instruções
mal projetado, dependência entre
instruções, ...
Dependência de Dados
(Hazards)
Dependência de dados:
Instruções que seguem
sub utilizam o registrador
$2, cujo valor é
produzido pela instrução
sub
.
.
sub $2, $1, $3
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)
.
.
Dependência de Dados
Reg MD RegMI
U
L
A
Reg MD RegMI
U
L
A
Reg MD RegMI
U
L
A
Reg MD RegMI
U
L
A
Reg MD RegMI
U
L
A
 CC1 CC2 CC3 CC4 CC5 CC6 CC7 CC8 CC9
Valor do registro $2 10 10 10 10 10/-20 -20 -20 -20 -20
sub $2, $1, $3
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)
Solução por Software
n O compilador pode detectar a ocorrência de hazard
de dados e introduzir NOPs (no operation) ou re-
escalonar as instruções
sub $2, $1, $3
nop
nop
nop
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)
Escalonamento de Instruções
n Um rearranjo das instruções no programa, chamado
escalonamento de instruções, pode resolver esta pendência.
...
ld r2, I
add r2, r2, #123
st r2, I
ld r3, J
sub r3, r3, #567
st r3, J ...
...
ld r2, I
ld r3, J
add r2, r2, #123
sub r3, r3, #567 
st r2, I
st r3, J...
Hardware: Congelar o pipe
(stall ou bolha)
n A unidade de controle do processador pode detectar a
ocorrência de conflitos e congelar execução de novas
instruções até que o conflito seja resolvido
n O congelamento pode ser feito colocando-se em zero os
sinais de controle que acompanham os dados no pipeline
0
WB
M
EX
Control M
u
x
Introdução de bolhas
n As bolhas interrompem a execução dos estágios
sub $s0, $t1, $t2
bolhas
add $t2, $s0, $t3
Tempo
Reg
MD
RegMI
U
L
A
Reg
MD
RegMI
U
L
A
 2 4 6 8 10 14
Deteção de Conflitos
n Comparar índices dos registradores a serem lidos
e escritos, armazenados nos registradores do
pipeline:
n IF/ID.ReadRegister1 # registradores a serem
n IF/ID.ReadRegister2 # lidos
n ID/EX.WriteRegister
n EX/MEM.WriteRegister
n MEM/WB.WriteRegister
n Deve-se comparar igualmente se a instrução
escreve em um registrador (RegWrite = 1)
Unidade de Deteção de Hazard
M
U
X
Hazard 
Detection 
Unit
Control
WB
M
EX
Registers
PC
Instruction
Memory
0
Data
Memory M
U
X
WB
WB
M
M
U
X
Deteção de Conflitos
n EX hazard:
ID/EX.RegWrite and
((ID/EX.RegDst = 0 and
ID/EX.WriteRegisterRt=IF/ID.ReadRegister1) or
(ID/EX.RegDst = 1 and
ID/EX.WriteRegisterRd=IF/ID.ReadRegister1) or
(ID/EX.RegDst = 0 and
ID/EX.WriteRegisterRt=IF/ID.ReadRegister2) or
(ID/EX.RegDst = 1 and
ID/EX.WriteRegisterRd=IF/ID.ReadRegister2))
n MEM hazard:
EX/MEM.RegWrite and
((EX/MEM.WriteRegister = IF/ID.ReadRegister1) or
(EX/MEM.WriteRegister = IF/ID.ReadRegister2))
Introdução de Bolhas
R
eg
M
D R eg
M
I
R
e g
M
D Reg
M
I
R
e g
M
D Re g
M
I
R
e g
M
D Re g
M
I
R
eg
M
D Reg
M
I
sub $2, $1, $3
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15,100($2)
• As bolhas atrasam a execução das instruções seguintes 
Exemplo
n Considere a seguinte sequência:
sub $2, $1, $3
and $4, $2, $5
or $8, $2, $6
add $9, $4, $2
slt $1, $6, $7
n Quantos conflitos existem e quantas bolhas são
geradas ?
Terceiro Ciclo
M
U
X
Hazard 
Detection 
Unit
Control
WB
M
EX
Registers
PC
Instruction
Memory
0
Data
Memory M
U
X
WB
WB
M
M
U
X
or $8, $2, $6 and $4, $2, $5 sub $2, $1, $3
2
ID/EX.RegWrite
0
0
0
Quinto Ciclo
M
U
X
Hazard 
Detection 
Unit
Control
WB
M
EX
Registers
PC
Instruction
Memory
0
Data
Memory M
U
X
WB
WB
M
M
U
X
and $4, $2, $5 bolha bolha sub $2, $1, $3
MEM/WB.RegWrite
0
0
0
2
Stall
n Como toda a arquitetura permanece
ociosa durante as pausas, tanto os
projetistas quanto os programadores de
sistemas RISC fazem um esforço
consciente para evitá-las
Data Hazard: Adiantamento de
Dados (Forwarding)
Reg
MD
RegMI
U
L
A
Reg
MD
RegMI
U
L
A
add $s0, $t1, $t1
sub $t2, $s0, $t3
Tempo
 2 4 6 8 10
Adiantamento de Dados.
Tempo (em ciclos)
CC 1
10 10 10 10 10/– 20 – 20 – 20 – 20 – 20
X X X – 20 X X X X XValor de EX/MEM:
X X X X – 20 X X X X
IM Reg
IM Reg
sub $2, $1, $3
and $12, $2, $5
IM Reg DM Reg
IM DM Reg
IM DM Reg
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)
DM Reg
Reg
Reg
Reg
DM
Valor do registro $2:
Valor de MEM/WB:
CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9
Forwarding: Controle
PC
Instruction
memory
Registers
M
u
x
M
u
x
Control
ALU
EX
M
M WB
ID/EX
EX/MEM
MEM/WB
Data
memory
M
u
x
Forwarding
unit
IF/ID
In
st
ru
ct
io
n
M
u
x
Rd
EX/MEM.RegisterRdRt
Rt
RsIF/ID.RegisterRs
WB
WB
MEM/WB.RegisterRd
IF/ID.RegisterRt
IF/ID.RegisterRt
IF/ID.RegisterRd
Exemplo
n Considere a mesma sequência:
sub $2, $1, $3
and $4, $2, $5
or $8, $2, $6
add $9, $4, $2
slt $1, $6, $7
n Como fica com adiantamento de dados ?
Terceiro Ciclo
PC
Instruction
memory
Registers
M
u
x
M
u
x
Control
ALU
EX
M
M WB
ID/EX
EX/MEM
MEM/WB
Data
memory
M
u
x
Forwarding
unit
IF/ID
In
st
ru
ct
io
n
M
u
x
2
EX/MEM.RegisterRd
3
1IF/ID.RegisterRs
WB
WB
MEM/WB.RegisterRd
IF/ID.RegisterRt
IF/ID.RegisterRt
IF/ID.RegisterRd
sub $2, $1, $3and $4, $2, $5or $8, $2, $6
$1
$3
2
5
4
Quarto Ciclo
PC
Instruction
memory
Registers
M
u
x
M
u
x
Control
ALU
EX
M
M WB
ID/EX
EX/MEM
MEM/WB
Data
memory
M
u
x
Forwarding
unit
IF/ID
In
st
ru
ct
io
n
M
u
x
4
EX/MEM.RegisterRd
5
2IF/ID.RegisterRs
WB
WB
MEM/WB.RegisterRd
IF/ID.RegisterRt
IF/ID.RegisterRt
IF/ID.RegisterRd
sub $2, $1, $3and $4, $2, $5or $8, $2, $6
$2
$5
2
6
8
add $9, $4, $2
2
$2
Quinto Ciclo
PC
Instruction
memory
Registers
M
u
x
M
u
x
Control
ALU
EX
M
M WB
ID/EX
EX/MEM
MEM/WB
Data
memory
M
u
x
Forwarding
unit
IF/ID
In
st
ru
ct
io
n
M
u
x
8
EX/MEM.RegisterRd
6
2IF/ID.RegisterRs
WB
WB
MEM/WB.RegisterRd
IF/ID.RegisterRt
IF/ID.RegisterRt
IF/ID.RegisterRd
sub $2, $1, $3and $4, $2, $5or $8, $2, $6
$2
$6
4
2
9
add $9, $4, $2
4
slt $1, $6, $7
2
Sexto Ciclo
PC
Instruction
memory
Registers
M
u
x
M
u
x
Control
ALU
EX
M
M WB
ID/EX
EX/MEM
MEM/WB
Data
memory
M
u
x
Forwarding
unit
IF/ID
In
st
ru
ct
io
n
M
u
x
9
EX/MEM.RegisterRd
2
4IF/ID.RegisterRs
WB
WB
MEM/WB.RegisterRd
IF/ID.RegisterRt
IF/ID.RegisterRt
IF/ID.RegisterRd
and $4, $2, $5or $8, $2, $6
$4
$2
6
7
1
add $9, $4, $2
8
slt $1, $6, $7
4
Conflitos no Adiantamento
n Load word pode causar um atraso:
n Uma instrução tenta ler um registro após um load que
escreve no mesmo registro.
n É preciso uma unidade de detecção de hazard para
atrasar a instrução pós load.
Conflitos no Adiantamento
Reg
IM
Reg
Reg
IM DM
IM Reg DM RegIM
IM DM Reg
IM DM Reg
DM Reg
RegReg
Reg
bubble
CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9
Tempo (ciclos)
CC 10
lw $2 20($1)
and $4, $2, $5
or $8, $2, $6
add $9, $4, $2
slt $1, $6, $7
Hazard detection unit
PC
M
u
x
M
u
x
M
u
x
Control
ALU
EX
M
WB
M
WB
WB
ID/EX
EX/MEM
MEM/WB
M
u
x
Hazard
detection
unit
Forwarding
unit
0
M
u
x
IF/ID
ID/EX.MemRead
IF
/ID
W
rit
e
P
C
W
rit
e
ID/EX.RegisterRt
Rt
Rs
Rd
Rt
IF/ID.RegisterRs
IF/ID.RegisterRt
IF/ID.RegisterRt
IF/ID.RegisterRd
EX/MEM.RegisterRd
MEM/WB.RegisterRd
Instruction
memory
Registers
Data
memory
In
st
ru
ct
io
n
Branch hazards
n Quando é decidido um desvio, outras instruções estão no pipeline.
Reg
Reg
40 beq $1, $3, $7 IM Reg
IM DM
IM DM
IM DM
DM
DM Reg
Reg Reg
Reg
Reg
RegIM
44 and $12, $2, $5
48 or $13, $6, $2
52 add $14, $2, $2
72 lw $4, 50($7)
Reg
Tempo (em ciclos)
CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9
Opção: Congelar Pipe
add $4, $5, $6
beq $1, $2, 40
lw $3, 300($0)
2 ns 6 ns 2 ns
Busca de
instrução RegUAL
Acesso
a dadosReg
Busca de
instrução RegUAL
Acesso
a dadosReg
Busca de
instrução RegUAL
Acesso
a dados
Reg
2 ns 2 ns 2 ns 2 ns
...
n Uma opção é sempre congelar o pipeline quando se encontra uma
instrução de salto condicional, esperando o resultado da comparação
n Problema: piora o desempenho do pipeline
Previsão de Salto
n Uma melhor alternativa é fazer uma
previsão de salto
n Caso a previsão esteja correta, não há
perda no pipeline
n Caso a previsão esteja incorreta, as
instrução seguintes ao salto devem ser
descartadas (descarga do pipeline)
Técnicas de Previsão de Desvio
n desvio nunca será realizado
n desvio sempre será realizado
n desvio depedente do código da operação
n desvio dependente do histórico da instrução
n implementado com o auxílio de uma tabela de histórico
de desvios
n armazena endereço da instrução, endereço do desvio
e estado
Outras Técnicas
n múltiplos fluxos
n ambas alternativas são executadas simultaneamente
n busca antecipada de instruções
n pré-carga das instruções no end. de desvio
n memória de laço de repetição (loop buffer)
n armazena internamente as instruções executadas mais
recentemente
n atraso de desvio (delayed branch)
n permitir a execução de algumas instruções
imediatamente após a instrução de desvio
n implica no reordenamento de instruções
q Processador sempre executa instrução seguinte
q Compilador deve reordenar as instruções ou inserir nop
Tempo
 2 4 6 8 10 12 14
Busca de
instrução RegUAL
Acesso
a dadosRegbeq $1, $2, 40
add $4, $5, $6
lw $3, 300($0)
Busca de
instrução RegUAL
Acesso
a dadosReg
Busca de
instrução
2 ns 2 ns 2 ns
RegUAL Acessoa dadosReg
2 ns 2 ns 2 ns 2 ns
...
(Delayed branch slot )
Atraso de Desvio
Descarga do Pipeline
PC
Instruction
memory
4
Registers
M
u
x
M
u
x
M
u
x
ALU
EX
M
WB
M
WB
WB
ID/EX
0
EX/MEM
MEM/WB
Data
memory
M
u
x
Hazard
detection
unit
Forwarding
unit
IF.Flush
IF/ID
Sign
extend
Control
M
u
x
=
Shift
left 2
M
u
x
q A velocidade máxima de uma máquina com pipeline
é de uma instrução por ciclo de clock.
Acelerando máquinas com
pipeline
 IF ID EX MEM WB
 IF ID EX MEM WB
 IF ID EX MEM WB
 IF ID EX MEM WB
 IF ID EX MEM WB
 IF ID EX MEM WB
 IF ID EX MEM WB
 IF ID EX MEM WB
 CC1 CC2 CC3 CC4 CC5 CC6 CC7 CC8 CC9 CC10 CC11 CC12
q Duas técnicas para iniciar múltiplas
instruções por ciclo de clock:
q arquiteturas superpipeline
q arquiteturas superescalares.
Acelerando máquinas
com pipeline
q A arquitetura Superpipeline subdivide cada
estágio do pipeline em subestágios e multiplica o
clock internamente.
q Cada (sub)estágio continua executando uma
instrução por clock.Mas como o clock interno é
multiplicado, o pipeline pode aceitar duas ou mais
instruções para cada clock externo.
Acelerando máquinas com
pipeline: o superpipeline
Superpipeline
 CC1 CC2 CC3 CC4 CC5 CC6 CC7 CC8
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
q A arquitetura superescalar contém
múltiplas unidades de execução que são
capazes de fazer a mesma coisa.
q Isto permite ao processador executar
várias instruções similares
concorrentemente, pelo roteamento das
instruções às unidades de execução
disponíveis.
Acelerando máquinas com
pipeline: a superescalar
Pipeline superescalar
 CC1 CC2 CC3 CC4 CC5 CC6 CC7 CC8
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
Superpipeline superescalar
 CC1 CC2 CC3 CC4 CC5 CC6 CC7 CC8
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
Execução dinâmica:
escalonamento.
n O hardware executa o escalonamento
n O hardware tenta encontrar instruções para executar
n É possível a execução de instruções for a de ordem
n Execução especulativa e predição dinâmica de desvios.
n Todos processadores modernos são bastante complicados
n Compaq/DEC Alpha 21264: 9 estágios de pipeline, 6 instruction issue
n PowerPC e Pentium: tabela de histórico de desvios
n O papel do compilador é muito importante.
n Este curso serve de base para avançar no assunto.
n Overview of Intel’s Pentium Processors: http://www.intel.com
Referências
Patterson, D. A., Hennessy, J. L., (1998)
Computer Organization and Design: The
Hardware/Software Interface. Morgan Kaufmann.
http:/www.mkp.com/cod2e.htm/
Leitura recomendada
n Tanenbaum, A.S., (1990) Organização
estruturada de computadores. Cap 4.
n 4.5 {4.5.4}