Capítulo 4 - O Processador

Rodolfo Azevedo - rodolfo.azevedo@unicamp.br

http://www.ic.unicamp.br/~rodolfo/mc732

Introdução

• Desempenho da CPU depende de três fatores:
• Contagem de instruções (IC) — determinada pelo ISA e compilador
• CPI (ciclos por instrução) — determinada pelo hardware
• Tempo de ciclo — determinado pelo hardware

\[\text{Tempo de CPU} = \text{IC} \times \text{CPI} \times T_{ciclo}\]

• Duas implementações RISC-V neste capítulo:
• Versão simplificada de ciclo único
• Versão com pipeline

Subconjunto de Instruções

• Trabalharemos com um subconjunto representativo do RISC-V:
• Memória: ld, sd
• Aritmética/lógica: add, sub, and, or

• Desvio: beq

• Esse subconjunto é suficiente para ilustrar os princípios de projeto do processador

Nota: o livro-texto usa lw/sw (RV32I). Nestes slides usamos ld/sd (RV64I). Os princípios de projeto do datapath e pipeline são idênticos.

Fluxo de Execução de uma Instrução

1. Fetch — buscar instrução na memória usando o PC
2. Decode — decodificar campos e ler registradores
3. Execute — executar operação na ALU
4. Memory — acessar memória de dados (load/store)

5. Write-back — escrever resultado no banco de registradores

6. Todas as instruções compartilham os dois primeiros passos

7. Os passos seguintes dependem do tipo da instrução

Convenções de Projeto Lógico

• Dois tipos de elementos:
• Combinacionais — saída depende apenas da entrada atual
  • Porta AND, mux, ALU, somador

• Sequenciais — possuem estado interno (memória)

  • Registradores, memórias

• Elementos sequenciais são sensíveis à borda (edge-triggered)

• Atualizam o valor na borda de subida do clock
• Podem ter sinal de write enable

Metodologia de Temporização

• Lógica combinacional entre elementos de estado
• Dados lidos no início do ciclo, escritos no final

   ┌──────────┐   Lógica        ┌──────────┐
   │ Elemento │──combinacional──▶│ Elemento │
   │ de estado│                  │ de estado│
   └──────────┘                  └──────────┘
       ▲ clock                       ▲ clock

• O período do clock deve ser longo o suficiente para que os sinais se propaguem pela lógica combinacional
• Metodologia de clock de borda única: leitura e escrita na mesma borda

Construindo o Datapath: Instruction Fetch

• Componentes necessários:
• Memória de instruções — armazena as instruções
• PC (Program Counter) — endereço da instrução atual
• Somador — calcula PC + 4

  PC ──▶ Memória de ──▶ Instrução
  │      Instruções
  │
  └──▶ (+4) ──▶ Próximo PC

• A cada ciclo: lê a instrução no endereço PC e incrementa PC ← PC + 4

Datapath: Instruções R-format

• Operações: add, sub, and, or
• Passos:
• Ler dois registradores (rs1, rs2)
• Executar operação na ALU

• Escrever resultado no registrador destino (rd)

• Componentes:

• Banco de registradores — 32 registradores, 2 portas de leitura, 1 de escrita
• ALU — executa a operação

Datapath: Load e Store

• ld rd, offset(rs1) e sd rs2, offset(rs1)
• Passos:
• Calcular endereço: base (rs1) + offset com extensão de sinal
• Load: ler memória e escrever no registrador

• Store: ler registrador e escrever na memória

• Componentes adicionais:

• Unidade de extensão de sinal — estende o imediato de 12 bits para 64 bits
• Memória de dados — separada da memória de instruções

Datapath: Branch

• beq rs1, rs2, offset
• Passos:
• Ler rs1 e rs2
• Comparar na ALU (subtração, testar flag Zero)

• Calcular endereço alvo: PC + (imediato << 1)

• Se a condição é verdadeira, PC ← endereço alvo

• Caso contrário, PC ← PC + 4

• Um shift left de 1 bit dobra o alcance do desvio

Compondo o Datapath

• Combinar os elementos com muxes para selecionar entre caminhos:
• Mux no PC: PC+4 ou endereço de branch
• Mux na entrada da ALU: registrador ou imediato

• Mux no write-back: saída da ALU ou dado da memória

• Memórias separadas para instruções e dados

• Evita conflito estrutural (leitura de instrução + acesso a dados)

