Aula 11

Prévia do material em texto

1
Organização de Computadores I
DCC006
Prof. Omar Paranaiba Vilela Neto
Aula 11 – Pipelining
2
Pipelining: É Natural!
 Lavanderia
 4 pessoas A, B, C e D 
possuem 4 sacolas de 
roupa para lavar, secar 
e dobrar
 Lavar leva 30 minutos
 Secar leva 40 minutos
 Dobrar leva 20 minutos
A B C D
3
 Lavanderia sequencial leva 6 horas para terminar
 Se eles conhecessem computação, quanto tempo levaria? 
A
B
C
D
30 40 20 30 40 20 30 40 20 30 40 20
6 7 8 9 10 11 Meia-noite
T
a
r
e
f
a
s
s
e
q
Tempo
Lavanderia Sequencial
4
 Lavanderia com pipelining leva 3.5 horas !!! 
A
B
C
D
6 7 8 9 10 11 Meia-noite
T
a
r
e
f
a
s
s
e
q
Tempo
30 40 40 40 40 20
Lavanderia com Pipelining
5
 Pipelining não melhora a 
latência de uma única 
tarefa, mas melhora o 
throughput do trabalho 
todo
 Taxa de inserção de 
tarefas é limitada pela 
tarefa mais lenta
 Existem múltiplas tarefas 
sendo executadas em um 
dado instante
 SpeedUp potencial = 
número de estágios
 Tempo para encher o 
pipeline e tempo de dreno 
reduzem o speedup
A
B
C
D
6 7 8 9
T
a
r
e
f
a
s
s
e
q
Tempo
30 40 40 40 40 20
Lições Aprendidas
6
 Múltiplas instruções podem ser executadas a cada instante
 Leva em consideração o paralelismo existente entre instruções
 Chave para implementação eficiente em qualquer processador 
moderno
Pipelining
7
Implementação de Pipeline
Instrução
R
E
G
R
E
G
Comb.
R
E
S
U
L
T
A
D
O
Clock
Comb.Comb.
1τ 2τ 3τ
/ 1 2 3
/ 1 2 3max( , , )
s pipe
c pipe
t
t
τ τ τ
τ τ τ
= + +
=
8
Equação do Pipeline
t s/ pipe=∑ τ i
t c / pipe=max  τ i 
t c / pipe=∑ τ i  /n
9
Pipelining
• Melhoria do desempenho pelo aumento do throughput de instruções
Speedup ideal é o número de estágios no pipeline. 
Instruction
fetch
Reg ALU Data
access
Reg
8 ns
Instruction
fetch
Reg ALU Data
access
Reg
8 ns
Instruction
fetch
 8 ns
Time
lw $1, 100($0)
lw $2, 200($0)
lw $3, 300($0)
2 4 6 8 10 12 14 16 18
2 4 6 8 10 12 14
...
Program
execution
order
(in instructions)
Instruction
fetch
Reg ALU
Data
access
Reg
Time
lw $1, 100($0)
lw $2, 200($0)
lw $3, 300($0)
2 ns
Instruction
fetch
Reg ALU
Data
access
Reg
2 ns
Instruction
fetch
Reg ALU
Data
access
Reg
2 ns 2 ns 2 ns 2 ns 2 ns
Program
execution
order
(in instructions)
10
Representação esquemática do Pipelining
Instrução 1 2 3 4 5 6 7 8 9
i IF ID EX MEM WB
i+1 IF ID EX MEM WB
i+2 IF ID EX MEM WB
i+3 IF ID EX MEM WB
i+4 IF ID EX MEM WB
11
Pipelining
• Como facilitar a construção.
– Todas as instruções tem o mesmo comprimento
– Poucos formatos de instrução 
– Operandos em memória aparece somente em loads e stores
• O que é difícil ?
– Hazards estrutural: suponha que você tenha somente uma memória
– Hazards controle: Instruções de desvio
– Hazards data: Uma instrução depende de uma instrução antecessora
12
Idéia Básica
Instruction
memory
Address
4
32
0
Add Addresult
Shift
left 2
Instruction
M
u
x
0
1
Add
PC
0Write
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
dataAddress
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
O que precisamos adicionar ao Datapath?
13
Pipelined Datapath
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
Você pode identificar um problema mesmo se não existe dependência?
Quais instruções manifestam este problema?
14
Datapath Corrigido
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
Address
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
Data
memory
1
ALU
result
M
u
x
ALU
Zero
ID/EX
15
Representação Gráfica do Pipeline
• Responda as seguintes questões:
– Quantos ciclos são usados para executar este código?
– O que a ALU esta fazendo durante o 4º ciclo?
– Use esta representação para ajuda-lo a entender o datapaths
IM Reg DM Reg
IM Reg DM Reg
CC 1 CC 2 CC 3 CC 4 CC 5 CC 6
Time (in clock cycles)
lw $10, 20($1)
Program
execution
order
(in instructions)
sub $11, $2, $3
ALU
ALU
16
Controle do Pipeline
PC
Instruction
memory
Address
In
st
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
17
• Nós temos 5 estágios. O que necessita ser controlado em cada estágio?
– Busca da Instrução e incrementa PC
– Decodificação da Instrução / Leitura do Banco de Registradores
– Execução ou cálculo de Endereço
– Acesso à Memória de Dados
– Escrita no Banco de Registradores
 
