Embed Size (px)
Citation preview
Universidade de BrasUniversidade de Brasíílialia
PipeliningOrganizaOrganizaçãção e Arquitetura deo e Arquitetura de
ComputadoresComputadores
Objetivo
n Apresentar a utilização de uma técnicapara aumento de desempenho dearquiteturas 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 estores.
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çãodepende 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 umabicicleta 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 é deuma bicicleta por unidade de tempo
n O pipeline só começa a produzir nessa taxa umavez que linha esteja cheia
n Primeira bicicleta produzida em 5 UTn Após a primeira, o pipe produz uma bicicleta por
UT
Balanceamento do Pipeline
n Suponha que a operação Montagem da RodaTrazeira 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 Pipelinen O pipeline não funciona se as tarefas não requerem o
mesmo tempon Se uma tarefa leva 2 UT, todas tem que trabalhar
neste períodon Latência do pipeline seria 10 UTn 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 UTn Vazão de 1 Bici / UT
Pipelining em Hardware
n Pipelining é uma técnica de projeto onde ohardware processa mais de uma instruçãode cada vez sem esperar que umainstrução termine antes de começar apróxima.
Pipelining
n Numa máquina sem pipeline os quatroestágios básicos de uma instruçãocompreendem:
n busca
n decodificação
n execução
n atualização
Pipelining
n Os mesmos estágios existem numamáquina com pipeline, porém sãoexecutados em paralelo: assim que umestágio termina, passa o resultado para opróximo e começa a trabalhar a próximainstrução.
Pipelining
n Num projeto de pipeline RISC típico, cadainstrução toma um ciclo de clock para cadaestágio de modo que o processador podeaceitar uma nova instrução a cada ciclo declock.
Pipelining
n O pipeline não alivia o tempo de latênciadas instruções. Cada instrução continuanecessitando da mesma quantidade detempo 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
AL
UPCPC Endereço Instrução
Memória deinstruções
Dados
Registro #
Registro #
Registro #
Registros
Endereços
Dados
Memóriade dados
Busca de Instruções
PCPC Endereço Instrução
Memória deinstruções
Ad
d
4
Instruções do Tipo-R
ALU
WriteData
ReadReg1
ReadReg2
WriteReg
Registros
Instrução
Readdata1
Readdata2
Zero
result
RegWrite
3 Operação da UAL
Instruções load e store
ALU
WriteData
ReadReg1
ReadReg2
WriteReg
Registros
Instrução
Readdata1
Readdata2
Zero
result
RegWrite
3 Operação da UAL
Endereços
WriteData
Memóriade dados
Extensãode sinal
Extensãode sinal
16 32
MemWrite
MemRead
Readdata
Instruções de desvio
ALU
WriteData
ReadReg1
ReadReg2
WriteReg
Registros
InstruçãoReaddata1
Readdata2
Zero
RegWrite
3 Operação da UAL
Extensãode sinal
Extensãode sinal
16 32
Add
Shiftleft 2
Shiftleft 2
branch control logic
endereço de desvio
PC + 4
Juntando as partes
ALU
WriteData
ReadReg1
ReadReg2
WriteReg
Registros
Readdata1
Readdata2
Zero
RegWrite
3 Operação da UAL
Extensãode sinal
Extensãode sinal
16 32
Add
Shiftleft 2
Shiftleft 2
PCPC
EndereçoInstrução
Memória deinstruções
Ad
d
4
Endereços
WriteData
Memória dedados
MemWrite
MemRead
ReaddataM
UX
MUX
MUX
MUX
MUX
MUX
PCSrc
ALUSrc
MemtoReg
ControleControle
Branch
MUX
MUX
ALU
WriteData
ReadReg1
ReadReg2
WriteReg
Registros
Readdata1
Readdata2
Zero
RegWrite
Extensãode sinal
Extensãode sinal
16 32
Add
PCPC Endereço
Instrução
Memória deinstruções
Ad
d
4
Endereços
WriteData
Memória dedados
MemWrite
MemRead
ReaddataM
UX
MUX M
UX
MUX
MUX
MUX
PCSrcALUSrc
MemtoReg
ALUcontrol
ALUcontrol
ALUOp
RegDst
[15 - 0]
[15 - 11]
[20 - 16]
[25 - 21]
[31 - 26]
[31 - 0]
Incluindo controle
[5 - 0]
Shiftleft 2
Shiftleft 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 todasinstruções.
n O segundo estágio pode ler o registro ao mesmotempo que decodifica a instrução.
MIPS: Projetado para Pipeline
n Operandos na memória só aparecem nas instruçõesload e store. O estágio de execução pode serutilizado para calcular um endereço de memória, paraser acessado no próximo estágio.
n Operandos alinhados na memória. Facilitatransferência de dados que ocupam mais de umendereço.
Pipeline na arquitetura MIPS
n As instruções do processador MIPS necessitamcinco etapas:
1. Busca instrução na memória2. Lê registros e decodifica instrução3. Executa operação ou calcula endereço4. Acessa operando na memória (de dados)5. Escreve o resultado num registron 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 dasInstruçõ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 deinstrução RegUAL Acesso
a dadosReglw $1, 100($0)
lw $2, 200($0)
lw $3, 300($0)
Busca deinstrução RegUAL Acesso
a dadosReg
Busca deinstruçã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 deinstrução
RegUAL Acessoa dados
Reglw $1, 100($0)
lw $2, 200($0)
lw $3, 300($0)
Busca deinstrução
RegUAL Acessoa dados
Reg
Busca deinstrução
2 ns 2 ns 2 ns
RegUAL Acessoa dados
Reg
2 ns 2 ns 2 ns 2 ns
.
.
.
Melhora o desempenho com o aumento dothroughput de instruções.
Controle do pipeline
n Temos 5 estágios. O que deve ser controladoem cada estágio?
n IF: Instruction Fetch e PC Incrementn ID: Instruction Decode / Register Fetchn EX: Executionn MEM: Memory Stagen WB: Write Back
Idéia básica. Fluxo de dados
Instructionmemory
Address
4
32
0
Add Addresult
Shiftleft 2
Instruction
Mux
0
1
Add
PC
0Writedata
Mux
1Registers
Readdata 1
Readdata 2
Readregister 1
Readregister 2
16Sign
extend
Writeregister
Writedata
ReaddataAddress
Datamemory
1
ALUresult
Mux
ALUZero
IF: Instruction Fetch ID: Instruction decode /register file read
EX: Execute /Address Calculation
MEM: Memory Access
WB: Write Back
Fluxo de dados e registrospipeline
Instructionmemory
Address
4
32
0
Add Addresult
Shiftleft 2
Inst
ruct
ion
IF/ID EX/MEM MEM/WB
Mux
0
1
Add
PC
0Writedata
Mux
1Registers
Readdata 1
Readdata 2
Readregister 1
Readregister 2
16Sign
extend
Writeregister
Writedata
Readdata
1
ALUresult
Mux
ALUZero
ID/EX
Datamemory
Address
Busca de instrução
Instructionmemory
Address
4
32
0
Add Addresult
Shiftleft 2
Inst
ruct
ion
IF/ID EX/MEM MEM/WB
Mux
0
1
Add
PC
0Writedata
Mux
1Registers
Readdata 1
Readdata 2
Readregister 1
Readregister 2
16Sign
extend
Writeregister
Writedata
Readdata
1
ALUresult
Mux
ALUZero
ID/EX
Datamemory
Address
Decodificação/leitura de registros
Instructionmemory
Address
4
32
0
Add Addresult
Shiftleft 2
Inst
ruct
ion
IF/ID EX/MEM MEM/WB
Mux
0
1
Add
PC
0Writedata
Mux
1Registers
Readdata 1
Readdata 2
Readregister 1
Readregister 2
16Sign
extend
Writeregister
Writedata
Readdata
1
ALUresult
Mux
ALUZero
ID/EX
Datamemory
Address
Execução/cálculo de endereço
Instructionmemory
Address
4
32
0
Add Addresult
Shiftleft 2
Inst
ruct
ion
IF/ID EX/MEM MEM/WB
Mux
0
1
Add
PC
0Writedata
Mux
1Registers
Readdata 1
Readdata 2
Readregister 1
Readregister 2
16Sign
extend
Writeregister
Writedata
Readdata
1
ALUresult
Mux
ALUZero
ID/EX
Datamemory
Address
Acesso à memória
Instructionmemory
Address
4
32
0
Add Addresult
Shiftleft 2
Inst
ruct
ion
IF/ID EX/MEM MEM/WB
Mux
0
1
Add
PC
0Writedata
Mux
1Registers
Readdata 1
Readdata 2
Readregister 1
Readregister 2
16Sign
extend
Writeregister
Writedata
Readdata
1
ALUresult
Mux
ALUZero
ID/EX
Datamemory
Address
Write back
Instructionmemory
Address
4
32
0
Add Addresult
Shiftleft 2
Inst
ruct
ion
IF/ID EX/MEM MEM/WB
Mux
0
1
Add
PC
0Writedata
Mux
1Registers
Readdata 1
Readdata 2
Readregister 1
Readregister 2
16Sign
extend
Writeregister
Writedata
Readdata
1
ALUresult
Mux
ALUZero
ID/EX
Datamemory
Address
Controle do Pipeline
PC
Instructionmemory
Address
Ins t
ruct
ion
Instruction[20– 16]
MemtoReg
ALUOp
Branch
RegDst
ALUSrc
4
16 32Instruction[15– 0]
0
0Registers
Writeregister
Writedata
Readdata 1
Readdata 2
Readregister 1
Readregister 2
Signextend
Mux
1Write
data
Read
data Mux
1
ALUcontrol
RegWrite
MemRead
Instruction[15– 11]
6
IF/ID ID/EX EX/MEM MEM/WB
MemWrite
Address
Datamemory
PCSrc
Zero
AddAdd
result
Shiftleft 2
ALUresult
ALU
Zero
Add
0
1
Mux
0
1
Mux
Controle do pipeline
n Os registradores do pipeline não necessitamsinais de controle, pois são carregados acada ciclo de clock
n Como deveria ser feito o controle numafábrica de automóveis?
n uma central imaginária dizendo a cada um o que deve serfeito?
n deveríamos utilizar uma máquina de estados finitos?
Controle do Pipelinen 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
InstructionReg 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 0lw 0 0 0 1 0 1 0 1 1sw X 0 0 1 0 0 1 0 Xbeq 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
Ins
tru
cti o
nAd d
In st ru c tio n[2 0– 1 6]
Me
mto
Re
g
A L U O p
B r an ch
R e g D s t
A L U S rc
4
16 3 2In st ru c tion[1 5 – 0 ]
0
0
Mux
0
1
A ddA d d
re su lt
R eg iste rsW ritere g is ter
W rited a ta
R ea dd ata 1
R ea dd ata 2
R e adre g is ter 1
R e adre g is ter 2
S ig nex ten d
Mux
1
A L Ure su l t
Z e ro
W rited a ta
R e a dd ata
Mux
1
A LUco n tr o l
S h ift
le ft 2
Re
gW
rit 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 BIF /ID
P C S rc
ID /E X
E X /M E M
M E M /W B
Mux
0
1
Me
mW
rite
A dd re ss
D a ta
m e m o ry
A d d re ss
Simplificando
RegMD
RegMI
UL
Aadd $s0, $t0, $t1
IF ID EX MEM WB
Execução com pipeline
Reg MD RegMI
UL
A
RegMD
RegMIU
LA
RegMD
RegMI
UL
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 pausarpor várias razões, incluindo atrasos naleitura da memória, conjunto de instruçõesmal projetado, dependência entreinstruções, ...
Dependência de Dados(Hazards)
Dependência de dados:Instruções que seguemsub utilizam o registrador$2, cujo valor éproduzido pela instruçãosub
.
.sub $2, $1, $3and $12, $2, $5or $13, $6, $2add $14, $2, $2sw $15, 100($2)
.
.
Dependência de Dados
Reg MD RegMI
UL
A
Reg MD RegMI
UL
A
Reg MD RegMI
UL
A
Reg MD RegMI
UL
A
Reg MD RegMI
UL
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 hazardde 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, chamadoescalonamento de instruções, pode resolver esta pendência.
...ld r2, Iadd r2, r2, #123st r2, Ild r3, Jsub r3, r3, #567st r3, J ...
...ld r2, Ild r3, Jadd r2, r2, #123sub r3, r3, #567 st r2, Ist r3, J...
Hardware: Congelar o pipe(stall ou bolha)
n A unidade de controle do processador pode detectar aocorrência de conflitos e congelar execução de novasinstruções até que o conflito seja resolvido
n O congelamento pode ser feito colocando-se em zero ossinais de controle que acompanham os dados no pipeline
0
WB
M
EX
Control Mux
Introdução de bolhasn As bolhas interrompem a execução dos estágios
sub $s0, $t1, $t2
bolhas
add $t2, $s0, $t3
Tempo
RegMD
RegMI
UL
A
RegMD
RegMI
UL
A
2 4 6 8 10 14
Deteção de Conflitos
n Comparar índices dos registradores a serem lidose escritos, armazenados nos registradores dopipeline:
n IF/ID.ReadRegister1 # registradores a seremn IF/ID.ReadRegister2 # lidosn ID/EX.WriteRegistern EX/MEM.WriteRegistern MEM/WB.WriteRegister
n Deve-se comparar igualmente se a instruçãoescreve em um registrador (RegWrite = 1)
Unidade de Deteção de Hazard
MU
X
Hazard Detection
Unit
Control
WB
M
EX
RegistersPC
InstructionMemory
0
DataMemory M
UX
WB
WB
M
MUX
Deteção de Conflitos
n EX hazard:ID/EX.RegWrite and((ID/EX.RegDst = 0 andID/EX.WriteRegisterRt=IF/ID.ReadRegister1) or
(ID/EX.RegDst = 1 andID/EX.WriteRegisterRd=IF/ID.ReadRegister1) or
(ID/EX.RegDst = 0 andID/EX.WriteRegisterRt=IF/ID.ReadRegister2) or
(ID/EX.RegDst = 1 andID/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
Reg
MD Reg
MI
Re g
MD Reg
MI
Re g
MD Re g
MI
Re g
MD Re g
MI
Reg
MD Reg
MI
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ãogeradas ?
Terceiro Ciclo
MU
X
Hazard Detection
Unit
Control
WB
M
EX
RegistersPC
InstructionMemory
0
DataMemory M
UX
WB
WB
M
MUX
or $8, $2, $6 and $4, $2, $5 sub $2, $1, $3
2
ID/EX.RegWrite0
0
0
Quinto Ciclo
MU
X
Hazard Detection
Unit
Control
WB
M
EX
RegistersPC
InstructionMemory
0
DataMemory M
UX
WB
WB
M
MUX
and $4, $2, $5 bolha bolha sub $2, $1, $3MEM/WB.RegWrite
0
0
0
2
Stall
n Como toda a arquitetura permaneceociosa durante as pausas, tanto osprojetistas quanto os programadores desistemas RISC fazem um esforçoconsciente para evitá-las
Data Hazard: Adiantamento deDados (Forwarding)
RegMD
RegMI
UL
A
RegMD
RegMI
UL
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 – 20X 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
PCInstruction
memory
Registers
Mux
Mux
Control
ALU
EX
M
M WB
ID/EX
EX/MEM
MEM/WB
Datamemory
Mux
Forwardingunit
IF/ID
Inst
ruct
ion
Mux
RdEX/MEM.RegisterRdRt
Rt
RsIF/ID.RegisterRs
WB
WB
MEM/WB.RegisterRd
IF/ID.RegisterRtIF/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
PCInstruction
memory
Registers
Mux
Mux
Control
ALU
EX
M
M WB
ID/EX
EX/MEM
MEM/WB
Datamemory
Mux
Forwardingunit
IF/ID
Inst
ruct
ion
Mux
2EX/MEM.RegisterRd
3
1IF/ID.RegisterRs
WB
WB
MEM/WB.RegisterRd
IF/ID.RegisterRtIF/ID.RegisterRt
IF/ID.RegisterRd
sub $2, $1, $3and $4, $2, $5or $8, $2, $6
$1
$3
25
4
Quarto Ciclo
PCInstruction
memory
Registers
Mux
Mux
Control
ALU
EX
M
M WB
ID/EX
EX/MEM
MEM/WB
Datamemory
Mux
Forwardingunit
IF/ID
Inst
ruct
ion
Mux
4EX/MEM.RegisterRd
5
2IF/ID.RegisterRs
WB
WB
MEM/WB.RegisterRd
IF/ID.RegisterRtIF/ID.RegisterRt
IF/ID.RegisterRd
sub $2, $1, $3and $4, $2, $5or $8, $2, $6
$2
$5
26
8
add $9, $4, $2
2
$2
Quinto Ciclo
PCInstruction
memory
Registers
Mux
Mux
Control
ALU
EX
M
M WB
ID/EX
EX/MEM
MEM/WB
Datamemory
Mux
Forwardingunit
IF/ID
Inst
ruct
ion
Mux
8EX/MEM.RegisterRd
6
2IF/ID.RegisterRs
WB
WB
MEM/WB.RegisterRd
IF/ID.RegisterRtIF/ID.RegisterRt
IF/ID.RegisterRd
sub $2, $1, $3and $4, $2, $5or $8, $2, $6
$2
$6
42
9
add $9, $4, $2
4
slt $1, $6, $7
2
Sexto Ciclo
PCInstruction
memory
Registers
Mux
Mux
Control
ALU
EX
M
M WB
ID/EX
EX/MEM
MEM/WB
Datamemory
Mux
Forwardingunit
IF/ID
Inst
ruct
ion
Mux
9EX/MEM.RegisterRd
2
4IF/ID.RegisterRs
WB
WB
MEM/WB.RegisterRd
IF/ID.RegisterRtIF/ID.RegisterRt
IF/ID.RegisterRd
and $4, $2, $5or $8, $2, $6
$4
$2
67
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 paraatrasar 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
Mux
Mux
Mux
Control
ALU
EX
M
WB
M
WB
WB
ID/EX
EX/MEM
MEM/WB
Mux
Hazarddetection
unit
Forwardingunit
0
Mux
IF/ID
ID/EX.MemRead
IF/ID
Writ
e
PC
Writ
e
ID/EX.RegisterRtRtRs
Rd
Rt
IF/ID.RegisterRsIF/ID.RegisterRtIF/ID.RegisterRtIF/ID.RegisterRd
EX/MEM.RegisterRd
MEM/WB.RegisterRd
Instructionmemory
RegistersData
memory
Inst
ruct
ion
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 deinstrução RegUAL Acesso
a dadosReg
Busca deinstrução RegUAL Acesso
a dadosReg
Busca deinstrução RegUAL Acesso
a dadosReg
2 ns 2 ns 2 ns 2 ns...
n Uma opção é sempre congelar o pipeline quando se encontra umainstruçã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 umaprevisão de salto
n Caso a previsão esteja correta, não háperda no pipeline
n Caso a previsão esteja incorreta, asinstrução seguintes ao salto devem serdescartadas (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çãon implementado com o auxílio de uma tabela de histórico
de desvios
n armazena endereço da instrução, endereço do desvioe estado
Outras Técnicas
n múltiplos fluxosn ambas alternativas são executadas simultaneamente
n busca antecipada de instruçõesn 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 desvion 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 deinstrução RegUAL Acesso
a dadosRegbeq $1, $2, 40
add $4, $5, $6
lw $3, 300($0)
Busca deinstrução RegUAL Acesso
a dadosReg
Busca deinstruçã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
PCInstruction
memory
4
Registers
Mux
Mux
Mux
ALU
EX
M
WB
M
WB
WB
ID/EX
0
EX/MEM
MEM/WB
Datamemory
Mux
Hazarddetection
unit
Forwardingunit
IF.Flush
IF/ID
Signextend
Control
Mux
=
Shiftleft 2
Mux
q A velocidade máxima de uma máquina com pipelineé de uma instrução por ciclo de clock.
Acelerando máquinas compipeline
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últiplasinstruções por ciclo de clock:
q arquiteturas superpipeline
q arquiteturas superescalares.
Acelerando máquinascom pipeline
q A arquitetura Superpipeline subdivide cadaestágio do pipeline em subestágios e multiplica oclock internamente.
q Cada (sub)estágio continua executando umainstrução por clock. Mas como o clock interno émultiplicado, o pipeline pode aceitar duas ou maisinstruções para cada clock externo.
Acelerando máquinas compipeline: 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émmúltiplas unidades de execução que sãocapazes de fazer a mesma coisa.
q Isto permite ao processador executarvárias instruções similaresconcorrentemente, pelo roteamento dasinstruções às unidades de execuçãodisponíveis.
Acelerando máquinas compipeline: 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: TheHardware/Software Interface. Morgan Kaufmann.http:/www.mkp.com/cod2e.htm/
Leitura recomendada
n Tanenbaum, A.S., (1990) Organizaçãoestruturada de computadores. Cap 4.
n 4.5 {4.5.4}
