MIPS-32 Pipelined Processor with L1 Cache & Hazard Unit

Implementação completa de um processador MIPS de 32 bits com arquitetura em pipeline de 5 estágios, intertravamento de hardware para controle de hazards (load-use hazard unit) e hierarquia de memória Harvard com módulos dedicados de memória Cache L1 de Mapeamento Direto (Direct-Mapped Cache), modelado e simulado em Logisim-evolution.

---

1. Visão Geral da Arquitetura

O circuito opera sob a divisão clássica de 5 estágios em pipeline proposta por Patterson & Hennessy, com registradores de desacoplamento entre estágios (IF/ID, ID/EX, EX/MEM e MEM/WB), unidade de controle combinacional desacoplada e hierarquia de memória de dados e instruções isoladas.

flowchart LR
    subgraph IF ["Estágio IF"]
        PC["PC Register"] --> ICache["L1 I-Cache (16x32b)"]
        PC --> Addr4["PC + 4"]
    end

    subgraph ID ["Estágio ID"]
        UC["Control Unit (UC)"]
        UH["Hazard Unit (UH)"]
        RF["Register File (32x32b)"]
        Ext["Sign Extender (16->32)"]
    end

    subgraph EX ["Estágio EX"]
        ALU["ULA (Add/Sub/Zero)"]
        BranchCalc["Branch Target Adder"]
        BranchCond["Branch Taken Logic"]
    end

    subgraph MEM ["Estágio MEM"]
        DCache["L1 D-Cache (16x32b)"]
        DMem["Data RAM"]
    end

    subgraph WB ["Estágio WB"]
        MuxWB["MemtoReg MUX"]
    end

    IF -->|IF/ID| ID
    ID -->|ID/EX| EX
    EX -->|EX/MEM| MEM
    MEM -->|MEM/WB| WB
    WB -.->|DataWrite / RegWrite| RF
    UH -.->|Stall / Freeze| PC
    UH -.->|Stall / Freeze| IF
    EX -.->|BranchTaken / Target| PC

Loading

---

2. Especificação dos Estágios do Pipeline

2.1. Busca de Instrução (EIF - Instruction Fetch)

• Controle de Fluxo de PC: O registrador PC é atualizado na borda de subida do clock. Na ausência de hazards e branches, $PC \leftarrow PC + 4$.
• Desvios Condicionais: Em caso de branch tomado no estágio de execução (EX_BranchTaken = 1), o multiplexador de entrada de PC seleciona EX_BranchTarget.
• Memória de Instruções & Cache L1-I: As instruções são acessadas em primeira instância pela CacheModule de instruções; falhas de cache disparam Stall_ICache congelando o estágio até a recuperação pela ROM de instruções.

2.2. Decodificação e Leitura de Registradores (EID - Instruction Decode)

• Banco de Registradores (RegisterFile):
  • 32 registradores de uso geral de 32 bits ($zero a $ra).
  • Duas portas de leitura assíncronas (ReadData1, ReadData2) indexadas pelos campos rs (bits [25:21]) e rt (bits [20:16]).
  • Uma porta de escrita síncrona habilitada por RegWrite indexada por RegAddrDest [4:0].
  • O registrador $zero ($r0$) é fixado permanentemente em $0\text{x}00000000$.
• Extensor de Sinal (Extender): Expansão do imediato de 16 bits para 32 bits com preservação do bit de sinal em complemento de dois ($\text{bit}[15]$ replicado nas posições $[31:16]$).

2.3. Execução e Cálculo de Branch (EEX - Execute)

• Unidade Lógica e Aritmética (ULA):
  • Operações de soma ($A + B$) e subtração ($A - B$) em barramentos de 32 bits.
  • Comparador de igualdade a zero para geração do sinal Zero_Flag ($A - B = 0$).
• Seleção de Operandos da ULA:
  • Entrada $A$: EX_DataOut1 (conteúdo de rs).
  • Entrada $B$: Multiplexado via ALUSrc entre EX_DataOut2 (conteúdo de rt) e ImmediateExt (imediato estendido).
• Cálculo de Desvio (Branch Target): Calculado no estágio de execução em paralelo à ULA principal:

  \begin{aligned}
  \text{BranchTarget} &= \text{EX.PC4} + (\text{ImmediateExt} \ll 2) \\
  \text{BranchTaken}  &= \text{Branch} \land \text{Zero}
  \end{aligned}
  

• Destino do Registrador: Multiplexador controlado por RegDest seleciona entre EX_RT (instruções tipo I) e EX_RD (instruções tipo R).