• Todos os componentes conectados em um único datapath

Controle Simples: ALU Control

• ALU precisa de sinais de controle para selecionar a operação
• Estratégia de dois níveis:
• ALUOp (2 bits) — derivado do opcode
• ALU control (4 bits) — derivado de ALUOp + campo funct

ALUOp	Operação
00	Soma (load/store)
01	Subtração (branch)
10	Depende de funct

Unidade de Controle Principal

• Gera sinais de controle a partir do opcode da instrução

Sinal	Função
RegWrite	Habilita escrita no registrador
ALUSrc	Seleciona segundo operando da ALU
MemRead	Habilita leitura da memória
MemWrite	Habilita escrita na memória
MemtoReg	Seleciona dado da memória para write-back
Branch	Instrução de desvio

Sinais de Controle por Instrução

Sinal	R-type	ld	sd	beq
ALUSrc	0	1	1	0
MemtoReg	0	1	X	X
RegWrite	1	1	0	0
MemRead	0	1	0	0
MemWrite	0	0	1	0
Branch	0	0	0	1
ALUOp	10	00	00	01

Questões de Desempenho

• O caminho crítico é determinado pela instrução mais lenta
• Instrução ld: IF → ID → EX → MEM → WB

• Todas as 5 etapas são usadas

• O período do clock deve acomodar o pior caso

• Não é possível variar o período por tipo de instrução

• Instruções rápidas (como add) são penalizadas

• Solução: pipelining!

Visão Geral do Pipeline

• Analogia da lavanderia:
• 4 etapas: lavar, secar, dobrar, guardar
• Sem pipeline: espera uma carga terminar antes de começar outra

• Com pipeline: inicia nova carga assim que a lavadora fica livre

• Pipeline não reduz a latência de uma instrução individual

• Pipeline melhora a vazão (throughput) do processador

Estágios do Pipeline RISC-V

1. IF — Instruction Fetch (buscar instrução)
2. ID — Instruction Decode / Register Read (decodificar e ler registradores)
3. EX — Execute / Address Calculation (executar ou calcular endereço)
4. MEM — Memory Access (acessar memória)
5. WB — Write-Back (escrever resultado)

Desempenho do Pipeline

• Exemplo: cada estágio leva 200 ps

Implementação	Tempo por instrução	Throughput
Ciclo único	800 ps	1/800 ps
Pipeline	200 ps (ciclo)	1/200 ps

• Speedup ideal = número de estágios do pipeline

• \(\text{Speedup} = \frac{T_{sem\ pipeline}}{T_{com\ pipeline}} \approx n\) (para \(n\) estágios)

• Na prática, speedup é menor que \(n\) por causa dos hazards

ISA Projetado para Pipeline

• Características do RISC-V que facilitam o pipeline:
• Todas as instruções têm 32 bits — busca em 1 ciclo
• Poucos formatos de instrução — decodificação simples
• Campos de registradores na mesma posição em todos os formatos
• Operações de memória apenas com load/store — cálculo de endereço no EX
• Operandos alinhados na memória — acesso em 1 ciclo

Hazards

• Situações que impedem a execução da próxima instrução no ciclo seguinte
• Três tipos:
• Structural hazards — conflito de recursos
• Data hazards — dependência de dados
• Control hazards — decisão de desvio pendente

Structural Hazards

• Conflito quando dois estágios precisam do mesmo recurso
• Exemplo: memória única para instruções e dados

• IF e MEM acessariam a memória simultaneamente

• Solução: memórias separadas (ou caches) para instruções e dados

• No RISC-V pipeline: memória de instruções (IF) e memória de dados (MEM)

Data Hazards

• Uma instrução depende do resultado de uma instrução anterior ainda no pipeline

add x19, x0, x1
sub x2, x19, x3     # x19 ainda não foi escrito!

• O resultado de add só estaria disponível após o estágio WB
• Mas sub precisa dele no estágio ID

Forwarding (Bypassing)

• O resultado é calculado no estágio EX — antes de ser escrito no registrador
• Podemos encaminhar (forward) o resultado diretamente para onde ele é necessário

add x19, x0, x1     # resultado disponível após EX
sub x2, x19, x3     # recebe via forwarding

• Caminhos de forwarding conectam as saídas de EX/MEM e MEM/WB às entradas da ALU
• Muxes selecionam entre o valor do registrador e o valor encaminhado

