Tema 2 - Parte 2 - MIPS Pipeline - Conflitos

Prévia do material em texto

Tema 2 – Parte 2
MIPS pipeline: conflitos na execução em pipeline.
Prof. Luciano Agostini, Marcelo Porto e Bruno Zatt
{agostini, porto, zatt}@inf.ufpel.edu.br
Universidade Federal de Pelotas
Centro de Desenvolvimento Tecnológico
Programa de Pós-Graduação em Computação
Arquiteturas de Computadores
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 2 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
“Existem situações de execução no pipeline em que a 
instrução seguinte não pode ser executada no próximo ciclo 
de relógio. Tais situações são chamadas de conflitos.”
Tipos de Conflitos:
❑ Estruturais
❑ De controle
❑ De dados
Os Conflitos do Pipeline
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 3 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
O Hardware não pode suportar a combinação de instruções 
que o pipeline deseja executar em um dado ciclo de relógio.
• O conjunto de instruções do MIPS foi projetado para executar 
em pipeline (é muito fácil evitar conflitos estruturais quando 
do desenho do pipeline)
• Mas se houvesse somente uma memória (para dados e 
instruções), se uma instrução tentasse acessar um dado na 
memória enquanto tivesse que ser buscada uma nova 
instrução, ocorreria um conflito estrutural. 
Conflitos Estruturais (Structural Hazards)
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 4 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
• Originam-se na necessidade de se tomar uma decisão 
baseada nos resultados de uma instrução, a qual ainda 
não foi concluída.
• Muito comuns em instruções de salto condicional (beq, 
no caso do MIPS reduzido)
• Uma possível solução é a parada (também chamada de
“bolha”), ou seja, interromper a progressão das 
instruções pelo pipeline.
Conflitos de Controle (Control Hazards)
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 5 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
Exemplo 3: analisar o efeito da parada no desempenho do 
desvio condicional.
Considere que se tenha hardware extra que permita testar registradores, calcular 
o endereço de desvio condicional e atualizar o PC, tudo isso no segundo estágio.
add $4, $5, $6
beq $1, $2, 40
Ordem de
execução
do programa
(em instruções)
lw $3, 300($0)
Tempo 2 4 6 8 10 12 14 16 18
2 ns
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg4 ns
2 ns 2 ns 2 ns 2 ns 2 ns
Conflitos de Controle: parada
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 6 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
Se for necessário resolver o desvio condicional em um estágio 
posterior ao segundo (o que ocorre na maioria dos processadores 
reais), ocorrerá uma perda maior de desempenho em função da 
necessidade de encher novamente o pipeline
add $4, $5, $6
beq $1, $2, 40
Ordem de
execução
do programa
(em instruções)
lw $3, 300($0)
Tempo 2 4 6 8 10 12 14 16 18
2 ns
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
6 ns
2 ns 2 ns 2 ns 2 ns 2 ns
pipeline esvaziando
Conflitos de Controle: parada
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 7 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
Outra solução é a Predição:
• É a técnica geralmente adotada nos processadores reais!
• Um esquema simples de predição é assumir que os desvios 
condicionais sempre irão falhar. 
– Se acertar, o pipeline prossegue com velocidade máxima
– Se errar, será neccesário atrasar o avanço das instruções pelo 
pipeline
Conflitos de Controle: predição estática
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 8 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
add $4, $5, $6
beq $1, $2, 40
Ordem de
execução
do programa
(em instruções)
lw $3, 300($0)
Tempo 2 4 6 8 10 12 14 16 18
2 ns
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
2 ns
add $4, $5, $6
beq $1, $2, 40
Ordem de
execução
do programa
(em instruções)
or $7, $8, $9
Tempo 2 4 6 8 10 12 14 16 18
2 ns
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg4 ns
bolha bolha bolha bolha bolha
Quando o
desvio condicional 
não se realiza
Quando o
desvio condicional 
se realiza
Conflitos de Controle: predição estática
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 9 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
• Outro esquema mais sofisticado de predição reside em se 
considerar parte dos desvios se realizando e parte não se 
realizando
• Exemplo de uso prático: nos loops a última instrução é 
sempre um desvio para um endereço anterior, que na 
maioria das vezes, se concretiza
• Dada a grande probabilidade de se realizarem, podemos 
predizer que os desvios para endereços anteriores sempre 
se realizam…
Conflitos de Controle: predição estática
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 10 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
• Predição dinâmica realiza a predição em função do comportamento 
anterior de cada desvio
• Podem mudar a predição para um mesmo desvio com o decorrer da 
execução do programa
• Um esquema comum é manter uma história para cada desvio 
realizado ou não-realizado
• Preditores dinâmicos são implementados em hardware e apresentam 
até 90% de acerto
• Quando o palpite estiver errado, o controle do pipeline precisa 
assegurar que as instruções seguintes ao desvio não terão influência 
na execução futura 
Conflitos de Controle: predição dinâmica
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 11 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
• Decisão retardada consiste em escolher uma instrução para ser 
executada logo após a instrução de desvio, de modo a manter o 
pipeline preenchido
add $4, $5, $6
beq $1, $2, 40
Ordem de
execução
do programa
(em instruções)
lw $3, 300($0)
Tempo 2 4 6 8 10 12 14 16 18
2 ns
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg4 ns
add $4, $5, $6
beq $1, $2, 40
Ordem de
execução
do programa
(em instruções)
lw $3, 300($0)
Tempo 2 4 6 8 10 12 14 16 18
2 ns
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
2 ns
original
Slot do desvio retardado
Conflitos de Controle: delayed branch
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 12 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
add $s0, $t0, $t1
sub $t2, $s0, $t3
• A execução de uma instrução depende do resultado de 
outra, a qual ainda está no pipeline. 
• Exemplo:
add $s0, $t0, $t1
Ordem de
execução
do programa
(em instruções)
sub $t2, $s0, $t3
Tempo 2 4 6 8 10 12 14 16 18
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
Busca da
instrução
Acesso
ao Dado
ULAReg Reg
bolha bolha bolha bolha bolha
bolha bolha bolha bolha bolha
bolha bolha bolha bolha bolha
Conflitos de Dados (Data Hazards)
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 13 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
• Passar para o compilador a solução deste tipo de conflito é 
inviável, pois este tipo de conflito é muito frequente
• Solução: não é preciso esperar pelo término de uma 
instrução aritmética/lógica
• Tão logo a ULA chegue ao resultado da operação, este 
resultado pode ser disponibilizado para as instruções quevem a seguir
• Esta técnica é chamada de adiantamento (forwarding ou 
bypass)
Conflitos de Dados: adiantamento
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 14 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
Exemplo 4: considerando as duas instruções citadas 
anteriormente, mostre as conexões necessárias entre os estágios 
do pipeline de modo a tornar viável o adiantamento.
Conflitos de Dados: adiantamento
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 15 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
Estágios:
BI: busca de instrução (memória de instruções)
DI: decodificação da instrução e leitura do banco de registradores (banco de 
registradores sendo lido)
EX: estágio de execução da instrução (ULA)
MEM: acesso à memória (memória de dados)
ER: escrita do resultado no banco de registradores (banco de registradores 
sendo escrito)
EX MEM ERDIBIadd $s0, $t0, $t1
Tempo 2 4 6 8 10
Representação Gráfica do Pipeline de Instrução
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 16 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
EX MEM ERDIBIadd $s0, $t0, $t1
Leitura do banco 
de registradores
Escrita no banco 
de registradores
Memória de 
dados não é 
acessada
Representação Gráfica do Pipeline de Instrução
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 17 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
Solução do Exemplo 4: conexão entre a saída da ULA e a 
entrada da própria ULA
EX MEM ERDIBIadd $s0, $t0, $t1
sub $t2, $s0, $t1
Ordem de
execução
do programa
(em instruções)
Tempo 2 4 6 8 10
EX MEM ERDIBI EX
Resultado: não haverá bolha!
Só pode haver caminho para adiantamento se o estágio-destino for 
posterior no tempo ao estágio-fonte
Conflitos de Dados: adiantamento
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 18 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
Exemplo 5: adiantamento envolvendo instrução lw
Resultado: mesmo com adiantamento, haverá a perda de um 
ciclo de relógio (a bolha inevitável)
Conflitos de Dados: adiantamento
lw $s0, 20($t1)
sub $t2, $s0, $t3
Ordem de
execução
do programa
(em instruções)
Tempo 2 4 6 8 10
EX MEM ERDIBI EX
bolha bolha bolha bolha bolha
EX ERDIBI MEM
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 19 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
# reg $t1 possui o endereco de v[k]
lw $t0, 0($t1) # reg $t0 (temp) = v[k]
lw $t2, 4($t1) # reg $t2 = v[k+1]
sw $t2, 0($t1) # v[k] = reg $t2
sw $t0, 4($t1) # v[k+1] = reg $t0 (temp)
Exemplo 6: encontre o conflito existente no código do 
procedimento swap, abaixo.
Conflitos de Dados: reordenação do código
O conflito aparece no registrador $t2, entre a 2a e a 3a linhas. 
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 20 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
Exemplo 7: reordene as instruções de modo a evitar a parada 
no pipeline devido ao conflito de dados
Conflitos de Dados: reordenação do código
# reg $t1 possui o endereço de v[k]
lw $t0, 0($t1) # reg $t0 (temp) = v[k]
lw $t2, 4($t1) # reg $t2 = v[k+1]
sw $t2, 0($t1) # v[k] = reg $t2
sw $t0, 4($t1) # v[k+1] = reg $t0 (temp)
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 21 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
Exemplo 7: reordene as instruções de modo a evitar a parada 
no pipeline devido ao conflito de dados
Solução: intercambiar as duas últimas instruções de sw.
# reg $t1 possui o endereco de v[k]
lw $t0, 0($t1) # reg $t0 (temp) = v[k]
lw $t2, 4($t1) # reg $t2 = v[k+1]
sw $t0, 4($t1) # v[k+1] = reg $t0 (temp)
sw $t2, 0($t1) # v[k] = reg $t2
Note que nenhum novo conflito foi criado!
Conflitos de Dados: reordenação do código
2. Organizações do MIPS: pipeline
PPGC UFPel: Arquitetura de Computadores Slide 22 Profs. Luciano Agostini, Marcelo Porto e Bruno Zatt
Bibliografia recomendada
• PATTERSON, David A.; HENESSY, John L. Organização e 
Projeto de Computadores: a interface hardware/software. 
2ª.ed. Rio de Janeiro: LTC, 2000.