2.4. Acesso à Memória (EMEM - Memory Access)

• Interface com o subsistema de memória de dados através do módulo de Cache L1-D (CacheModule) e memória primária de retaguarda (DataMemory).
• Em operações de leitura (MemRead) com acerto de cache, os dados são entregues no mesmo ciclo. Em caso de falha de cache (miss), o circuito gera Stall_DCache para pausar a propagação do pipeline até a conclusão da carga.

2.5. Escrita no Banco de Registradores (EWB - Write-Back)

• Multiplexador controlado por MemtoReg define o dado final a ser retroalimentado ao RegisterFile:
  • $\text{MemtoReg} = 0$: Dado proveniente do resultado da ULA (ResultOut).
  • $\text{MemtoReg} = 1$: Dado carregado da memória (DataOut).

---

3. Subsistema de Memória Cache L1 (CacheModule)

O processador implementa uma memória cache L1 de Mapeamento Direto (Direct-Mapped Cache) com capacidade para 16 linhas de 1 palavra (32 bits), totalizando 64 bytes de armazenamento local.

3.1. Estrutura de Endereçamento (32 bits)

O barramento de endereço de 32 bits é particionado da seguinte forma:

Tag (26 bits)	Índice / Set (4 bits)	Byte Offset (2 bits)
bits [31:6]	bits [5:2]	bits [1:0]

• Byte Offset (2 bits): Alinhamento em nível de palavra de 32 bits (bits [1:0] ignorados para indexação de palavras).
• Índice (4 bits): Indexa diretamente uma das $2^4 = 16$ linhas da cache.
• Tag (26 bits): Rótulo comparado com a tag armazenada para verificação de correspondência de bloco.

3.2. Estrutura Interna e Lógica de Acerto (Hit/Miss)

Cada uma das 16 linhas da cache possui:

1. Bit de Validade (Valid): 1 bit indicando se a linha contém dados válidos.
2. Tag RAM: 26 bits para identificação do bloco de memória.
3. Data RAM: 32 bits correspondentes à palavra de dados.

A lógica combinacional de validação é definida por:

$$\begin{aligned} \text{Hit} &= \text{Valid} \land (\text{Tag}_{\text{in}} = \text{Tag}_{\text{cache}}) \\\ \text{Miss} &= \neg \text{Hit} \\\ \text{Stall}_{\text{Cache}} &= (\text{CPU.MemRead} \lor \text{CPU.MemWrite}) \land \text{Miss} \end{aligned}$$

Em caso de Miss, a cache dispara um ciclo de preenchimento a partir da memória primária (DataMemory ou InstructionMemory), atualizando simultaneamente a tag, o dado e ligando o bit de validade.

---

4. Unidade de Detecção de Hazards (UH)

Para solucionar dependências de dados do tipo Load-Use (onde uma instrução imediatamente posterior a um lw tenta ler o registrador de destino antes de sua recuperação da memória), a unidade UH introduz uma bolha (stall) de 1 ciclo no pipeline.

4.1. Condição Formal de Intertravamento

$$\text{Stall} = \text{EX.MemRead} \land \big((\text{EX.rt} = \text{ID.rs}) \lor (\text{EX.rt} = \text{ID.rt})\big)$$

4.2. Ações de Intertravamento

Quando a condição de stall é ativada (Stall = 1):

• IF_PC_Write = 0: Congela o registrador PC no ciclo atual, impedindo avanço de instrução.
• IF_ID_Write = 0: Congela o registrador de desacoplamento IF/ID, retendo a instrução em decodificação.
• ID_Stall = 1: Força os sinais de controle no registrador ID/EX para zero (NOP), gerando uma bolha no estágio de execução.

---

5. Unidade de Controle (UC)

A Unidade de Controle decodifica o código de operação (Opcode_In [31:26]) e o código de função (Funct_In [5:0]) utilizando dois decodificadores $6 \to 64$ e sintetiza a rede de sinais de controle do datapath.

5.1. Equações Booleanas dos Sinais de Controle

$$\begin{aligned} \text{MemtoReg} &= \text{Lw} \\\ \text{MemRead} &= \text{Lw} \\\ \text{MemWrite} &= \text{Sw} \\\ \text{Branch} &= \text{Beq} \\\ \text{RegDest} &= \text{R-Type} \\\ \text{ALUCtrl} &= (\text{R-Type} \land \text{Sub}) \lor \text{Beq} \\\ \text{RegWrite} &= \text{R-Type} \lor \text{Addi} \lor \text{Lw} \\\ \text{ALUSrc} &= \text{Addi} \lor \text{Lw} \lor \text{Sw} \end{aligned}$$