Forwarding (Bypassing)

Load-Use Hazard

• Forwarding não resolve todos os casos
• O dado de ld só está disponível após o estágio MEM

ld  x2, 0(x1)
sub x4, x2, x5     # precisa de x2 no EX, mas ld só tem no MEM

• Não é possível encaminhar "para trás no tempo"
• Solução: inserir um stall (bolha) de 1 ciclo

Escalonamento de Código

• O compilador pode reorganizar instruções para evitar stalls

# Antes (com stall):           # Depois (sem stall):
ld  x2, 0(x1)                  ld  x2, 0(x1)
sub x4, x2, x5  # stall!       ld  x3, 8(x1)
ld  x3, 8(x1)                  sub x4, x2, x5  # sem stall
add x6, x2, x3                 add x6, x2, x3

• O compilador insere instruções independentes entre a produção e o uso do dado

Control Hazards

• O resultado do branch só é conhecido após comparação

• As instruções seguintes já entraram no pipeline

• Estratégias:

• Stall: esperar até saber o resultado (custo alto)
• Predict not taken: continuar com PC+4, flush se errar
• Predict taken: assumir que o desvio será tomado

Branch Prediction

• Predição estática:
• Predict not taken — simples, acerta em ~50%

• Backward taken, forward not taken — bom para loops

• Predição dinâmica:

• Baseada no histórico de execução do branch
• Hardware mantém tabela de predição
• Quanto mais profundo o pipeline, maior a penalidade por misprediction

Datapath com Pipeline

• Registradores de pipeline entre cada estágio:

• IF/ID, ID/EX, EX/MEM, MEM/WB

• Cada registrador armazena:

• Dados processados no estágio anterior

• Sinais de controle necessários nos estágios seguintes

• A instrução "flui" pelos estágios carregando seus dados e controle

Operação Ciclo a Ciclo: Load

Ciclo	Estágio	Ação
1	IF	Buscar instrução, PC+4
2	ID	Ler rs1, estender imediato
3	EX	Calcular endereço (base + offset)
4	MEM	Ler dado da memória
5	WB	Escrever dado no registrador rd

Operação Ciclo a Ciclo: Store

Ciclo	Estágio	Ação
1	IF	Buscar instrução, PC+4
2	ID	Ler rs1, rs2, estender imediato
3	EX	Calcular endereço (base + offset)
4	MEM	Escrever dado na memória
5	WB	Nenhuma operação (nop)

Diagrama Multi-Ciclo do Pipeline

Instrução    CC1   CC2   CC3   CC4   CC5   CC6   CC7
  ld         IF    ID    EX    MEM   WB
  sub              IF    ID    EX    MEM   WB
  and                    IF    ID    EX    MEM   WB
  or                           IF    ID    EX    MEM
  add                                IF    ID    EX

• Cada instrução ocupa 5 ciclos
• Mas uma nova instrução inicia a cada ciclo
• Throughput: 1 instrução/ciclo (no caso ideal)

Controle no Pipeline

• Sinais de controle gerados no estágio ID
• Propagados pelos registradores de pipeline

Estágio	Sinais utilizados
EX	ALUSrc, ALUOp
MEM	MemRead, MemWrite, Branch
WB	RegWrite, MemtoReg

• Sinais viajam junto com os dados — cada estágio usa os sinais corretos

Detectando a Necessidade de Forwarding

• Comparar números de registradores ao longo do pipeline:
• EX hazard: EX/MEM.Rd == ID/EX.Rs1 ou ID/EX.Rs2

• MEM hazard: MEM/WB.Rd == ID/EX.Rs1 ou ID/EX.Rs2

• Condições adicionais:

• O estágio anterior deve escrever em registrador (RegWrite = 1)
• O registrador destino não pode ser x0

Sinais de Forwarding

• ForwardA e ForwardB controlam muxes na entrada da ALU

Valor	Fonte
00	Banco de registradores (sem forwarding)
10	Resultado de EX/MEM (hazard EX)
01	Resultado de MEM/WB (hazard MEM)

Double Data Hazard

add x1, x1, x2
add x1, x1, x3
add x1, x1, x4

• A terceira instrução tem hazard tanto com EX/MEM quanto com MEM/WB

• Deve-se usar o resultado mais recente (EX/MEM tem prioridade)

