Y86:
Encadeamento de Instruções (PIPE)
Arquitectura de Computadores
Lic. em Engenharia Informática
Luís Paulo Santos
Y86: Encadeamento de instruções (pipeline)
9 – Organização do Processador
Conteúdos
9.2 – Datapath encadeado (pipeline)
9.3 – Dependências de Dados e Controlo
Resultados de
Aprendizagem
AC – Y86: PIPE
R9.2 – Analisar e descrever organizações
encadeadas de processadores elementares
R9.3 – Caracterizar limitações inerentes a
organizações encadeadas (dependências) e
conceber potenciais soluções
2
Y86 PIPE-: Limitações
• Dependências de Dados
– Uma leitura de um registo precedida de uma escrita no mesmo registo
constitui uma dependência de dados
– Se a leitura ocorre antes da conclusão da escrita ocorre uma anomalia
– Na versão PIPE- estas anomalias são corrigidas empatando o pipeline
através da injecção de “bolhas” (nops)
• Dependências de controlo
– O desfecho dos saltos condicionais só é conhecido depois da fase de
execução. O Y86 prevê que o salto é tomado, executando as instruções
no alvo de forma especulativa. Previsões erradas são corrigidas inserindo
“bolhas”.
– O destino de um ret só é conhecido depois da fase de leitura de
memória. O Y86 resolve esta anomalia inserindo “bolhas” até que o
endereço da próxima instrução seja conhecido.
AC – Y86: PIPE
3
Y86 PIPE: Motivação
• As dependências de dados são demasiado comuns
• Resolvê-las recorrendo à injecção de “bolhas” resulta no
desperdício de um elevado número de ciclos, comprometendo o
desempenho do pipeline
• A versão PIPE do Y86 propõe-se resolver estas dependências de
dados, diminuindo o número de bolhas injectadas (logo o
número de ciclos desperdiçados)
• As dependências de controlo não sofrem qualquer alteração
relativamente a PIPE-
AC – Y86: PIPE
4
Write back
PIPE-: Condições para stall
W
icode
valE
dstE
dstM
data out
read
Data
Data
memory
memory
Mem.
control
write
• Registo a ler
valM
Memory
data in
Addr
M_ valA
M_Bch
– d_srcA e d_srcB
M
icode
Bch
(instrução no estágio de
decode)
• Registos destino
– dstE e dstM nos estágios E,
MeW
• Dependência Dados
– d_srcA ou d_srcB ==
E_dst? ou M_dst? Ou
W_dst? (? = E ou M)
• Ignorar se RegID==8
valE
valA
dstE
dstM
dstE
dstM srcA
dstE
dstM srcA
e_Bch
Execute
E
icode
ALU
fun.
ALU
ALU
CC
CC
ifun
ALU
A
ALU
B
valC
valA
valB
srcB
d_ srcA d_ srcB
Select
A
Decode
d_ rvalA
A
srcB
W_ valM
B
Register
Register M
file
file
W_ valE
E
D
icode
ifun
rA
rB
valC
valP
Predict
PC
Fetch
Instruction
Instruction
memory
memory
PC
PC
increment
increment
f_PC
M_ valA
Select
PC
F
AC – Y86: PIPE
W_ valM
predPC
5
PIPE- : Implementação do stalling
Se (d_srcA in {E_dstE, E_dstM, M_dstE, M_dstM, W_dstE, W_dstM} ||
d_srcB in {E_dstE, E_dstM, M_dstE, M_dstM, W_dstE, W_dstM} )
Então
E_bubble = D_stall = F_stall =1;
W_dstM
W_dstE
W
icode
valE
valM
dstE
dstM
valE
valA
dstE
dstM
E_bubble
“Injecção” de um nop no
estágio E (icode=0,
E_dstE=E_dstM=8)
dstM
D_stall
Escrita no registo D inibida
M_dstM
M_dstE
M
icode
Bch
E_dstM
Pipe
control
logic
E_dstE
E_bubble
E
icode
ifun
valC
valA
valB
dstE
srcA
srcB
d_srcB
d_srcA
srcB
D_icode
D_stall
F_stall
AC – Y86: PIPE
D
F
srcA
icode
ifun
rA
rB
valC
F_stall
Escrita no registo F inibida
valP
predPC
6
Data Forwarding
• Problema
– Um registo é lido na fase de DECODE
– A escrita só ocorre na fase de WRITEBACK
• Observação
– O valor a escrever no registo é gerado na fase de execução
ou memória
• Resolução do problema
– Passar o valor necessário directamente do estágio onde está
disponível (E, M ou W) para o estágio de DECODE
AC – Y86: PIPE
7
I1
I2
Y86 PIPE: Exemplo de Forwarding (1)
I1: irmovl $10, %eax
I2: mrmovl 30(%ebx), %ecx
W_valE
valE
W
Data
Data
memory
memory
I2
I3
Memory
Addr, Data
I3: addl %esi, %edi
M
I4: addl %esi, %eax
Bch
I3
I4
I5: jmp MAIN
valE
CC
CC
ALU
ALU
Execute
aluA, aluB
E
valA valB
1
I1
F
I2
I3
I4
I5
I6
AC – Y86: PIPE
2
D
F
3
4
5
E
D
M
E
W
M
F
D
F
E
D
F
6
,
I4
I5
d_srcA,
d_srcB
Forward
A
B
Register
Register M
file
file E
Decode
Write back
W
M
E
D
F
D
valP
rA,
valP
I5
I6
Instruction
Instruction
memory
memory
PC
PC
increment
increment
Fetch
f_PC
F
valB = W_valE
8
I1
Y86 PIPE: Exemplo de Forwarding (2)
I1: irmovl $10, %eax
I2: mrmovl 30(%ebx), %ecx
W
Data
Data
memory
memory
I1
I2
M_valE
Memory
Addr, Data
I3: addl %esi, %eax
valE
M
I4: …
Bch
I2
I3
valE
CC
CC
ALU
ALU
Execute
aluA, aluB
E
valA valB
1
I1
F
I2
I3
I4
I5
I6
AC – Y86: PIPE
2
D
F
3
4
5
E
D
M
E
W
M
F
D
F
E
D
F
6
,
I3
I4
d_srcA,
d_srcB
Forward
A
B
Register
Register M
file
file E
Decode
Write back
W
M
E
D
F
D
valP
rA,
valP
I4
I5
Instruction
Instruction
memory
memory
PC
PC
increment
increment
Fetch
f_PC
F
valB = M_valE
9
Y86 PIPE: Exemplo de Forwarding (3)
W
I1: irmovl $10, %eax
Data
Data
memory
memory
I2: addl %esi, %eax
Memory
Addr, Data
I3: …
M
Bch
I1
e_valE
valE
CC
CC
ALU
ALU
Execute
aluA, aluB
E
valA valB
1
I1
F
I2
I3
I4
I5
I6
AC – Y86: PIPE
2
D
F
3
4
5
E
D
M
E
W
M
F
D
F
E
D
F
6
,
I2
d_srcA,
d_srcB
Forward
A
B
Register
Register M
file
file E
Decode
Write back
W
M
E
D
F
D
valP
rA,
valP
I3
Instruction
Instruction
memory
memory
PC
PC
increment
increment
Fetch
f_PC
F
valB = e_valE
10
I1
I2
Y86 PIPE: Exemplo de Forwarding (4)
I1: mrmovl 30(%ebx), %ecx
I3: addl %esi, %ebx
W_valM
valM
W
Data
Data
memory
memory
I2
I3
Memory
Addr, Data
I3: addl %esi, %edi
M
I4: addl %ecx, %eax
Bch
I3
I4
I5: jmp MAIN
valE
CC
CC
ALU
ALU
Execute
aluA, aluB
E
valA valB
1
I1
F
I2
I3
I4
I5
I6
AC – Y86: PIPE
2
D
F
3
4
5
E
D
M
E
W
M
F
D
F
E
D
F
6
,
I4
I5
d_srcA,
d_srcB
Forward
A
B
Register
Register M
file
file E
Decode
Write back
W
M
E
D
F
D
valP
rA,
valP
I5
I6
Instruction
Instruction
memory
memory
PC
PC
increment
increment
Fetch
f_PC
F
valA = W_valM
11
I1
Y86 PIPE: Exemplo de Forwarding (5)
I1: mrmovl 30(%ebx), %ecx
I2: addl %esi, %edi
W
m_valM
Data
Data
memory
memory
I1
I2
Memory
Addr, Data
I3: addl %ecx, %eax
M
I4: …
Bch
I2
I3
valE
CC
CC
ALU
ALU
Execute
aluA, aluB
E
valA valB
1
I1
F
I2
I3
I4
I5
I6
AC – Y86: PIPE
2
D
F
3
4
5
E
D
M
E
W
M
F
D
F
E
D
F
6
,
I3
I4
d_srcA,
d_srcB
Forward
A
B
Register
Register M
file
file E
Decode
Write back
W
M
E
D
F
D
valP
rA,
valP
I4
I5
Instruction
Instruction
memory
memory
PC
PC
increment
increment
Fetch
f_PC
F
valA = m_valM
12
Y86 PIPE: Exemplo de Forwarding (6)
I1: mrmovl 30(%ebx), %ecx
I2: addl %ecx, %eax
W
m_valM
Data
Data
memory
memory
I1
Memory
Addr, Data
I3: …
M
Bch
nop
I1
valE
CC
CC
ALU
ALU
Execute
aluA, aluB
E
valA valB
1
I1
F
I2
I3
I4
I5
AC – Y86: PIPE
2
D
F
3
E
D
F
4
5
M
E
W
M
D
F
E
D
F
6
,
I2
d_srcA,
d_srcB
Forward
A
B
Register
Register M
file
file E
Decode
Write back
W
W
M
E
D
F
D
valP
rA,
valP
I3
Instruction
Instruction
memory
memory
PC
PC
increment
increment
Fetch
f_PC
F
valA = m_valM
13
Load /Use
• Uma situação de load/use ocorre quando uma leitura de
memória para registo é seguida de uma leitura do mesmo
registo
I1: mrmovl 30(%ebx), %ecx
I2: addl %ecx, %eax
• Como I1 ainda está no estágio de Execute quando I2 pede o
valor do registo, este valor ainda não foi lido e não pode
ser encaminhado (forwarded) para o Decode
• A resolução da anomalia passa por injectar uma “bolha”,
dando assim tempo para que a memória seja lida
AC – Y86: PIPE
14
Data
Data
memory
memory
Mem.
control
write
Memory
data in
Detecção de load/use
Addr
M_Bch
M
icode
M_valA
M_valE
Bch
valE
valA
dstE
dstM
e_Bch
e_valE
ALU
ALU
CC
CC
Execute
E
icode
ifun
ALU
fun.
ALU
A
ALU
B
valC
valA
valB
dstE
dstM
dstE
dstM
srcA
srcB
d_srcA d_srcB
Sel +Fwd
A
Decode
D
icode
rA
rB
valC
srcB
Fwd
B
A
ifun
srcA
W_valM
B
Register
RegisterM
file
file E
W_valE
valP
Predict
PC
Anomalia
Fetch
Instruction
Instruction
memory
memory
Condição
PC
PC
increment
increment
f_PC
Load/Use
F
AC – Y86: PIPE
M_valA
E_icode in { IMRMOVL, IPOPL } &&
E_dstM in { d_srcA, d_srcB }
Select
PC
W_valM
predPC
15
Y86 PIPE: Atalho a usar
I1: irmovl $10, %eax
W
I1
Data
Data
memory
memory
I2: irmovl $30, %eax
Memory
Addr, Data
I3: addl %eax, %eax
valE
M
Bch
valE
CC
CC
I2
ALU
ALU
Execute
aluA, aluB
e_valE
E
valA valB
1
I1
F
I2
I3
I4
2
D
F
3
4
E
D
M
E
F
D
F
5
6
,
I3
d_srcA,
d_srcB
AC – Y86: PIPE
A
B
Register
Register M
file
file E
Decode
Write back
D
valP
rA,
valP
I4
Instruction
Instruction
memory
memory
PC
PC
increment
increment
Fetch
I5
I6
Forward
f_PC
F
valA = valB = e_valE
16
W_valE
Write back
W_valM
W
icode
valE
valM
dstE dstM
data out
read
m_valM
Data
Data
memory
memory
Mem.
control
write
Memory
Y86 PIPE:
implementação de
forwarding
data in
Addr
M_Bch
M
icode
Bch
– Adicionar 5 atalhos dos
registos de pipeline E, M,
e W para o estágio
M_valA
M_valE
valE
valA
dstE dstM
e_Bch
e_valE
ALU
ALU
CC
CC
Execute
E
icode
ifun
ALU
fun.
ALU
A
ALU
B
valC
valA
DECODE
valB
dstE dstM srcA
srcB
d_srcA d_srcB
dstE dstM srcA
Sel+Fwd
A
Decode
D
icode
Fwd
B
A
rA
rB
valC
W_valE
valP
AC – Y86: PIPE
Instruction
Instruction
memory
– Adicionar 2 multiplexers
para seleccionar valA e
valB no DECODE
W_valM
B
Register
Register M
file
file E
ifun
srcB
PC
PC
increment
Predict
PC
17
Y86 PIPE: implementação de forwarding
W_valE
W_valM
valE
valM
dstE dstM
data out
read
m_valM
Data
Data
memory
memory
l
write
## Qual o atalho a utilizar?
## NOTA: X representa A ou B conforme
## se trate de valA ou valB
data in
Addr
M_valA
M_valE
valE
valA
dstE dstM
e_valE
ALU
ALU
ALU
fun.
ALU
A
ALU
B
valC
valA
valB
dstE dstM srcA
srcB
d_srcA d_srcB
dstE dstM srcA
Sel+Fwd
A
Fwd
B
A
B
Register
Register M
file
file E
AC – Y86: PIPE
valC
srcB
valP
W_valM
W_valE
int new_E_valX = [
# Use incremented PC
D_icode in { ICALL, IJXX } : D_valP;
# Forward valE from execute
d_srcX == E_dstE : e_valE;
# Forward valM from memory
d_srcX == M_dstM : m_valM;
# Forward valE from memory
d_srcX == M_dstE : M_valE;
# Forward valM from write back
d_srcX == W_dstM : W_valM;
# Forward valE from write back
d_srcX == W_dstE : W_valE;
# Use value read from register file
1 : d_rvalX;
];
18
Y86 PIPE: Resumo
• Dependências de Dados
– Tratadas maioritariamente com forwarding
• Não há penalização no desempenho
– Load/use exige que se empate o pipeline durante 1 ciclo
• Dependências de Controlo (não há alterações relativamente a PIPE-)
– Salto condicional mal previsto: cancelar instruções em F e D
• 2 ciclos do relógio desperdiçados
– ret: Empatar o estágio F (injectando bolhas em E) até o
endereço de retorno ser lido
• 3 ciclos do relógio desperdiçados
AC – Y86: PIPE
19