---

6. Conjunto de Instruções Suportado (ISA Subset)

Instrução	Mnemônico	Formato	Opcode	Funct	Semântica Operacional
Add	add $rd, $rs, $rt	R	0x00	0x20	$R[rd] \leftarrow R[rs] + R[rt]$
Subtract	sub $rd, $rs, $rt	R	0x00	0x22	$R[rd] \leftarrow R[rs] - R[rt]$
Add Immediate	addi $rt, $rs, imm	I	0x08	N/A	$R[rt] \leftarrow R[rs] + \text{SignExt}(imm)$
Load Word	lw $rt, offset($rs)	I	0x23	N/A	$R[rt] \leftarrow M[R[rs] + \text{SignExt}(offset)]$
Store Word	sw $rt, offset($rs)	I	0x2B	N/A	$M[R[rs] + \text{SignExt}(offset)] \leftarrow R[rt]$
Branch on Equal	beq $rs, $rt, label	I	0x04	N/A	$\text{if } (R[rs] == R[rt]) \text{ PC} \leftarrow \text{PC} + 4 + (\text{SignExt}(imm) \ll 2)$

---

7. Simulação e Execução

7.1. Requisitos de Ambiente

• Software: Logisim-evolution versão v4.0.0 ou superior (e.g., v4.1.0 ou v5.0.0).

  [!IMPORTANT] Versões legadas ($\le \text{v3.8.0}$) impõem restrição de 5 bits no componente Decoder da biblioteca #Plexers, descartando os decodificadores de 6 bits da UC. Utilize sempre o pacote nativo atualizado (.deb ou -all.jar).

7.2. Execução Passo a Passo

1. Abertura do Circuito:

   # Execução via binário nativo ou jar
   logisim-evolution circuit/processor.circ &

2. Carregamento de Programas:
   • Navegue até o subcircuito InstructionMemory.
   • Clique com o botão direito sobre o componente ROM e selecione Edit Contents....
   • Carregue o arquivo hexadecimal de teste localizado em programs/cache_hazard_test.hex.
3. Simulação por Passos ou Contínua:
   • Habilite a simulação com Ctrl + K.
   • Para avançar um semiciclo manualmente, pressione Ctrl + T.
   • Para alternar a frequência de clock automática, acesse o menu Simulate $\rightarrow$ Tick Frequency (recomendado: 1 Hz a 4 Hz para inspeção visual do pipeline).

7.3. Programa de Verificação (cache_hazard_test.asm)

O programa de teste incluído valida simultaneamente a ocorrência de acertos e falhas na cache L1 e o intertravamento de dependência de dados:

# programs/cache_hazard_test.asm
lw   $t0, 0($zero)     # Compulsory Miss: Aloca índice 0 da D-Cache e dispara Stall_DCache
lw   $t1, 0($zero)     # Cache Hit: Dado lido diretamente da D-Cache sem stall
lw   $t2, 4($zero)     # Compulsory Miss: Aloca índice 1 da D-Cache
lw   $t3, 0($zero)     # Cache Hit: Linha 0 permanece residente na cache
addi $t4, $zero, 10    # Aritmética imediata
addi $t5, $zero, 10
sub  $t6, $t4, $t5     # $t6 = 0 (Ativa Zero_Flag na ULA)
beq  $t4, $t5, target  # Desvio tomado: flush do pipeline
addi $t7, $zero, 99    # Instrução descartada
target:
sw   $t6, 8($zero)     # Armazena resultado na memória

---

8. Estrutura do Repositório

mips-processor/
├── circuit/
│   └── processor.circ         # Esquema estrutural completo (Logisim-evolution XML)
├── assets/
│   ├── datapath_overview.png  # Esquema geral dos 5 estágios e pipeline registers
│   ├── control_unit.png       # Esquema da UC (decodificadores 6->64 e portas lógicas)
│   ├── hazard_unit.png        # Unidade de detecção de hazard Load-Use
│   ├── execute_stage.png      # Estágio de execução (ULA e lógica de branch)
│   └── cache_module.png       # Módulo da memória Cache L1 de Mapeamento Direto
├── programs/
│   ├── cache_hazard_test.asm  # Código-fonte MIPS Assembly anotado para verificação
│   └── cache_hazard_test.hex  # Imagem hexadecimal para carga na ROM do Logisim
└── README.md                  # Documentação formal da arquitetura