Processo de Pipelining (exemplo da lavanderia)
• Ana, Bruno, Carla, Luiz
têm roupas sujas a serem lavadas,
secadas, dobradas e guardadas
• Lavadora leva 30 minutos
• Secadora leva 30 minutos
• “Dobrar” leva 30 minutos
• “Guardar” leva 30 minutos
A B C D
Pipelining (exemplo da lavanderia)
6 PM
O
r
d
e
m
T
a
r
e
f
a
s
8
7
30
30
30
30
30
30
30
30
12
11
10
9
30
30
30
30
2 AM
1
30
30
30
30
Tempo
A
B
C
D
• Processo seqüencial de lavagem leva oito horas para os quatro (2 para cada)
• Quanto tempo levaria, utilizando-se pipelining
?
Pipelining (exemplo da lavanderia)
6 PM
8
7
30
30
30
30
10
9
30
11
12
1
2 AM
Tempo
30
30
A
B
C
D
• Utilizando-se a técnica de pipeline consome-se 3,5
horas no processo de lavagem !
Observações sobre Pipelining
6 PM
8
7
30
30
30
30
9
30
A
30
30
• Pipelining não ajuda a melhorar a latência
10
de uma atividade, mas aumenta o
throughput (total)
• Várias tarefas operando em paralelo
utilizam recursos diversos
• Aceleração potencial = Número de
estágios de pipe (ex: 4)
• Taxa de pipeline limitada pelo estágio mais
lento (ex: se lavar demora mais que as
outras tarefas)
B
C
D
• Desequilíbrios na duração dos estágios
reduz a aceleração
Pipe cheio
• Tempo para “encher” o pipeline e para
“esvaziá-lo”reduz a aceleração
• Pode parar por dependências entre as
tarefas
BI: Busca da
instrução
DI: Decodificação/
Leitura do banco de
registradores
BI
EX: Execução/
Cálculo do endereço
DI
MEM: Acesso à
memória
EX
ER: Escrita no banco
de registradores
MEM
ER
M
U
X
1
Somador
UAL
Reg a ser
lido # 1
P
C
Endereço de
leitura
Instrução
M
U
X
Memória de
Instruções
3
Reg a ser
lido #2
Dado
lido #1
Reg a ser
escrito
Dado
lido #2
Dado de
escrita
EscReg
16
Extensão
de sinal
32
EscMen
M
U
X
UAL
Endereço
Dado
lido
Dado a ser
escrito
LerMem
M
U
X
Os Cinco Estágios da Instrução de Carga
• Busca: Busca da instrução na memória de instruções
• Reg/Dec: Decodificação da Instrução e Leitura do(s)
registrador(es) e
• UAL: Calcula o endereço da memória de dados
• Mem: Lê dado da memória de dados
• Reg: Escreve o dado no banco de registradores
Ciclo 1 Ciclo 2
Carga
Busca Reg/Dec
Ciclo 3 Ciclo 4 Ciclo 5
UAL
Mem
Reg
Pipelining
Tempo
2
Busca
Reg
4
6
8
UAL
Acesso
Dados
Reg
Busca
8ns
Reg
Busca
2
4
Reg
Busca
6
UAL
Reg
10
8
Acesso
Dados
UAL
Busca
Tempo para executar 3 instruções = 13ns
Acesso
Dados
8ns
Tempo para executar 3 instruções = 24ns
Tempo
UAL
Reg
12
Reg
Acesso
Dados
UAL
Reg
Acesso
Dados
Reg
14
Reg
Monociclos vs. Pipeline
Implementação Monociclo: cada instrução em um ciclo
Ciclo 1
Ciclo2
Clk
Load
Store
Waste
Implementação Pipeline:
Ciclo 1 Ciclo 2 Ciclo 3 Ciclo 4 Ciclo 5 Ciclo 6 Ciclo 7 Ciclo 8 Ciclo 9 Ciclo 10
Clk
Load
Busca
Reg
Exec
Mem
Escr
Store
Busca
Reg
Exec
Mem
Reg
Exec
Tipo R Busca
Mem
Escr
Por que utilizar Pipeline?
• Suponha que vão ser executadas 100 instruções
• Máquina monociclo
–1 ciclo de relógio tem duração de 45 ns
–Cada instrução demora 1 ciclo (ciclo grande para
possibilitar executar qualquer instrução)
–Tempo total: 1 ciclo x 100 inst = 45ns x 100 = 4500 ns
• Máquina ideal pipelined
– 1 ciclo de relógio tem duração de 10 ns (ciclo tem
tempo igual ao tempo do elemento mais lento)
– cada estágio de pipeline utiliza um ciclo de relógio
(são 5 estágios no total)
–Tempo total: 5  1 ciclo + (1 ciclo  (100 inst -1)) =
10 ns x 99 + 50 ns = 1040 ns
Monociclos vs. Pipeline
Implementação Pipeline:
Ciclo 1 Ciclo 2 Ciclo 3 Ciclo 4 Ciclo 5 Ciclo 6 Ciclo 7 Ciclo 8 Ciclo 9 Ciclo 10
Clk
Busca
Reg
Exec
Mem
Escr
Busca
Reg
Exec
Mem
Escr
Busca
Reg
Exec
Mem
5 ciclos
+
Escr
1 ciclo por instrução
(descontando a primeira instrução que
dura 5 ciclos)
Representação Gráfica de Pipeline
Tempo em ciclos de clock
Ordem de
execução
das
instruções
lw
lw
lw
C1
C2
MI
Reg
MI
C3
C4
C5
UAL
MD
Reg
UAL
MD
Reg
UAL
MD
Reg
MI
Reg
C6
C7
Reg
Lendo
Escrevendo
Pipeline – Recursos Disponíveis
Tempo em ciclos de clock
C1
C2
MI
Reg
MI
C3
C4
C5
UAL
MD
Reg
UAL
MD
Reg
UAL
MD
Reg
UAL
MD
Reg
UAL
MD
Reg
MI
Reg
MI
A partir da instrução 5,
temos ocupação máxima do
processador
Reg
MI
C6
Reg
C7
C8
C9
Reg
Conflitos do Pipeline: Conflito Estrutural
Conflitos estruturais:
• Tentativa de utilizar o mesmo recurso de modos
diferentes e ao mesmo tempo
Ex da lavadora:
–Lavar e secar utilizando a mesma máquina
–Pessoa que dobra roupa já está ocupada
guardando roupa
–Sem duas memórias, não poderia ter acesso à
instrução simultaneamente com dados
Conflitos do Pipeline: Conflito Estrutural
Tempo em ciclos de clock
C1
C2
MI
Reg
MI
C3
C4
C5
UAL
MD
Reg
UAL
MD
Reg
UAL
MD
Reg
UAL
MD
Reg
UAL
MD
Reg
MI
Reg
MI
Reg
MI
Detecção fácil neste caso!
C6
Reg
C7
C8
C9
Reg
Conflitos do Pipeline: Conflito de Controle
Conflitos de controle:
• Tentativa de tomar uma decisão antes que a condição
seja avaliada
Ex da lavanderia:
–Para lavar uniformes precisa saber quantidade de
sabão;
–Precisa esperar a secadora ficar disponível para
colocar próximo uniforme
–Instruções de desvio
Soluções para Conflito de Controle
Tempo em ciclos de clock
C1
C2
MI
Reg
C3
C4
C5
UAL
MD
Reg
UAL
MD
C6
C7
C8
C9
Add
Beq
MI
Reg
Load
Parada: espera até a decisão estar clara
MI
Reg
Reg
UAL
MD
Reg
Soluções para Conflito de Controle
Tempo em ciclos de clock
C1
C2
MI
Reg
C3
C4
C5
C6
UAL
MD
Reg
UAL
MD
Reg
UAL
MD
C7
Add
Beq
Load
MI
Reg
MI
Reg
Predição: Escolhe uma direção e
retorna se não for a direção correta.
50% mais rápido se der certo
Reg
C8
C9
Conflitos do Pipeline: Conflito de Dados
Conflitos de dados:
• Tentativa de utilizar um item antes de estar pronto
Ex da lavanderia:
–Uma meia na secadora outra na lavadora; não
pode dobrar
–Instrução depende de resultado da instrução
anterior ainda no pipeline
Ex: add r2 r3 r1
addi r1 r4 100
Solução para Conflito por Dados
Tempo em ciclos de clock
Add r2 r3 r1
Addi r1 r4 100
C1
C2
MI
Reg
MI
C3
C4
C5
UAL
MD
Reg
UAL
MD
Reg
C6
Reg
C7
Conflitos do Pipeline: Conflito Estrutural
Tempo em ciclos de clock
Add r2 r3 r1
Addi r1 r4 100
C1
C2
MI
Reg
MI
C3
C4
C5
UAL
MD
Reg
UAL
MD
Reg
Adiantamento: Adianta o resultado de um estágio
para o outro
C6
Reg
C7