• Regra: só aplicar forwarding de MEM/WB se não houver forwarding de EX/MEM para o mesmo registrador

Detecção de Load-Use Hazard

• Verificar no estágio ID:

if (ID/EX.MemRead == 1) and
   ((ID/EX.Rd == IF/ID.Rs1) or (ID/EX.Rd == IF/ID.Rs2))
then stall

• Mecanismo de stall:
• Forçar sinais de controle para nop no registrador ID/EX
• Impedir atualização do PC e do registrador IF/ID
• A instrução no IF e ID é "congelada" por 1 ciclo

Detecção de Load-Use Hazard

Control Hazards no Pipeline

• Branch decidido no estágio MEM → 3 ciclos de penalidade

• Instruções buscadas erroneamente devem ser descartadas (flush)

• Otimização: mover comparação para o estágio ID

• Reduz penalidade para 1 ciclo
• Requer hardware de comparação adicional no ID

Data Hazards em Branches

• Se o branch depende de resultado anterior:

add x1, x2, x3
beq x1, x4, alvo    # x1 vem de add

• Com comparação no ID e forwarding de EX/MEM: 1 ciclo de stall
• Se depende de ld imediatamente antes: 2 ciclos de stall

Branch Prediction Dinâmica

• Branch History Table (BHT):
• Indexada pelos bits menos significativos do PC

• Armazena se o branch foi tomado ou não na última execução

• Preditor de 1 bit:

• Problema com loops internos: erra duas vezes (na saída e na reentrada)

Preditor de 2 Bits

• Muda a predição somente após dois erros consecutivos
• Quatro estados:

  Strongly     Weakly      Weakly      Strongly
   Taken  ←→   Taken   ←→  Not Taken ←→ Not Taken

• Funciona melhor para loops:
• Acerta todas as iterações exceto a última
• Na próxima execução do loop, ainda prediz "taken"

Preditores Avançados

• Preditores correlacionados: usam o histórico global de branches recentes para selecionar entre múltiplos preditores de 2 bits
• GShare: combina o histórico global com os bits do PC via XOR para indexar a tabela de predição
• Preditores de torneio: um meta-preditor seleciona dinamicamente entre um preditor local (baseado no histórico do branch individual) e um preditor global
• Processadores modernos combinam múltiplas técnicas para atingir taxas de acerto acima de 95%
• Maior profundidade de pipeline aumenta a penalidade por misprediction, justificando preditores mais sofisticados

Branch Target Buffer

• Problema: mesmo predizendo corretamente, precisamos do endereço alvo
• Branch Target Buffer (BTB):
• Cache que armazena o endereço alvo de branches recentes
• Indexado pelo PC

• Antes mesmo de decodificar, já fornece o próximo PC

• Se o branch está no BTB e a predição é "taken" → buscar do endereço alvo

• Se não está → assumir not taken (PC+4)

Exceções e Interrupções

• Eventos que alteram o fluxo normal de execução
• Exceção: originada dentro da CPU (instrução inválida, overflow)

• Interrupção: originada externamente (I/O, timer)

• Tratamento:

• Salvar PC da instrução causadora em SEPC
• Registrar causa em SCAUSE
• Desviar para o handler em endereço fixo

Interrupções Vetorizadas

• Endereço do handler depende da causa:

Causa da exceção	Endereço do handler
Instrução inválida	base + 0x00
Overflow aritmético	base + 0x04
Interrupção externa	base + 0x08
...	...

• Alternativa: handler único que consulta SCAUSE

Exceções no Pipeline

• A instrução que causa a exceção pode estar em qualquer estágio
• Ações:
• Flush das instruções nos estágios anteriores
• Salvar PC em SEPC

• Redirecionar fetch para o endereço do handler

• Exceções precisas: o estado do processador reflete a execução até a instrução que causou a exceção — como se instruções posteriores não tivessem iniciado

Múltiplas Exceções no Pipeline

• Várias instruções no pipeline podem gerar exceções simultaneamente
• O processador prioriza a exceção da instrução mais antiga (mais à frente no pipeline)
• Exceções de instruções mais recentes são descartadas — serão re-executadas

Paralelismo em Nível de Instrução (ILP)

• Duas abordagens para explorar ILP:
• Pipeline mais profundo — mais estágios, clock mais rápido

• Múltipla emissão (multiple issue) — várias instruções por ciclo

