Pipelining - Universidade do Minho

Transcrição

Arquitectura de Computadores II
LESI - 3º Ano
Pipelining
João Luís Ferreira Sobral
Departamento do Informática
Universidade do Minho
Janeiro 2002
Visão global de Pipelining
•
Técnica que permite sobrepor a execução de várias instruções
Time
6 PM
7
8
9
10
11
12
1
2 AM
6 PM
7
8
9
10
11
12
1
2 AM
Task
order
A
B
C
D
Time
Task
order
A
B
C
D
•
•
Cada fase (estágio) da pipiline executa de forma concorrente, como
numa linha de montagem
Pipelining em MIPS
•
Fases de execução das instruções no MIPS:
1.
2.
3.
4.
5.
IF
Busca da instrução (IF)
Leitura dos registos e descodificação das instruções (ID)
Execução da operação ou cálculo de endereço (EXE)
Acesso ao operando em memória (MEM)
Escrita do resultado em registo (WB)
ID
EXE
MEM
WB
IF
ID
EXE
MEM WB
IF
Execução em pipeline
IF
ID
IF
EXE
ID
IF
MEM WB
EXE MEM WB
ID
EXE MEM WB
2
© João Luís Sobral 2002
•
Desempenho do processador com pipelining
•
Duração de cada ciclo de execução em pipeline é igual à duração do
estágio mais longo, adicionando a sobrecarga da pipeline (passagem de
informação entre estágios)
Tcc pipeline = max [ estágioi ] + sobrecarga de pipeline
•
A execução em pipeline requer que as várias fases estejam
balanceadas (i.e., demorem o mesmo tempo a executar):
lw $s0, 0($s1)
add $s1, $s2, $s3
•
IF
ID
IF
EXE MEM WB
ID
EXE WB
IF
ID
EXE
MEM WB
O tempo (ideal) de execução com pipelining:
Texecpl = [ #estágios
IF
ID
IF
+
( #instruções - 1) ]
x
Tcc
EXE MEM WB
ID
EXE MEM WB
IF
ID
EXE MEM WB
•
Pipelining aumenta o débito (instruções realizadas por unidade de
tempo) mas não diminui o tempo necessário para cada instrução!
•
O ganho é potencialmente igual ao número de estágios da pipeline
ganho =
•
TexecSc
# instruções×# estágios × Tcc
=
=
# estágios
TexecPl [# estágios + (# instruções − 1)]× Tcc #instruções→∞
O ganho pode ser interpretado de forma diferente, consoante a base de
comparação seja uma implementação single-cycle ou multi-ciclo
base multi-ciclo
CPIpipeline = CPImulti-ciclo / # estágios da pipeline
base single-cycle
Tccpipeline = Tccsingle-cycle / # estágios
3
Single-cycle versus Multi-ciclo versus Pipelining
•
Ciclo 1
Ciclo 2
Clk
• Implementação Single Cycle:
Load
Store
Waste
Ciclo 1 Ciclo 2 Ciclo 3 Ciclo 4 Ciclo 5 Ciclo 6 Ciclo 7 Ciclo 8 Ciclo 9 Ciclo 10
Clk
• Implementação Multi-ciclo:
Load
Ifetch
Reg
Exec
Mem
Wr
Store
Ifetch
Reg
Exec
Mem
R-type
Ifetch
• Implementação com Pipeline:
Load Ifetch
Reg
Store Ifetch
Exec
Mem
Wr
Reg
Exec
Mem
Wr
Reg
Exec
Mem
R-type Ifetch
4
Wr
•
Exemplo de desempenho do processador MIPS com pipelining
•
Tempos acesso às unidades funcionais:
Memória (Leitura ou escrita)
2 nanosegundos
ALU
2 nanosegundos
Banco de registos
1 nanosegundo
•
Qual a diferença de desempenho entre uma implementação com
pipelining e uma implementação single-cycle com ciclo de duração fixa?
•
Duração de cada instrução:
Tipo de
Instrução
Tipo R
Load
Store
Branch
Busca da
instrução
2
2
2
2
Leitura de
registos
1
1
1
1
Operação
na ALU
2
2
2
2
Acesso à
Memória
Escrita em
registo
1
1
2
2
Total
•
CPIsingle-cycle = CPIpipeline = 1.
•
Duração do ciclo na versão single-cycle com o ciclo de relógio fixo:
6 ns
8 ns
7 ns
5 ns
Tccsc = duração da instrução mais longa = load = 8 ns
•
Duração do período de relógio com pipeline, assumindo 5 estágios:
Tccpipe = duração do estágio mais longo = 2 ns
•
Ganho (máx.) = Texecsc/Texecpipe = Tccsc/Tccpipe = 8 ns / 2 ns = 4,0x
Program
execution
Time
order
(in instr uctio ns)
lw $1, 10 0($0)
2
Instructi on
R eg
fe tch
lw $2, 20 0($0)
4
6
8
A LU
Data
access
10
12
14
16
A LU
Data
access
18
R eg
Instructi on
R eg
fe tch
8 ns
lw $3, 30 0($0)
R eg
Instructi on
fetch
8 ns
...
8 ns
P rogram
e xecutio n
Time
o rd er
( in instructions)
2
lw $1, 100($0)
Instruction
fetch
lw $2, 200($0)
2 ns
lw $3, 300($0)
4
R eg
Instruction
fetch
2 ns
6
8
Da ta
access
ALU
Reg
Instruction
fetch
2 ns
ALU
R eg
2 ns
10
14
12
R eg
D at a
access
R eg
ALU
D at a
access
2 ns
2 ns
R eg
2 ns
•
Ganho na execução de 3 instruções = 24 / 14 = 1,74x
•
Ganho na execução de 1000 instruções = 8000 ns / 2008 ns = 3,98x
5
•
•
Projectar o conjunto de instruções para execução em pipelining
•
Instruções de dimensão fixa facilitam a busca e a descodificação de
instruções
•
Poucos formatos de instruções com os registos fonte especificados
sempre nos mesmos campos permitem o paralelismo entre a
descodificação e a leitura do valor dos registos
•
Uma arquitectura do tipo load-store, onde os operandos em memória só
aparecem em load e store facilitam o balanceamento dos estágios da
pipeline
•
Operandos alinhados em memória tornam os acessos à memória mais
rápidos
Anomalias na execução em pipelining (hazards)
•
Impedem que a pipeline prossiga a execução normal provocando o
aumento do CPI médio para valores superiores a 1.
•
Estruturais – o hardware não suporta a combinação de instruções em
execução (ex. são necessárias duas unidades para acesso à memória,
uma para a busca das instruções outra para os acessos a dados em
memória)
Solução =>
duplicar unidades funcionais ou portas de acesso
•
Controlo – a execução da instrução seguinte depende de uma decisão
baseada num resultado anterior (ex. saltos condicionais)
Soluções =>
1. empatar a pipeline
2. prever o salto
3. retardar o salto
•
Dados – a execução da instrução seguinte depende de dados produzidos
por instruções anteriores.
Solução =>
1. delegar no compilador
2. encaminhar os dados entre unidades
6
•
Exemplos de anomalias de controlo na execução em pipeline
•
Empatar a execução de um salto
Program
execution
Time
order
(in instructions)
add $4, $5, $6
2
4
Instruction
fetch
beq $1, $2, 40
2ns
6
Reg
8
Data
access
AL U
Instru ction
fet ch
Reg
10
4 ns
16
Reg
Data
access
ALU
Instru ction
fe tch
lw $3, 300($0)
14
12
Re g
Reg
Data
access
ALU
Re g
2ns
•
Prever o salto como não tomado
Progr am
execution
Time
order
(in instructions)
add $4, $5, $6
2
6
Instruction
Reg
fetch
2 ns
lw $3, 300($0)
2
4
Inst ruction
Reg
fetch
2 ns
b u b b le
or $7, $8, $9
•
Data
acce ss
Dat a
access
8
10
Reg
14
12
Reg
ALU
Data
acce ss
Reg
b u b b le
b u b b le
b u bb le
In structio n
Reg
fetch
4 ns
14
R eg
ALU
Da ta
access
ALU
12
Reg
ALU
6
Instruction
Reg
fetch
beq $1, $2, 40
10
Instruction
Reg
fetch
2 ns
Program
execution
Time
order
(in instructions)
8
Da ta
a ccess
ALU
Instruction
Reg
fetch
beq $1, $2, 40
add $4, $5 ,$6
4
b u b b le
Data
access
ALU
Reg
Execução retardada do salto
Program
execution
order
Time
(in instructions)
beq $1, $2, 40
2
Instruct ion
fetch
add $4, $5, $6
(Delayed branch slot) 2 ns
lw $3, 300($0)
4
Reg
Instru ction
fe tch
6
AL U
Reg
Instru ction
fe tch
2 ns
8
Data
acce ss
ALU
Reg
10
12
14
Reg
Data
access
ALU
Re g
Data
access
Re g
2 ns
7
•
Exemplos de anomalias de dados na execução em pipeline
•
Em caminhar os dados para resolver a dependência
Program
execution
order
Time
(in instructions)
a dd $s0, $t0, $t1
2
IF
sub $t2, $s0, $t3
•
4
8
ID
EX
MEM
IF
ID
EX
10
WB
MEM
WB
Limitação no encaminhamento dos dados
2
Time
Program
execution
order
(in instructions)
lw $s0, 20($t1)
IF
4
6
ID
EX
bubble
bubble
sub $t2, $s0, $t3
•
6
IF
8
10
12
MEM
WB
bubble
bubble
bubble
ID
EX
MEM
14
WB
Reordenação das instruções para resolver a dependência de dados
lw
lw
sw
sw
$t0,
$t2,
$t2,
$t0,
0($t1)
4($t1)
0($t1)
4($t1)
#
#
#
#
#
lw
lw
sw
sw
$t0,
$t2,
$t0,
$t2,
0($t1)
4($t1)
4($t1)
0($t1)
#
#
#
#
8
reg $t1 contém &v[k]
$t0 (temp) = v[k]
$t2 = v[k+1]
v[k] = $t2
v[k+1] = $t0
$t0 (temp) = v[k]
$t2 = v[k+1]
v[k+1] = $t0
v[k] = $t2
Pipelining
•
DP para suporte à execução em pipeline
•
5 fases de execução => 5 estágios da pipeline
IF: Instruction fetch
ID: Instruction decode/
register file read
EX: Exe cute/
address calculation
MEM: Memory access
WB: Write back
0
M
u
x
1
Add
dd
Add reA
sult
4
Shift
left 2
PC
Read
register 1
Address
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
Instruction
Instruction
memory
0
M
u
x
1
Write
data
Zero
ALU ALU
result
Read
data
Address
1
M
u
x
0
Data
memory
Write
data
16
32
Sign
extend
•
Entre cada fase da pipeline é necessário introduzir um registo para
conter toda a informação necessária à execução dessa instrução
•
O nome de cada registo corresponde às fases que separa (Ex. IF/ID)
•
O valor dos registos avança simultaneamente com a execução das
instruções
0
M
u
x
1
IF/ID
ID/EX
EX/MEM
MEM/WB
Add
dd
Add reA
sult
4
Shift
left 2
PC
Address
Instruction
memory
n
o
ti
c
ru
t
s
n
I
Read
register 1
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
0
M
u
x
1
Write
data
Zero
ALU ALU
result
Address
Data
memory
Write
data
16
Sign
extend
Read
data
1
M
u
x
0
32
9
Pipelining
•
Representação gráfica da execução em pipeline
lw $10, 20($1)
sub $11, $2, $3
•
Representação com um diagrama multi-ciclo
Time (in clock cycles)
Program
execution
order
(in instructions)
lw $10, 20($1)
CC 1
CC 2
CC 3
IM
Reg
ALU
sub $11, $2, $3
Progr am
execution
order
( in instructions)
lw $10, $20($1)
IM
CC 5
DM
Reg
ALU
DM
CC 6
Reg
Time ( in clock cycles)
CC 1
CC 2
CC 3
CC 4
CC 5
Instruction
fetch
Instruction
decode
Execution
Data
access
Wri te ba ck
Instruction
fetch
Instruction
decode
Execution
Data
acc es s
sub $11, $2, $3
•
Reg
CC 4
CC 6
Write back
Representação de um ciclo com um diagrama single-cycle (ciclo 2)
sub $11, $2, $3
Instruction fetch
lw $10, 20($1)
Instruction decode
0
M
u
x
1
IF/ID
ID/EX
EX/MEM
MEM/WB
Add
dd
Add reA
sult
4
Shift
left 2
PC
Address
Instruction
memory
n
o
ic
t
ru
ts
n
I
Read
register 1
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
Write
data
0
M
u
x
1
Zero
ALU ALU
result
Address
Read
data
Data
memory
Write
data
16
Sign
extend
32
Clock 2
10
1
M
u
x
0
Pipelining
•
Unidade de controlo para suporte à execução em pipeline
•
Os sinais de controlo utilizados na versão do MIPS com pipeline são
idênticos aos da versão single-cycle
•
O registo PC e os registos da pipeline são escritos com novos valores a
cada ciclo.
•
A principal diferença consiste no facto de agora os sinais estarem
associados à fase em que são necessários. As primeiras duas fases (IF e
ID) são iguais para todas as instruções.
EXE
Instrução
RegDst
Tipo R
lw
sw
beq
•
1
0
X
X
MEM
ALU
op
10
00
00
01
WB
ALU
Mem Mem
Branch
Src
Read Write
0
0
0
0
1
0
1
0
1
0
0
1
0
1
0
0
Reg
Write
1
1
0
0
Memto
Reg
0
1
X
X
A informação de controlo é adicionada aos registos de pipeline , sendo
gerada na fase de descodificação e acompanha a execução da instrução
ao longo da pipeline.
WB
Instruction
IF/ID
Control
M
WB
EX
M
WB
ID/EX
EX/MEM
MEM/WB
11
Pipelining
•
Dependências de dados (anomalias)
•
A execução em pipeline gera problemas adicionais quando as instruções
dependem de resultados produzidos por instruções anteriores:
sub
and
or
add
sw
•
$2,
$12,
$13,
$14,
$15,
$1, $3
$2, $5
$6, $2
$2, $2
100($2)
As anomalias resultam facto das instruções seguintes efectuarem a
leitura do banco de registos antes da instrução escrever no registo:
CC 1
Value of
register $2: 10
sub $2, $1, $3
IM
and $12, $2, $5
CC 2
CC 3
CC 4
CC 5
CC 6
CC 7
CC 8
CC 9
10
10
10
10/– 20
– 20
– 20
– 20
– 20
Reg
IM
DM
Reg
IM
or $13, $6, $2
Reg
DM
DM
Reg
add $14, $2, $2
Reg
IM
DM
Reg
sw $15, 100($2)
IM
Reg
Reg
Reg
DM
Reg
•
As anomalias geradas pela leitura e escrita de um registo no mesmo
ciclo (p.ex. no ciclo 5) pode ser resolvidas ao nível do hardware se as
escritas em registos forem efectuadas na primeira metade do ciclo e as
leituras na segunda metade do ciclo.
•
Uma solução (pouco eficiente) para os restantes casos seria obrigar o
compilador a introduzir instruções de nop para eliminar as dependências.
sub
nop
nop
and
or
add
sw
$2, $1,
$12,
$13,
$14,
$15,
$3
$2, $5
$6, $2
$2, $2
100($2)
12
Pipelining
•
Resolução de dependências de dados (anomalias)
•
Detecção das dependências de dados – detecção dos casos em que o
registo destino numa instrução na fase de EX ou WB é utilizado como
uma das entradas da ALU (fase EX):
1a. EX/MEM.RegisterRd = ID/EX.RegisterRs
1b. EX/MEM.RegisterRd = ID/EX.RegisterRt
2a. MEM/WB.RegisterRd = ID/EX.RegisterRs
2b. MEM/WB.RegisterRd = ID/EX.RegisterRt
•
Encaminhamento de dados – Na maior parte das dependências de
dados o resultado já se encontra calculado (em EX/MEM ou MEM/WB)
só não foi ainda escrito no banco de registos. Assim é possível criar
atalhos no DP para encaminhar os dados e resolver as dependências.
CC 1
CC 2
CC 3
CC 4
CC 5
CC 6
CC 7
CC 8
CC 9
10
X
X
10
X
X
10
– 20
X
10/– 20
X
– 20
– 20
X
X
– 20
X
X
– 20
X
X
– 20
X
X
DM
Reg
Value of register $2 : 10
Value of EX/MEM : X
Value of MEM/WB : X
Pr ogram
execution or der
(in instructions)
sub $2, $1, $3
IM
Re g
and $12, $2, $5
or $13, $6, $2
IM
Reg
IM
DM
Reg
add $14, $2, $2
IM
sw $15, 100($2)
DM
Reg
IM
13
Reg
Re g
DM
Reg
Re g
DM
Re g
Pipelining
•
Resolução de dependências de dados com encaminhamento de dados
•
O DP para resolução de dependências dever ter a capacidade de
encaminhar para as entradas da ALU os valores em EX/MEM e
MEM/WB. Tal é conseguido através da introdução de multiplexers na
em cada entrada da ALU
ID/EX
EX/MEM
MEM/WB
M
u
x
Registers
For wardA
ALU
M
u
x
Rs
Rt
Rt
Rd
Data
memory
For wardB
M
u
x
EX/MEM.RegisterRd
Forwarding
unit
•
Só efectua o
encaminhamento
quando a instrução
escreve num registo e
esse registo não é $0
Quando
EX/MEM.registerRd =
EM/WB.registerRd
prefere o valor mais
recente (em EX/MEM).
exemplo:
add $1, $1, $2
add $1, $1, $3
add $1, $1, $4
M
u
x
MEM/WB.RegisterRd
As condições anteriormente indicadas não são suficientes porque
algumas instruções não escrevem nos registos ou escrevem em $0:
if (EX/MEM.RegWrite)
and (EX/MEM.RegisterRd≠0)
and (EX/MEM.RegisterRd = ID/EX.RegisterRs) ForwardA = 10
if (EX/MEM.RegWrite)
and (EX/MEM.RegisterRd≠0)
and (EX/MEM.RegisterRd = ID/EX.RegisterRt) ForwardB = 10
if (MEM/WB.RegWrite)
and (MEM/WB.RegisterRd≠0)
and (EX/MEM.registerRd≠ID/EX.RegisterRs)
and (MEM/WB.RegisterRd = ID/EX.RegisterRs) ForwardA = 01
if (MEM/WB.RegWrite)
and (MEM/WB.RegisterRd≠0)
and (EX/MEM.registerRd≠ID/EX.RegisterRt)
and (MEM/WB.RegisterRd = ID/EX.RegisterRt) ForwardB = 01
14
Pipelining
•
Resolução de dependências de dados: “empatar” a pipeline
•
A utilização do valor de um lw na instrução seguinte introduz uma
anomalia que não pode ser resolvida com atalhos.
Time (in clock cyc les)
Program
CC 1
execution
order
(in instructions)
lw $2, 20($1)
IM
and $4, $2, $5
CC 2
CC 3
Re g
IM
or $8, $2, $6
CC 4
CC 5
DM
Reg
Reg
DM
IM
IM
CC 7
DM
CC 9
Re g
Reg
slt $1, $6, $7
CC 8
Re g
Reg
add $9, $4, $2
•
CC 6
DM
IM
Re g
DM
Re g
Re g
Nos caso em que as anomalias não são resolvidas é necessário empatar a
pipeline até que o valor esteja disponível:
P ro g r am
T ime (i n c lo c k cy c le s)
e xe cu t ion
CC 1
CC 2
o rd e r
(i n i n s t ru c t i o n s )
lw $ 2, 2 0 ($ 1 )
IM
an d $ 4, $2, $5
or $ 8, $2, $6
CC 3
R eg
IM
Reg
CC 4
CC 5
DM
Re g
Re g
IM
IM
CC 6
CC 7
DM
Reg
Reg
DM
CC 8
CC 9
CC 10
Re g
bubble
ad d $ 9, $4, $2
IM
slt $ 1, $6 , $ 7
IM
15
DM
Re g
Reg
Reg
DM
R eg
Pipelining
•
Resolução de dependências de dados: “empatar” a pipeline
(continuação)
•
A condição em que é necessário empatar a pipeline é dada por:
if (ID/EX.MemRead) and
( (ID/EX.RegisterRt=IF/ID.RegisterRs)
or (ID/EX.RegisterRt = IF/ID.RegisterRt))
•
Esta condição pode ser implementada por uma nova unidade. Empatar a
pipeline é implementado através de uma sinal de não permite a escrita
nos registos PC, IF/ID e que insira um nop no estágio EX.
Controlar a escrita em PC e IF/ID
para “congelar” o valor dos registos
Unidade para detecção de situação em que é
necessário empatar a pipeline
ID /EX.Me mRead
Ha zard
detection
uni t
Inserção de nop no estágio EX
ID/EX
WB
C ontrol
0
M
u
x
IF /ID
PC
Instruct ion
memory
E X /M E M
M
WB
EX
M
MEM /WB
WB
M
u
x
n
o
tic
u
rt
s
n
I
Regist ers
A LU
Data
m em or y
M
u
x
IF/ID.Reg isterR s
IF/ID.Reg isterR t
IF/ID.Reg isterR t
Rt
IF/ID.Reg isterR d
Rd
ID /EX.R egisterRt
Rs
Rt
16
M
u
x
EX/MEM.RegisterRd
Forwarding
unit
MEM/WB.RegisterRd
M
u
x
Pipelining
•
Resolução de dependências controlo
•
Os saltos condicionais implicam uma penalização de 3 ciclos, uma vez
que o endereço de salto apenas é resolvido na fase MEM:
Ti me (in clock cycles)
Program
execu tion
CC 1
CC 2
order
(in instructions)
40 beq $1, $3, 7
IM
CC 3
CC 4
CC 5
DM
Reg
Reg
44 and $12, $2, $5
IM
Reg
48 or $13, $6, $2
DM
IM
CC 7
DM
Reg
72 lw $4 , 50($ 7)
IM
CC 8
CC 9
Reg
Reg
52 add $14, $2, $2
IF.Flush permite limpar o
registo IF/ID, inserindo um nop
CC 6
Reg
DM
Reg
Reg
DM
Reg
A penalização dos saltos pode ser reduzida a um ciclo
se a resolução dos saltos for efectuada na fase ID
IF.Flush
Hazard
detection
unit
ID/EX
M
u
x
WB
Control
0
M
u
x
IF/ID
4
WB
EX
M
MEM/WB
WB
Sh ift
left 2
Registers
PC
EX/ME M
M
Instruction
memory
M
u
x
=
ALU
M
u
x
Data
memory
M
u
x
Si gn
extend
M
u
x
Forwarding
unit
17
Pipelining
•
•
A previsão estática de saltos, por exemplo, prevendo que o salto não é
tomado pode ser implementada apenas adicionado lógica para eliminar
as instruções em IF, ID, EX (≈50% de previsões acertadas).
•
A previsão dinâmica de saltos baseada numa tabela com a história dos
saltos anteriores (≈90% de previsões acertadas).
•
Um bit por endereço de salto é pouco eficiente, uma vez que nos
ciclos for falha sempre duas vezes: na entrada (resultante da
última execução) e na saída.
•
Esquema com dois bit apenas altera a previsão quando erra duas
vezes, o que é mais eficiente:
Taken
Not taken
Predict
taken
Predict
taken
Taken
Not taken
Taken
Not taken
Predict
not taken
Taken
Predict
not taken
Not taken
•
A tabela com a história dos saltos contém o endereço da
instrução de salto e os bits correspondentes à informação sobre
os últimos saltos realizados
•
A previsão de saltos também requer uma tabela com os
endereços de salto tomados anteriormente, uma vez que o
endereço de salto só é calculado em EXE.
•
As duas tabelas têm uma implementação idêntica às caches e
podem-se juntar numa só:
PC
Pesquisa
Número de
entradas
na tabela
de história
de saltos
=
PC Previsto
Salto previsto como
tomado ou não
Não: a instrução não está prevista como sendo um salto.
Continuar normalmente
Sim: a instrução está prevista como sendo um salto. Utilizar PC previsto
18
Pipelining
•
•
Os saltos retardados, executam sempre a instrução seguinte ao salto.
a. From before
b. From target
sub $t4, $t5, $t6
add $s1, $s2, $s3
…
if $s2 = 0 then
add $s1, $s2, $s3
if $s1 = 0 then
add $s1, $s2, $s3
Delay slot
c. From fall through
Delay slot
if $s1 = 0 then
Delay slot
Becomes
Becomes
sub $t4, $t5, $t6
Becomes
add $s1, $s2, $s3
if $s1 = 0 then
if $s2 = 0 then
add $s1, $s2, $s3
add $s1, $s2, $s3
sub $t4, $t5, $t6
if $s1 = 0 then
sub $t4, $t5, $t6
•
•
Remove a penalização do salto sempre é encontrada uma instrução para
preencher o slot (≈50% dos casos).
•
Os saltos retardados são uma solução limitada porque a sua eficiência
diminui com a profundidade da pipeline e com a super-escalaridade.
Desempenho da pipeline com stalls
CPI pipeline = CPI Ideal + ciclos de stalls por instrução (CPI stalls)
Ganho =
•
Texecsem pipeline CPI ideal×# estágios × Tccsem pipeline
Texeccom pipeline (CPI ideal + CPI stalls ) × Tcc pipeline
=
# estágios
1 + CPI stalls
Exemplo: impacto da utilização de uma só porta para a memória
Máquina A – Memória dual port
Máquina B – Memória single port, relógio 1,05 vezes superior
40 % Loads
A Máquina B
Texec A
(1 + 0) × Tcc A
1× Tcc A × 1,05
GanhoB =
=
=
= 0,75 tem pior
Texec B (1 + 0,4 × 1) × Tcc B
1, 4 × Tcc A
desempenho!
19
Pipelining
•
Desempenho das variantes do processador MIPS
•
Tempos acesso às unidades funcionais:
Memória (Leitura ou escrita)
2 nanosegundos
•
Frequência
49%
22%
11%
16%
2%
Na versão com pipeline assume-se que 50% dos loads são utilizados na
instrução seguinte, e que 75% dos saltos são previstos de forma correcta.
Tipo de
Instrução
Tipo R
Load
Store
Branch
Jump
•
Banco de registos
1 nanosegundo
Qual a diferença de desempenho entre uma implementação com
pipelining, uma implementação multi-ciclo e uma implementação
single-cycle com ciclo de duração fixa para a seguinte mistura de
instruções:
Tipo de Instrução
Tipo R
Load
Store
Branch
Jump
•
ALU
2 nanosegundos
Busca da
instrução
2
2
2
2
2
Leitura de
registos
1
1
1
1
Operação
na ALU
2
2
2
2
Acesso à
Memória
2
2
Escrita em
registo
1
1
Total
6 ns
8 ns
7 ns
5 ns
Single-cycle
CPI=1
duração de cada ciclo (Tcc) = 8 ns
•
Multi-ciclo
CPI = 0,49 x 3 + 0,22 x 5 + 0,11 x 4 + 0,16 x 3 +0,02 x 2 = 2,21
Tcc = 2 ns
•
Pipeline
CPI load = 0,5 x 1 + 0,5 x 2 = 1,5 (50% originam stall)
CPI branch = 0,75 x 1 + 0,25 x 2 = 1,25 (25% de previsões erradas)
CPI = 0,49 x 1 + 0,22 x 1,5 + 0,11 x 1 + 0,16 x 1,25 + 0,02 x2 = 1,17
Tcc = 2 ns
Ganho Single-cycle/pipeline = #I x 1 x 8 / #I x 1,17 x 2 = 3,42x
Ganho Multi-ciclo/pipeline = 2,21 / 1,17 = 1,89x
20
Pipelining
Suporte a excepções
•
•
Quando ocorre uma excepção o controlo é transferido para o programa
no endereço de memória 0x4000040
•
É necessário “limpar” os registos da pipeline que contêm instruções
parcialmente executadas, posteriores à instrução onde ocorre a excepção.
•
O valor actual do PC deve ser guardado em EPC
•
DP para suporte a uma excepção aritmética (por exemplo em add):
Permite saltar para o
endereço 0x400 00040
“Limpar” os registos
IF/ID, ID/EX e EX/MEM
IF.Fl ush
Guarda o endereço da instrução
em execução em EPC
EX.Flush
ID.Flush
Hazard
detecti on
unit
40000040
ID /EX
M
u
x
WB
C ontrol
0
M
u
x
0
M
u
x
M
0
EX
IF/ID
EX/MEM
M
u
x
Cause
WB
MEM/WB
M
WB
Except
PC
4
Shift
left 2
R egister s
PC
Ins truc tion
memory
M
u
x
=
ALU
Data
memory
M
u
x
M
u
x
Sign
extend
M
u
x
Forwar ding
unit
•
O tratamento de excepções é complexo, uma vez que estas podem
ocorrer em vários estágios simultaneamente, obrigando a um esquema
de prioridades
•
Algumas arquitecturas implementam excepções imprecisas, onde o EPC
pode não indicar exactamente a instrução que provocou a excepção,
deixando essa responsabilidade ao sistema operativo
21
Bibliografia
•
Secções 6.1, 6.2, 6.3, 6.4, 6.5, 6.6, 6.7 de Computer Organization and
Design: the hardware/software interface, D. Patterson and J. Hennessy,
Morgan Kaufmann, 2ª edição, 1998.
•
Adicional:
•
Secções 3.1, 3.2, 3.3, 3.4, 3.5, 3.6 de Computer Architecture: A Quantitative
Approach, J. Hennessy and D. Patterson, Morgan Kaufmann, 2ª edição, 1996.
22

Pipelining - Universidade do Minho

Transcrição

Documentos relacionados

NYCO 1.100 - Interfire

premium 20 - Interfire

Gränsfors Bruk Scandinavian Forest Axe

rescue life manual and semiautomatic defibrillators

CamelBak Armorbak Hydration Pack.

Saídas Terça-Feira e Domingo em Vuelo Especial

AFr PPH SValentim Cartaz Menu A4

Informativo de Janeiro de 2008

Condomínio Pedra de Itaúna - COA-RJ

regenerador reg 1 para banho de nitretação