Controle do Pipeline
18
•
Controle Pipeline
Instruction Branch
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
Execution/Address Calculation 
stage control lines
Memory access stage 
control lines
Write-back 
stage control 
lines
Dst Op1 Op0 Src Read Write write Reg
Control
EX
M
WB
M
WB
WB
IF/ID ID/EX EX/MEM MEM/WB
Instruction
19
Datapath com Controle
PC
Instruction
memory
In
st
ru
ct
io
n
Add
Instruction
[20– 16]
M
em
to
R
eg
ALUOp
Branch
RegDst
ALUSrc
4
16 32Instruction[15– 0]
0
0
M
u
x
0
1
Add Addresult
Registers
Write
register
Write
data
Read
data 1
Read
data 2
Read
register 1
Read
register 2
Sign
extend
M
u
x
1
ALU
result
Zero
Write
data
Read
data
M
u
x
1
ALU
control
Shift
left 2
R
eg
W
rit
e
MemRead
Control
ALU
Instruction
[15– 11]
6
EX
M
WB
M
WB
WBIF/ID
PCSrc
ID/EX
EX/MEM
MEM/WB
M
u
x
0
1
M
em
W
rit
e
Address
Data
memory
Address
20
Harzards
Tudo que vimos até o momento faz parte do 
Maravilhoso Mundo dos Pipelinings
Vamos conhecer os
Harzards
21
Harzards Estruturais
Ocorre quando duas instruções desejam usar a 
mesma estrutura ao mesmo tempo
Não há problemas em nosso datapath
22
Harzards Estruturais
Ocorre quando duas instruções desejam usar a 
mesma estrutura ao mesmo tempo
Problemas se tivessemos apenas uma memória
23
• Problemas com o início da instrução seguinte antes que a instrução 
anterior tenha terminado– dependências que “retornam no tempo” são conflitos de Dados
Harzard de Dados
• Considere o programa
sub $2, $1, $3
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)
24
• Problemas com o início da instrução seguinte antes que a instrução 
anterior tenha terminado
– dependências que “retornam no tempo” são conflitos de Dados
Harzard de Dados
IM Reg
IM Reg
CC 1 CC 2 CC 3 CC 4 CC 5 CC 6
Time (in clock cycles)
sub $2, $1, $3
Program
execution
order
(in instructions)
and $12, $2, $5
IM Reg DM Reg
IM DM Reg
IM DM Reg
CC 7 CC 8 CC 9
10 10 10 10 10/– 20 – 20 – 20 – 20 – 20
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)
Value of 
register $2:
DM Reg
Reg
Reg
Reg
DM
25
• O compilador garante não existir dependência
• Onde nós faremos a inserção de “nops” ?
sub $2, $1, $3
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)
• Problema: Isto é Lento!
Solução por Software
26
• Usar resultados temporários, sem esperar que eles sejam escritos
– adiantamento do banco de registradores antes de ler/escrever o 
registrador
– Adiantamento da ALU
Harzard de Dados - Adiantamento
what if this $2 was $13?
IM Reg
IM Reg
CC 1 CC 2 CC 3 CC 4 CC 5 CC 6
Time (in clock cycles)
sub $2, $1, $3
Program
execution order
(in instructions)
and $12, $2, $5
IM Reg DM Reg
IM DM Reg
IM DM Reg
CC 7 CC 8 CC 9
10 10 10 10 10/– 20 – 20 – 20 – 20 – 20
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)
Value of register $2 :
DM Reg
Reg
Reg
Reg
X X X – 20 X X X X XValue of EX/MEM :
X X X X – 20 X X X XValue of MEM/WB :
DM
27
Harzard de Dados - Adiantamento
PC Instructionmemory
Registers
M
u
x
M
u
x
Control
ALU
EX
M
WB
M
WB
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.RegisterRd
MEM/WB.RegisterRd
Rt
Rt
Rs
IF/ID.RegisterRd
IF/ID.RegisterRt
IF/ID.RegisterRt
IF/ID.RegisterRs
28
• Load pode ainda causar dependência:
– Uma instrução tenta ler um registrador antes que uma instrução load que 
escreve no mesmo registrador seja completada.
–
–
• Nós precisamos de uma unidade de detecção para parar (“stall”) a instrução 
load
Harzard de Dados – Adiantamento failed
Reg
IM
Reg
Reg
IM
CC 1 CC 2 CC 3 CC 4 CC 5 CC 6
Time (in clock cycles)
lw $2, 20($1)
Program
execution
order
(in instructions)
and $4, $2, $5
IM Reg DM Reg
IM DM Reg
IM DM Reg
CC 7 CC 8 CC 9
or $8, $2, $6
add $9, $4, $2
slt $1, $6, $7
DM Reg
Reg
Reg
DM
29
Harzard de Dados – Parada
• Nós paramos o pipeline deixando todos os sinais de controle de EX, 
MEM e ER em 0
lw $2, 20($1)
Program
execution
order
(in instructions)
and $4, $2, $5
or $8, $2, $6
add $9, $4, $2
slt $1, $6, $7
Reg
IM
Reg
Reg
IM DM
CC 1 CC 2 CC 3 CC 4 CC 5 CC 6
Time (in clock cycles)
IM Reg DM RegIM
IM DM Reg
IM DM Reg
CC 7 CC 8 CC 9 CC 10
DM Reg
RegReg
Reg
bubble
30
Unidade de detecção de conflito
• Pára o avanço de instruções
• Controla a escrita dos registradores PC BI/DI
• Escolhe os valores reais do controle ou todos em 0
PC Instructionmemory
Registers
M
u
x
M
u
x
M
u
x
Control
ALU
EX
M
WB
M
WB
WB
ID/EX
EX/MEM
MEM/WB
Data
memory
M
u
x
Hazard
detection
unit
Forwarding
unit
0
M
u
x
IF/ID
In
st
ru
ct
io
n
ID/EX.MemRead
IF
/ID
W
rit
e
P
C
W
rit
e
ID/EX.RegisterRt
IF/ID.RegisterRd
IF/ID.RegisterRt
IF/ID.RegisterRt
IF/ID.RegisterRs
Rt
Rs
Rd
Rt EX/MEM.RegisterRd
MEM/WB.RegisterRd
Harzard de Dados – Detecção
31
• Quando decidimos desviar, outras instruções estão no pipeline!
• Nós pressupomos o desvio “não-realizado”
– Caso o desvio se realize precisamos descartar as instruções que 
estiverem sendo buscadas e decodificadas
Harzard de Desvios
Reg
Reg
CC 1
Time (in clock cycles)
40 beq $1, $3, 7
Program
execution
order
(in instructions)
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)
CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9
Reg
32
Descarte de Instruções
PC Instructionmemory
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
33
Melhoria do Desempenho
• Reordenar as instruções:
lw $t0, 0($t1)
lw $t2, 4($t1)
sw $t2, 0($t1)
sw $t0, 4($t1)
• “branch delay slot”
• Superscalar: inicia mais de uma instrução no mesmo ciclo
34
Escalonamento dinâmico
• O hardware faz o escalonamento 
– O hardware escolhe as instruções para executar
– Execução fora de ordem é possível
– Pressuposição dinâmica de desvio
• Todos processadores modernos são complicados
– DEC Alpha 21264: 9 estágios pipeline, 6 saídas de instruções
– PowerPC e Pentium: branch history table
– Importância da tecnologia de Compiladores
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34