Skip to content
STIMSMITH

Pipelined Microprocessor

Concept WIKI v1 · 5/26/2026

A pipelined microprocessor partitions instruction execution into stages separated by pipeline registers so multiple instructions can be in flight at once. In the Y86-64 PIPE design described in the evidence, a five-stage pipeline uses fetch, decode, execute, memory, and writeback-style computation, with extra control logic and data paths to handle hazards, stalls, bubbles, forwarding, and branch mispredictions.

Overview

A pipelined microprocessor is illustrated by the Y86-64 PIPE implementation, a five-stage pipeline that implements the Y86-64 instruction set. PIPE is structurally similar to the sequential SEQ processor: both partition computation into similar stages and use the same set of functional blocks. The key difference is that PIPE adds state elements in the form of pipeline registers, enabling up to five instructions to flow through the pipeline simultaneously, each in a different stage. [C1]

Pipeline structure

The PIPE design is organized around stages corresponding to instruction flow. The evidence identifies a five-stage structure with fetch, decode, execute, memory, and writeback-related logic. In the sequential SEQ design, a clock cycle begins from the current program counter, fetches instruction bytes, computes the next sequential PC, reads register operands, performs ALU work, optionally accesses data memory, writes results to registers, and updates the PC. PIPE retains similar functional blocks but separates concurrent instruction flow with pipeline registers. [C2]

Pipeline registers are central to operation. In the UCLID5 model, a pipeline register can take on several next-state values: the normal input value, the old value when the pipeline stalls, an empty value when a bubble is injected, or an initial value used for verification. [C3]

Hazards, stalls, bubbles, and forwarding

Because multiple instructions are active at the same time, PIPE requires additional data connections and control logic to resolve hazard conditions where data or control must pass between instructions in the pipeline. [C4]

The standard PIPE implementation handles data hazards for execute-stage arguments by forwarding into the decode stage. It requires a one-cycle decode-stage stall for a load/use hazard and a three-cycle stall for a return instruction. Branches are predicted as taken, and up to two instructions are canceled when a misprediction is detected. [C5]

Other variants show common design tradeoffs. A STALL variant uses no data forwarding; instead, an instruction stalls in decode for up to three cycles when a later pipeline instruction imposes a data hazard. An LF variant adds a forwarding path from the data-memory output to the pipeline register feeding the data-memory input, resolving some load/use hazards by forwarding rather than stalling. Branch-prediction variants include NT, which predicts branches as not taken unless unconditional, and BTFNT, which predicts backward branches as taken and forward branches as not taken unless unconditional; both can cancel up to two instructions on misprediction. [C6]

Modeling and verification considerations

The evidence discusses formal verification of pipelined Y86-64 microprocessors using UCLID5. UCLID5 provides a modeling language for the system and a command language for initialization, operation, and verification conditions. For this verification, the modeled system combines a pipelined microprocessor with a sequential reference implementation, and the verification script carries out Burch-Dill correspondence checking. [C7]

When modeling PIPE in UCLID5, the processor is represented with procedures for each stage. These procedures compute stage signals and may update state elements. For the complete processor model, stage procedures must be invoked in an order consistent with combinational signal flow across stages. For PIPE, the evidence gives ordering constraints such as writeback-to-decode and memory-to-execute-to-decode, leading to an ordering of writeback, fetch, memory, execute, and decode, followed by control-logic and pipeline-register updates. [C8]

Verification must address more than safety. The evidence notes that if verification only checks that the pipeline corresponds to a sequential implementation when instructions commit, then a deadlocked processor—or even a device that does nothing—could pass. Therefore liveness must also be checked to show that the pipeline cannot stall indefinitely and cannot enter a state where it never makes forward progress. [C9]

LINKED ENTITIES

1 links
Burch-Dill Correspondence Checking verification_method

CITATIONS

9 sources
9 citations
[1] C1: PIPE is a five-stage Y86-64 pipeline that adds pipeline registers to allow up to five instructions to flow simultaneously in different stages. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[2] C2: SEQ and PIPE use similar functional blocks and stages; SEQ flow includes PC-based fetch, register reads, ALU work, data memory access, register writeback, and PC update. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[3] C3: A modeled pipeline register can select an input value, old value for a stall, empty value for a bubble, or initial value for verification. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[4] C4: PIPE requires additional data connections and control logic to resolve hazard conditions where data or control must pass between pipeline instructions. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[5] C5: The STD PIPE variant uses decode-stage forwarding for execute-stage data hazards, stalls for load/use and return hazards, predicts branches as taken, and cancels up to two instructions on misprediction. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[6] C6: PIPE variants demonstrate no-forwarding stalls, added load/use forwarding, and alternative branch-prediction policies with possible cancellation of up to two instructions. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[7] C7: UCLID5 models the pipelined microprocessor and sequential reference implementation and supports verification scripts for Burch-Dill correspondence checking. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[8] C8: PIPE stage modeling in UCLID5 must respect combinational signal-flow dependencies, with constraints including writeback-to-decode and memory-to-execute-to-decode. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[9] C9: Safety-style verification alone can allow deadlocked or non-progressing processors to pass, so liveness must be verified to show that the pipeline does not stall indefinitely. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5