• Métrica: IPC (Instructions Per Clock)

• Inverso do CPI
• Se o processador emite 4 instruções/ciclo → CPI ideal = 0,25, IPC = 4

Múltipla Emissão Estática (VLIW)

• Compilador agrupa instruções em "pacotes de emissão"

• Decisões de escalonamento tomadas em tempo de compilação

• Exemplo RISC-V com emissão dual:

• Slot 1: instrução ALU ou branch

• Slot 2: instrução load ou store

• Se não há instrução adequada para um slot → nop

Exemplo de Escalonamento Estático

Loop que soma elementos de um array

Loop: ld   x31, 0(x20)      # load a[i]
      add  x31, x31, x21    # a[i] + s
      sd   x31, 0(x20)      # store a[i]
      addi x20, x20, 8      # i++
      bne  x20, x22, Loop   # repetir

Escalonamento dual issue:

Ciclo	ALU/Branch	Load/Store
1	nop	ld x31, 0(x20)
2	addi x20, x20, 8	nop
3	add x31, x31, x21	nop
4	bne x20, x22, Loop	sd x31, -8(x20)

Loop Unrolling

• Replicar o corpo do loop para expor mais ILP
• Reduz overhead do controle de loop
• Requer register renaming para evitar dependências falsas ou uso de outros registradores na replicação do código

Loop: ld  x31, 0(x20)
      add x31, x31, x21
      sd  x31, 0(x20)

      ld  x28, 8(x20)       # cópia com outro registrador
      add x28, x28, x21
      sd  x28, 8(x20)

      addi x20, x20, 16
      bne x20, x22, Loop

Múltipla Emissão Dinâmica (Superscalar)

• Hardware decide quantas e quais instruções emitir a cada ciclo

• O processador reordena instruções em tempo de execução

• Componentes-chave:

• Reservation stations — buffers que aguardam operandos
• Reorder buffer — garante commit em ordem
• Register renaming — elimina dependências falsas (WAR, WAW)

Execução Fora de Ordem

• Instruções são emitidas em ordem mas podem executar fora de ordem
• Resultados são armazenados no reorder buffer
• Commit acontece em ordem para manter exceções precisas

Fetch → Decode → Issue → Execute → Complete → Commit
         (em ordem)   (fora de ordem)    (em ordem)

Especulação

• Especulação de branch:
• Executar instruções antes de confirmar o resultado do branch
• Se a predição estiver correta → commit normal

• Se errada → descartar resultados (rollback)

• Especulação de load:

• Executar load antes de confirmar que não há store conflitante

• Se houver conflito → re-executar o load

• Reorder buffer é essencial para suportar especulação

Múltipla Emissão Funciona?

• Na prática, os ganhos são limitados:
• Dependências reais entre instruções
• Latência de acesso à memória (cache misses)
• Branches difíceis de prever

• Complexidade do hardware cresce exponencialmente

• Processadores modernos emitem 3–6 instruções/ciclo

• IPC real tipicamente entre 1 e 3 (muito abaixo do máximo teórico)

ARM Cortex A53 vs Intel Core i7

	Cortex A53	Core i7
Tipo	In-order	Out-of-order
Emissão	2 instruções	4–6 instruções
Pipeline	8 estágios	14+ estágios
Predição de branch	Sim	Sim (avançada)
Especulação	Limitada	Agressiva
Consumo	~0.1 W	~50–100 W
Aplicação	Mobile, embedded	Desktop, servidor

• Diferentes pontos no espaço de projeto desempenho-energia

Falácias e Armadilhas

• Falácia: Pipeline é fácil
• Na verdade, hazards tornam o projeto complexo

• Exceções, interrupções e corner cases são difíceis

• Armadilha: ISA mal projetado dificulta o pipeline

• Instruções de comprimento variável complicam IF
• Formatos irregulares complicam ID
• Modos de endereçamento complexos dificultam EX
• x86 precisa traduzir para micro-ops internamente

Considerações Finais

• O ISA influencia diretamente o projeto do datapath e controle
• Pipeline melhora throughput, não latência individual
• Hazards (estrutural, dados, controle) exigem soluções em hardware e software
• ILP oferece ganhos, mas com retornos decrescentes
• Dependências, latência de memória e complexidade limitam o paralelismo
• O power wall restringe pipelines profundos e múltipla emissão agressiva
• Motivou a mudança para multicore