Pipeline
Vídeo da aula estará disponível em breve
A Analogia da Lavanderia
Imagine que você precisa lavar 4 cargas de roupa. Cada carga passa por 4 etapas: lavar (30 min), secar (30 min), dobrar (30 min), guardar (30 min). Sem pipeline, você completa uma carga antes de começar a outra: 4 × 120 min = 480 min. Com pipeline, assim que a primeira carga sai da lavadora, a segunda entra — e todas as etapas operam em paralelo.
Diagrama — Lavanderia com Pipeline
Sem pipeline (sequencial):
Tempo: 30 60 90 120 150 180 210 240 270 300 330 360 ...480
Carga A: [Lavar][Secar][Dobrar][Guard]
Carga B: [Lavar][Secar][Dobrar][Guard]
Carga C: [...]
Total: 4 × 120 = 480 minutos
Com pipeline:
Tempo: 30 60 90 120 150 180 210
Carga A: [Lavar][Secar][Dobrar][Guard]
Carga B: [Lavar][Secar][Dobrar][Guard]
Carga C: [Lavar][Secar][Dobrar][Guard]
Carga D: [Lavar][Secar][Dobrar][Guard]
Total: 120 + 3 × 30 = 210 minutos
Speedup = 480 / 210 ≈ 2.3×
Speedup ideal (com muitas cargas) → 4× (número de estágios)Pipeline não acelera cada instrução individual — cada carga ainda leva 120 min. Pipeline aumenta o throughput: o número de instruções completadas por unidade de tempo.
Os 5 Estágios do Pipeline MIPS
O processador MIPS divide a execução de cada instrução em 5 estágios, cada um usando uma parte diferente do datapath:
Estágios do Pipeline MIPS
Estágio Nome O que faz
─────── ─────────────────────── ──────────────────────────────────────────
IF Instruction Fetch Busca a instrução na memória de instruções
usando o PC. Atualiza PC ← PC + 4.
ID Instruction Decode / Decodifica o opcode, lê registradores
Register Read rs e rt do banco, estende o sinal do
imediato. Gera sinais de controle.
EX Execute / Address Calc ULA executa a operação:
- R-type: operação aritmética/lógica
- lw/sw: calcula endereço (base + offset)
- beq: calcula se branch é tomado
MEM Memory Access Acessa memória de dados:
- lw: lê da memória
- sw: escreve na memória
- R-type/beq: não faz nada (passa reto)
WB Write Back Escreve resultado no banco de registradores:
- R-type: resultado da ULA
- lw: dado lido da memória
- sw/beq: não escreve (RegWrite=0)
Registradores de pipeline entre estágios:
IF/ID → ID/EX → EX/MEM → MEM/WB
Armazenam dados e sinais de controle entre ciclos.Diagrama — Pipeline Timing (5 instruções)
Ciclo: 1 2 3 4 5 6 7 8 9
───── ───── ───── ───── ───── ───── ───── ───── ─────
Instr 1: [IF ][ID ][EX ][MEM ][WB ]
Instr 2: [IF ][ID ][EX ][MEM ][WB ]
Instr 3: [IF ][ID ][EX ][MEM ][WB ]
Instr 4: [IF ][ID ][EX ][MEM ][WB ]
Instr 5: [IF ][ID ][EX ][MEM ][WB ]
Sem pipeline: 5 instruções × 5 ciclos = 25 ciclos
Com pipeline: 5 + 4 = 9 ciclos (5 para completar a 1ª + 1 por instrução)
Speedup = 25 / 9 ≈ 2.8×
Com N instruções: speedup → 5× (número de estágios) quando N → ∞
Em cada ciclo, até 5 instruções estão em execução simultânea,
cada uma em um estágio diferente do pipeline.
Speedup ideal vs real
O speedup ideal de um pipeline de k estágios é k (5x no MIPS). Na prática, o speedup é menor por causa de: (1) estágios desbalanceados (o mais lento determina o ciclo), (2) overhead dos registradores de pipeline, e (3) hazards que forçam stalls ou flushes. Pipeline real do MIPS: speedup de ~3-4x em vez de 5x.
Hazards: Problemas no Pipeline
Um hazard é uma situação em que a próxima instrução não pode ser executada no ciclo seguinte. Existem três tipos:
Hazard Estrutural
Ocorre quando dois estágios precisam do mesmo recurso hardware no mesmo ciclo. Exemplo clássico: uma única memória para instruções e dados. Se a instrução no estágio IF precisa ler uma instrução da memória ao mesmo tempo que a instrução no estágio MEM precisa ler/escrever dados, há conflito.
Solução no MIPS: memórias separadas para instruções e dados (arquitetura Harvard modificada). Na prática, caches L1 separadas (I-cache e D-cache).
Hazard de Dados
Ocorre quando uma instrução depende do resultado de uma instrução anterior que ainda não completou o pipeline.
Assembly MIPS
# Exemplo de Data Hazard (RAW — Read After Write)
add $s0, $t0, $t1 # escreve em $s0 no estágio WB (ciclo 5)
sub $t2, $s0, $t3 # lê $s0 no estágio ID (ciclo 3!) — valor errado!
Ciclo: 1 2 3 4 5
───── ───── ───── ───── ─────
add $s0: [IF ][ID ][EX ][MEM ][WB ] ← $s0 escrito aqui
sub $t2: [IF ][ID ][EX ][MEM ]
↑
sub lê $s0 aqui — mas add
ainda não escreveu o resultado!
Tipos de Data Hazard:
RAW (Read After Write): instrução lê antes da anterior escrever
— O MAIS COMUM, resolvido com forwarding
WAR (Write After Read): instrução escreve antes da anterior ler
— raro no pipeline MIPS de 5 estágios
WAW (Write After Write): duas instruções escrevem no mesmo registrador
— raro no pipeline MIPS (WB sempre em ordem)Hazard de Controle
Ocorre em instruções de branch (beq, bne). O processador precisa buscar a próxima instrução (IF) antes de saber se o branch será tomado (decidido no estágio EX ou MEM).
Assembly MIPS
# Hazard de Controle
beq $s0, $s1, L1 # decisão do branch no estágio EX (ciclo 3)
add $t0, $t1, $t2 # esta instrução já foi buscada no ciclo 2
sub $t3, $t4, $t5 # e esta no ciclo 3
L1: or $t6, $t7, $t8 # mas se branch é tomado, deveria executar aqui
Ciclo: 1 2 3 4 5
───── ───── ───── ───── ─────
beq: [IF ][ID ][EX ] ← branch decidido aqui
add: [IF ][ID ] ← já no pipeline! Se branch tomado,
sub: [IF ] estas instruções são INVÁLIDAS
Se o branch é tomado, as instruções add e sub precisam ser
"canceladas" (flushed) do pipeline. Ciclos desperdiçados = penalidade.Resolvendo Hazards de Dados: Forwarding
Forwarding (ou bypassing) é a técnica de passar o resultado de um estágio diretamente para a entrada de outro, sem esperar o estágio WB. O resultado é "encaminhado" assim que fica disponível.
Diagrama — Forwarding
Sem forwarding (stall necessário):
Ciclo: 1 2 3 4 5 6 7
───── ───── ───── ───── ───── ───── ─────
add $s0: [IF ][ID ][EX ][MEM ][WB ]
sub $t2: [IF ][stall][stall][ID ][EX ][MEM ]
↑
só pode ler $s0 depois do WB de add
Com forwarding:
Ciclo: 1 2 3 4 5
───── ───── ───── ───── ─────
add $s0: [IF ][ID ][EX ][MEM ][WB ]
sub $t2: [IF ][ID ][EX ][MEM ]
↑
resultado de add disponível na saída EX (ciclo 3)
forwarding envia direto para entrada EX de sub (ciclo 4)
O forwarding elimina stalls em MUITOS casos, mas não todos.Quando Forwarding Não Resolve: Load-Use Hazard
Assembly MIPS
# Load-Use Hazard — forwarding insuficiente
lw $s0, 0($t0) # $s0 disponível após MEM (ciclo 4)
add $t2, $s0, $t3 # precisa de $s0 no EX (ciclo 4) — conflito!
Ciclo: 1 2 3 4 5 6
───── ───── ───── ───── ───── ─────
lw $s0: [IF ][ID ][EX ][MEM ][WB ]
add $t2: [IF ][ID ][stall][EX ][MEM ]
↑
1 ciclo de stall inevitável
(resultado do lw só sai de MEM no ciclo 4,
mas add precisa no início do EX no ciclo 4)
Após o stall, forwarding de MEM/WB → EX resolve.
O compilador pode ajudar reordenando instruções para
preencher o "slot" do stall com algo útil.Resolvendo Hazards de Controle: Branch Prediction
Para minimizar a penalidade de branches, processadores usam branch prediction — tentam adivinhar se o branch será tomado antes de saber a resposta.
Estratégias de Branch Prediction
Predição Estática:
- Always Not Taken: assume que branch nunca é tomado
→ Continua executando sequencialmente
→ Se branch é tomado: flush e recomeça (penalidade)
→ Acerto: ~50-60% (loops sempre erram na última iteração)
- Always Taken: assume que branch sempre é tomado
→ Útil para loops (que geralmente repetem)
→ Acerto: ~60-70%
- BTFN (Backward Taken, Forward Not Taken):
→ Branches para trás (loops): prediz tomado
→ Branches para frente (if/else): prediz não tomado
→ Acerto: ~65-75%
Predição Dinâmica:
- 1-bit predictor: lembra a última decisão do branch
→ Falha 2× por loop (entrada e saída)
- 2-bit predictor (saturating counter):
→ Estados: Strongly Not Taken → Weakly Not Taken →
Weakly Taken → Strongly Taken
→ Precisa errar 2× consecutivas para mudar predição
→ Acerto: ~85-95%
- Processadores modernos (correlating, tournament, TAGE):
→ Combinam histórico local + global
→ Acerto: >95% em código real
Branch Target Buffer (BTB):
Cache que armazena endereço destino de branches anteriores.
Permite buscar instrução do destino antes mesmo de decodificar.
Delayed Branch no MIPS
O MIPS original usa uma técnica chamada delayed branch: a instrução logo após o branch (o "branch delay slot") é sempre executada, independentemente do branch ser tomado ou não. O compilador tenta colocar algo útil nesse slot. Se não encontrar, coloca um
nop. Processadores modernos abandonaram essa técnica em favor de prediction dinâmica.
Impacto Real do Pipeline
Cálculo de Desempenho
CPI (Cycles Per Instruction) no pipeline ideal: 1.0
(Uma instrução completada por ciclo, após preencher o pipeline)
CPI real = CPI_ideal + stalls_por_hazard_dados + stalls_por_hazard_controle
Exemplo:
- 30% das instruções são lw seguidas de uso imediato → 0.30 × 1 = 0.30 stalls
- 15% são branches, predição acerta 85%, penalidade = 2 ciclos
→ 0.15 × 0.15 × 2 = 0.045 stalls
CPI = 1.0 + 0.30 + 0.045 = 1.345
Speedup vs monociclo (5 ciclos por instrução):
Speedup = 5 / 1.345 ≈ 3.7×
Para melhorar:
- Compilador: reordenar instruções para evitar load-use hazards
- Hardware: melhor branch prediction, mais forwarding paths
- Arquitetura: superpipeline (mais estágios), superscalar (múltiplos pipes)No harness.os
Pipeline no processador é paralelismo temporal — múltiplas instruções em diferentes estágios simultaneamente. O harness.os usa o mesmo princípio: diferentes sessões podem estar em diferentes fases do workflow ao mesmo tempo.
Mapeamento: Pipeline → harness.os
Pipeline MIPS harness.os
───────────────────────────── ──────────────────────────────────────
5 estágios (IF/ID/EX/MEM/WB) 5 fases de sessão: start → load context
→ execute → log results → end session
Paralelismo temporal Múltiplas sessões no mesh:
Instrução 1 em WB enquanto Sessão A fazendo deploy enquanto
instrução 5 em IF Sessão B fazendo QA
Data Hazard (dependência) Dependência entre sessões:
add $s0 → sub $s0 Sessão de QA depende do resultado
da sessão de build
Forwarding Handoff mechanism:
Resultado direto sem WB end_session passa contexto direto
para start_session da próxima
Branch Prediction Workflow prediction:
Adivinhar caminho antes de Pré-carregar rules e knowledge
saber resultado antes de saber a tarefa exata
Stall (bubble) Session blocking:
Pipeline para e espera Sessão espera por input do usuário
ou resultado de outra sessãoHomework
- Dado o código abaixo, identifique todos os hazards e diga como cada um é resolvido (forwarding, stall ou ambos):
Assembly MIPS
lw $t0, 0($s0) add $t1, $t0, $t2 sw $t1, 4($s0) beq $t1, $zero, L1 sub $t3, $t1, $t4 - Um pipeline tem 8 estágios e executa 1000 instruções. Qual o speedup vs um processador monociclo de 8 ciclos por instrução? Assuma CPI ideal (sem hazards).
- Explique por que o branch prediction de 2 bits é melhor que o de 1 bit para loops. Quantas vezes cada um erra em um loop de 10 iterações?
- No harness.os, o mecanismo de handoff entre sessões é análogo ao forwarding. Explique: o que acontece se uma sessão não escreve um handoff adequado? Como isso se compara a um stall no pipeline?
Resumo
- Pipeline aumenta throughput (instruções/ciclo), não latência de instrução individual
- O MIPS usa 5 estágios: IF, ID, EX, MEM, WB — speedup ideal de 5x
- Hazards estruturais: resolvidos com hardware duplicado (memórias separadas)
- Hazards de dados (RAW): resolvidos com forwarding; load-use requer 1 stall
- Hazards de controle: resolvidos com branch prediction (estática ou dinâmica)
- CPI real = 1 + stalls por hazards; speedup real: ~3-4x no MIPS de 5 estágios
- Processadores modernos: pipelines de 14-20+ estágios, superscalar, prediction >95%
Verifique seu entendimento
O que é forwarding (bypassing) no contexto de um pipeline?