Processor Datapath and Pipelining

A datapath holds and transforms the values an instruction needs. The control unit steers those values and enables writes. Together they carry out instructions such as add, sub, and, or, ld, sd, and beq.

Follow values between clock edges

A state element remembers a value: the program counter, register file, and data memory are examples. A combinational element produces an output from its current inputs. Adders, multiplexers, the ALU, and the immediate generator do this work without storing an instruction's result between cycles.

At the active clock edge, state elements capture their next values. Between edges, their outputs feed combinational logic. The PC can therefore supply the current address throughout a cycle and capture the next address at its end. Reading a state element does not itself overwrite it.

Fetch and register access

The program counter (PC) holds the instruction address. Instruction memory returns the 32-bit instruction at that address. In this model it is read-only while the program runs and acts as an address-to-instruction lookup. A separate adder forms PC + 4 because the instructions in this subset occupy 4 bytes.

The register file contains x0–x31. Two read ports take the source numbers rs1 and rs2 and return their values. One write port takes destination rd, write data, and RegWrite. Reads are combinational; an enabled write is saved at the clock edge. Register x0 always reads as zero and discards writes. RV64 registers hold 64 bits. An RV32 version uses 32-bit registers and lw/sw, with the same basic connections.

Compute, select, and access memory

The arithmetic logic unit (ALU) adds, subtracts, or performs a bitwise operation. A 4-bit control code selects the operation. Its Zero output is 1 when the result is zero; subtraction can therefore test whether two values are equal.

The immediate generator, ImmGen, rebuilds an instruction's immediate and sign-extends it to 64 bits. Copying the sign bit preserves a negative value. The 12-bit pattern 1111 1111 1000 represents −8; zero extension would turn it into 4088 and send a memory operation to the wrong address.

A multiplexer, or mux, selects one input. Muxes choose the ALU's second operand, register write data, and next PC. A mux changes the route; a write enable decides whether a stored value changes.

Data memory has address and write-data inputs, a read-data output, and MemRead and MemWrite controls. A load needs instruction fetch and data access during the same single cycle. Separate instruction and data memories provide both accesses. Separate adders also let PC + 4 and the branch target be computed while the ALU does other work.

Unused outputs can still change during a cycle. Correct control means that only the selected outputs reach enabled state writes. A computed value on an unselected wire has no effect on the program.

Start with what each instruction must read and what it must change. The shared datapath combines these routes, with a multiplexer wherever alternative values meet one input.

Fetch and decode the fields

Fetch uses the PC to read instruction memory and computes PC + 4 in parallel. The opcode occupies bits 6–0. Where present, rd is in bits 11–7, funct3 in 14–12, rs1 in 19–15, and rs2 in 24–20; R-type funct7 occupies bits 31–25. Stable source-field positions allow register reads to begin while instruction control is being decoded. A store or branch has no rd field: bits 11–7 contribute to its immediate.

Compare the execution paths

For a load, the ALU result is an effective address, the address of the data to read. The memory output then returns to the register file. A store also forms an address with the ALU, but its second source value travels separately to the memory's write-data input. Selecting an immediate as the ALU operand must not discard that store value. ImmGen rebuilds the S-format offset from its two groups of bits.

A branch performs two operations in parallel. The ALU subtracts the compared register values; Zero tells whether they match. The branch adder adds the signed byte offset to the branch's own PC. The B-format encoding leaves out the always-zero low bit. ImmGen can reconstruct the complete byte offset, including that zero; a drawing that instead generates the offset in halfword units needs a left shift by one. The shift belongs in the path exactly once.

Merge the paths with muxes

ALUSrc selects either rs2's value or the immediate for the second ALU input. MemtoReg selects either the ALU result or the data-memory output for register write-back. PCSrc selects PC + 4 or the branch target. Two competing results need a selector, not a direct wire joining their outputs.

These paths explain why the load has the longest chain: fetch, register read, address calculation, memory read, and register write all contribute. Arithmetic bypasses data memory; a store bypasses register write-back.

Extend the existing routes

addi x5, x6, 3 reuses the immediate-input ALU path and the ALU-result write-back path. It needs suitable control, but no new datapath unit. jal has an additional requirement: it writes PC + 4 to rd while redirecting the PC without an equality test. Its write-back selector therefore needs a PC + 4 input, and its next-PC logic must support an unconditional jump.

An instruction trace connects the assembly operation to actual wire values. Separate values computed during the cycle from values saved at the ending clock edge.

Use a consistent trace order

1. Fetch from the current PC and identify the instruction fields.
2. Read source registers and form the signed immediate.
3. Select the ALU operands and calculate the result.
4. Perform the requested data-memory access.
5. Select register write data and the next PC.
6. List the state writes at the clock edge.

Add two register values

At PC 400, add x5, x6, x7 has encoding 0x007302B3. Its fields are opcode 0110011, rd 5, funct3 000, rs1 6, rs2 7, and funct7 0000000. With x6 = 25 and x7 = −9, the read ports output 25 and −9. ALUSrc selects the second register value, and the ALU produces 16. MemtoReg selects 16 for write-back. At the edge, x5 becomes 16 and the PC becomes 404. MemRead and MemWrite are both zero.

Load, then store a doubleword

At PC 404, consider ld x5, 16(x6) with x6 = 1000 and memory at 1016 holding 42. ImmGen outputs 16. The ALU computes the address 1016, and data memory returns 42. MemtoReg selects that memory value, so x5 becomes 42 and the PC becomes 408 at the edge. Writing 1016 to x5 would confuse the address with the value stored there.

At PC 408, sd x5, 24(x6) reads x5 = 42 and x6 = 1000. The ALU calculates 1024 while the rs2 path supplies 42 to memory. MemWrite enables the store; RegWrite is zero. At the edge, the doubleword at 1024 becomes 42 and the PC becomes 412. The memory address and store value travel on different wires.

The offsets are measured in bytes. Adjacent RV64 doublewords begin 8 bytes apart: after the doubleword at 1016, the next begins at 1024. Advancing by one byte would not reach the next doubleword.

Decide a branch

At PC 412, beq x8, x9, 12 compares x8 = 7 with x9 = 7. The ALU subtracts to obtain zero. Branch is 1, so Branch AND Zero is 1 and PCSrc selects the branch target. The branch adder produces 424 by adding 12 to 412. Only the PC changes.

If x9 is 8 instead, subtraction produces −1 and Zero is 0. The next PC is then 416. The encoded offset is in units of 2 bytes, so the stored signed quantity for this 12-byte displacement is 6; the complete displacement used by the adder is still 12.

Read the next instruction's state

Each single-cycle instruction completes its work between adjacent clock edges. The next instruction reads the state saved by the previous edge. Thus the store can read the load's new x5 value in the next cycle without pipeline forwarding. Each instruction takes one clock cycle, giving a single-cycle CPI of 1, regardless of how many hardware units its path uses.

The main control unit translates an opcode into steering signals and write permissions. It is a combinational truth table implemented with logic gates: hardwired control.

Give each signal a job

RegWrite enables a write to rd. ALUSrc selects the second ALU input: 0 for rs2, 1 for an immediate. MemRead and MemWrite request the corresponding data-memory access. MemtoReg selects register write data: 0 for the ALU result, 1 for memory data. Branch marks an equality branch. The 2-bit ALUOp tells the separate ALU control unit what operation class is needed.

PCSrc is different: it depends on the instruction and the compared values. The main control asserts Branch, and the ALU supplies Zero. Their AND forms PCSrc, so an ordinary arithmetic result of zero cannot by itself cause a branch.

Build the table from required actions

For ld, the ALU needs an immediate offset, so ALUSrc is 1. The loaded data goes to rd, making MemtoReg and RegWrite both 1. Memory is read, not written, giving MemRead = 1 and MemWrite = 0. Branch is 0, and ALUOp = 00 requests address addition.

For sd, the ALU also adds an offset, but the destination is memory. Set MemWrite = 1 and RegWrite = 0. MemRead stays zero: using memory does not mean reading it. For beq, the ALU uses both register values and subtracts, while the only possible architectural update is the PC.

Use don't-cares only where results are ignored

X is a don't-care, meaning either select value gives the same behavior. MemtoReg may be X for a store or branch because RegWrite is zero. The register-file write-data input is ignored, so the designer may choose the select value that simplifies the circuit.

A state-write enable cannot be treated this way when a write is forbidden. An accidental MemWrite during arithmetic can corrupt memory, even though the arithmetic instruction does not otherwise need that memory output. RegWrite and MemWrite must therefore be explicitly zero for instructions that do not perform those writes.

Add an immediate-arithmetic row

addi x5, x6, 3 takes its second operand from ImmGen and writes the ALU sum. Its row is ALUSrc 1, MemtoReg 0, RegWrite 1, MemRead 0, MemWrite 0, Branch 0, ALUOp 00. Its opcode 0010011 differs from the R-type opcode 0110011, so the main control needs this extra row. Supporting andi and ori also requires decoding their funct3 values to select the operation.

Signal names depend on the design. RegWEn, BSel, and WBSel in other course diagrams describe related write-enable and input-selection jobs. Follow the definition of a signal and its mux inputs when reading a new diagram.

The opcode alone cannot tell add from sub: both belong to the R-type class. Two-level control first identifies the class, then uses the function bits where they matter.

From ALUOp to operation

The main control supplies a 2-bit ALUOp among its other outputs. The ALU control combines it with funct3 and instruction bit 30, part of funct7, to produce four operation-control bits.

These codes describe this ALU implementation, not RISC-V instruction encodings. Loads and stores use ALUOp 00 because they add a base and offset. Equality branches use ALUOp 01 because subtraction produces Zero when the operands match. R-type instructions use ALUOp 10 and need further decoding.

Trace an encoded subtraction

sub x5, x6, x7 has encoding 0x407302B3. The opcode 0110011 identifies R-type and selects ALUOp 10. Its funct3 is 000, which leaves addition and subtraction as possibilities. Bit 30 is 1, from funct7 0100000, so the ALU control outputs 0110 for subtraction.

Changing that function bit to zero yields the corresponding add encoding 0x007302B3, with funct7 0000000 and ALU control 0010. The main-control row stays the same because both instructions use two register inputs, write an ALU result, and do not access data memory.

Reuse the adder for subtraction

In the classic ALU, the control lines represent Ainvert, Bnegate, and a 2-bit operation selector. Subtraction uses the adder after inverting the second operand and supplying a carry-in of 1:

This two's-complement identity allows add and subtract to share hardware. The Bnegate difference accounts for the codes 0010 and 0110; it does not require a separate arithmetic path for every instruction.

Decode bits only in their proper format

For ALUOp 00 or 01, the function-field positions do not select the ALU operation. A load's funct3 011 describes a doubleword access. Store and branch upper bits include immediate bits. Treating those positions as R-type function fields would confuse address formation with arithmetic decoding.

For a quick R-type check, ALUOp 10 with funct3 110 selects 0001, the OR operation. Adding another operation under the same opcode can require only an ALU-control change if the ALU already supports it. A new instruction class can also require main-control changes, as immediate arithmetic does.

A single-cycle processor must finish its slowest instruction before the next edge. Faster instructions still wait for the same fixed clock. Pipelining changes how much work each clock period must contain.

Find the single-cycle limit

Use these component delays, ignoring muxes and small adders: fetch 250 ps, register read 150 ps, ALU 200 ps, data memory 250 ps, and register write 150 ps.

The load is the critical path, setting the period to 1000 ps, or 1 ns. That is a 1 GHz clock. A mix of 25% loads, 10% stores, 50% R-type, and 15% branches has a weighted path delay of 800 ps. Yet every instruction gets 1000 ps, which is 1.25 times that average. An average delay cannot set a clock that must also accommodate the longest instruction.

Overlap five stages

The pipeline divides execution into IF (fetch), ID (decode and register read), EX (execute or calculate an address), MEM (access data memory), and WB (write a register). Different instructions occupy different stages simultaneously.

Throughput counts completed instructions per unit time. Latency measures the time one instruction spends from entry to completion. An assembly line can finish one item per interval even when each item needs several intervals to travel through it. The same distinction applies here.

The slowest stage takes 250 ps. With 20 ps of pipeline-register overhead, the clock period is 270 ps, about 3.70 GHz. One instruction travels through five periods, taking 1350 ps. This exceeds its single-cycle latency, but a full pipeline can complete an instruction every 270 ps.

Include fill and completion time

With no stalls, a k-stage pipeline executes n instructions in k + n − 1 cycles. For five stages this is n + 4. Four instructions need eight cycles, taking 2160 ps, compared with 4000 ps in the single-cycle processor. The speedup is about 1.85.

For 1,000,000 instructions, the pipeline needs 1,000,004 cycles, approximately 270.0 μs. The single-cycle design needs 1000 μs. The speedup approaches the ratio 1000/270, about 3.70, as the fixed fill-and-drain cost becomes small.

Perfect fivefold speedup would require five equally slow 200 ps stages with no register overhead or hazard delays. Unequal stages leave faster stages waiting for the slowest. More stages also add overhead and can increase hazard costs.

Fixed 32-bit instructions in this subset simplify fetch. Stable register fields help ID, and restricting data-memory access to loads and stores fits EX address calculation followed by MEM. These ISA properties make the stage boundaries practical.

Several instructions share the datapath at once, so each stage needs its own instruction's values. Pipeline registers preserve those values and their control signals at each clock edge.

Match contents to later work

Each register is named for its adjoining stages. It captures the outputs of the first stage for use in the second. There is no extra pipeline register after WB; WB writes architectural state. The PC supplies the state at the front of fetch.

The EX/MEM contents above support a design that acts on the branch information in MEM. A design that resolves branches in EX returns that information to fetch sooner. The resolving stage determines the control-hazard penalty.

Keep destination and data together

A load is decoded in ID but writes rd three cycles later in WB. At that time IF/ID contains a younger instruction. If the write port used that younger instruction's rd, the loaded value would go to the wrong register. The load's destination number must therefore travel through ID/EX, EX/MEM, and MEM/WB beside its result.

A store similarly carries its rs2 value through ID/EX and EX/MEM. Its address and data must describe the same store when they reach data memory. Pipeline registers preserve an instruction's identity through these paired values even though several other instructions are active nearby.

Move control with the instruction

Control is generated in ID. EX consumes ALUSrc and ALUOp; MEM consumes Branch, MemRead, and MemWrite; WB consumes MemtoReg and RegWrite. Each stage passes the controls needed later along with the data.

If ALU control is decoded in EX, ID/EX must carry bit 30 and funct3 as well as ALUOp. R-type operations share ALUOp 10, so that value alone cannot distinguish add, sub, AND, and OR. Another valid design decodes the complete 4-bit operation in ID and carries that code instead.

Keep the stage schedule regular

An R-type instruction passes through MEM without using data memory. A store passes through WB without writing a register. Keeping all instructions in the same five-stage schedule preserves the order of register writes. If an R-type instruction skipped MEM, it could reach the single register write port in the same cycle as the load just ahead of it.

The register file serves WB and ID in one cycle by writing in the first half and reading in the second. ID can then see a value written by an older instruction that cycle. Separate instruction and data memories let IF and MEM operate simultaneously.

Most information moves forward through the pipeline. Write-back returns a result to the register file, and branch control returns a next-PC decision to fetch. These long return paths explain why later instructions may need help before an older instruction has finished.

A pipeline diagram makes overlap explicit. Rows show instructions in program order, and columns show clock cycles. Each cell names the stage occupied by that instruction during that cycle.

Build a staircase

For five independent instructions, enter IF for I1 in cycle 1, then ID, EX, MEM, and WB in cycles 2–5. Start I2 one cycle later and repeat. The stage names form a diagonal staircase.

At cycle 5, I1 is in WB, I2 in MEM, I3 in EX, I4 in ID, and I5 in IF. Reading down a column gives a single-cycle snapshot. Following a row gives the history of one instruction.

Number the stages IF = 1 through WB = 5. Without stalls, instruction i reaches stage s in cycle i + s − 1. I3 therefore reaches MEM in cycle 6. The final WB cell gives the completion cycle: five instructions finish in cycle 9.

Put values into a snapshot

Let I1 be ld x5, 16(x6), with x6 = 1000 and memory at 1016 holding 42. Let I2 be an independent add, I3 an independent subtract, and I4 an independent OR. In cycle 4, the load reads memory at 1016, I2 uses the ALU, I3 reads registers, and I4 is fetched. In cycle 5 the load writes 42 into x5. A column contains work from several instructions, not several stages of the load.

Show a stall without stopping older work

Now use ld x10, 0(x20) followed by add x11, x10, x12, then an independent instruction. With forwarding, the immediate consumer still needs one stall:

• The load occupies IF 1, ID 2, EX 3, MEM 4, WB 5.
• The add occupies IF 2, ID 3, ID 4 again, EX 5, MEM 6, WB 7.
• The third instruction occupies IF 3, IF 4 again, ID 5, EX 6, MEM 7, WB 8.

The add waits in ID while a bubble moves through EX. The load continues normally; freezing it would postpone the very value the add needs. Every younger instruction is delayed with the add.

Count the sequence once

A five-stage pipeline needs n + 4 cycles without stalls. Each inserted stall adds one more cycle, giving n + 4 + stalls when there are no other losses. The three-instruction example finishes in cycle 8: three instructions, four extra stage intervals, and one stall.

The first four cycles fill the pipeline, and the last four drain it. These are views of the same n + 4 schedule, not two separate four-cycle charges. For a long sequence their fixed contribution is small; for a short sequence it can dominate the speedup.

A hazard prevents the next instruction from executing in its planned cycle. To diagnose one, identify the resource or value needed, the cycle it is needed, and the cycle it becomes available.

Distinguish three hazard types

Separate instruction and data memories remove the IF/MEM structural conflict. Writing the register file in the first half of a cycle and reading it in the second also allows WB and ID to share it. These arrangements leave no structural hazard in this five-stage model.

Identify the actual producer

A read-after-write (RAW) dependence exists when a later instruction reads a value written by an earlier one. In add x1, x2, x3 followed by sub x4, x1, x5, the add produces x1 and the subtract consumes it. Without help, the subtract reads x1 in ID during cycle 3, before the add writes it in WB during cycle 5.

A write-after-read (WAR) dependence reuses a register after an older instruction has read it. A write-after-write (WAW) dependence gives two instructions the same destination. These name dependences do not cause hazards in the in-order five-stage design: reads occur in ID and writes occur in WB in program order. They matter when deciding whether software may reorder instructions.

Follow a sequence with repeated destinations

Consider:

ld  x5, 0(x10)
add x6, x5, x7
sub x5, x8, x9
or  x9, x6, x5

The RAW links are load → add through x5, add → OR through x6, and subtract → OR through x5. The OR needs the subtract's new x5, not the older loaded value. Looking only for equal register names can miss this change of producer.

The subtract writes x5 after the add reads x5, a WAR dependence. The load and subtract also have a WAW dependence on x5. The OR writes x9 after the subtract reads it, another WAR dependence. None of these creates a WAR or WAW hardware hazard in this ordered pipeline.

Count waits without forwarding

With only the write-then-read register file, an immediate consumer needs two stall cycles. It must delay its ID read from cycle 3 to cycle 5. One independent instruction between producer and consumer reduces this to one stall. Two independent instructions let the consumer reach ID in the producer's WB cycle, requiring none.

A dependence is a property of the program; whether it creates a stall depends on timing and the available paths. A distant RAW dependence may require no action. Register x0 never supplies a pending result because it always reads zero and ignores writes.

Software can insert nop instructions or move independent work into waiting intervals. Hardware can forward results or insert stalls automatically. Both approaches must keep each consumer connected to the value its program-order producer writes.

An ALU result exists before it reaches register write-back. Forwarding, also called bypassing, routes that result directly to a later instruction's input, avoiding a wait for the register file.

Select the source for each operand

Two muxes feed the execution paths. ForwardA serves rs1 and ForwardB serves rs2. Each operand is checked independently.

The EX/MEM path reaches the immediately following instruction. The MEM/WB path reaches an instruction two places behind and can carry either an ALU result or loaded data. ForwardB also supplies the store-data path before ALUSrc chooses between that value and an immediate.

Check permission, destination, and match

For ForwardA = 10, the instruction in EX/MEM must have RegWrite = 1, a nonzero rd, and rd equal to ID/EX.rs1. Replace rs1 with rs2 for the ForwardB test. A store or branch must not be treated as a producer just because its instruction bits happen to resemble a destination number. Writes to x0 must not become forwarded values either.

For ForwardA = 01, perform the corresponding RegWrite, nonzero-rd, and register-match checks on MEM/WB. Use this older result only when EX/MEM does not already provide the required operand. ForwardB follows the same priority rule independently.

Follow one result across later consumers

Start with add x1, x2, x3, where x2 = 10 and x3 = 5. It produces 15 at the end of EX in cycle 3.

• The next instruction, sub x4, x1, x5, reaches EX in cycle 4. With x5 = 3, ForwardA = 10 supplies 15 and the subtraction gives 12.
• and x6, x7, x1 reaches EX in cycle 5. ForwardB = 01 takes x1 from MEM/WB.
• or x8, x1, x9 reads registers in ID during cycle 5, after the add's first-half write. It needs no forwarding in EX.

No stall is needed for these ALU-result dependences. The consumer receives the value when it uses the ALU, even if its earlier ID read obtained a stale value.

Resolve two matching writers

In three consecutive instructions add x1, x1, x2, add x1, x1, x3, and add x1, x1, x4, both EX/MEM and MEM/WB match the third instruction's rs1. EX/MEM holds the second add's result, the newest x1. MEM/WB holds the first add's result and must lose priority.

The same paths let add x5, x6, x7 feed sd x5, 0(x8) without a stall. The forwarded x5 reaches memory's write-data path while the store's ALU uses the immediate offset.

Forwarding cannot supply data before it exists. EX/MEM for a load contains its address, not the loaded value. The immediate consumer must wait until the load finishes MEM; forwarding the address would silently compute with the wrong quantity.

A load produces data at the end of MEM. The immediately following instruction would need that data at the beginning of EX in the same cycle. One stall moves the consumer's EX stage to the next cycle, when MEM/WB can supply the value.

Detect the missing value in ID

The hazard detection unit examines the instruction in EX and the instruction being decoded. The basic test is ID/EX.MemRead = 1 and a match between ID/EX.rd and either source-number field in IF/ID. A refined test excludes rd = x0 and checks which source fields the decoded instruction actually reads.

This last check avoids a false stall on an I-type instruction whose immediate bits occupy the usual rs2 position. Comparing raw field positions is safe but can delay an instruction that does not really read the register.

Hold younger work and advance the load

The stall performs three coordinated actions:

1. Set the controls entering ID/EX to zero, inserting a bubble.
2. Set PCWrite = 0 to keep the fetch address unchanged.
3. Set IF/IDWrite = 0 to retain the instruction waiting in ID.

The load and older instructions keep moving. The bubble passes through later stages without writing registers or memory. Freezing ID/EX with the load still in it would repeat the load instead of inserting an empty operation.

For ld x10, 0(x20) followed by add x11, x10, x12, the load is in EX and the add in ID during cycle 3. In cycle 4, the load is in MEM, the bubble in EX, and the add still in ID. In cycle 5, the load is in WB and the add reaches EX with ForwardA = 01.

Schedule independent instructions

Consider:

ld  x10, 0(x20)
ld  x11, 8(x20)
add x12, x10, x11
sd  x12, 24(x20)
ld  x13, 16(x20)
add x14, x10, x13
sd  x14, 32(x20)

The uses of x11 and x13 immediately follow their loads. With forwarding, these cause two stalls, giving 7 + 4 + 2 = 13 cycles. Move ld x13, 16(x20) to third place, before the first add. It separates the x11 load from its consumer and places x13 far enough ahead of its consumer. The sequence now takes 7 + 4 = 11 cycles.

The move is valid because the load reads x20, which the crossed instructions do not change. Its destination x13 does not affect those instructions. Its address x20 + 16 is distinct from the crossed store's x20 + 24. A load cannot move across a store that might write the bytes it reads. Reordering must preserve RAW, WAR, WAW, and memory dependences.

Combine stalls and forwarding

For ld x5, 0(x10), add x6, x5, x7, sub x5, x8, x9, and or x9, x6, x5, only the immediate load-use pair stalls. When OR reaches EX, ForwardA = 01 supplies the add's x6 and ForwardB = 10 supplies the subtract's x5. The total is 4 + 4 + 1 = 9 cycles.

Fetch needs a new address every cycle. A conditional branch provides the correct choice only after its comparison and target calculation. This gap creates a control hazard.

Relate resolution stage to penalty

In a five-stage pipeline with redirection after the resolving stage, an outcome known at the end of ID loses one fetch slot on a wrong guess. Resolution at the end of EX loses two; at the end of MEM it loses three. Younger instructions have already entered during those slots.

One strategy stalls fetch until every branch is decided. It is simple, but taken and not-taken branches both pay the full wait. Predict not taken instead continues at PC + 4. A correct guess needs no recovery. A taken branch redirects fetch and discards the younger instructions from the sequential path.

Trace a taken branch

Fetch beq x1, x2, 16 at address 100 in cycle 1 and resolve it at the end of EX in cycle 3. Predict-not-taken fetches addresses 104 and 108 in cycles 2 and 3. If the branch is taken, both are wrong-path instructions. Fetch begins at 116 in cycle 4, after a two-cycle penalty.

A flush makes those younger entries unable to change architectural state or raise exceptions. The implementation can invalidate entries or suppress their controls and exception effects. A wrong-path store must never reach an effective memory write.

A bubble is not the same as an all-zero RISC-V instruction. The all-zero encoding is illegal. If a real instruction encoding is inserted, the canonical nop is addi x0, x0, 0, encoded as 0x00000013. A killed pipeline entry instead represents no executed instruction.

Resolve earlier, but get operands earlier

Moving the comparator and branch-target adder to ID reduces the redirection penalty to one cycle. The comparison now needs source values in ID, so the usual EX forwarding alone is insufficient. With suitable ID forwarding, a branch immediately after its producing ALU instruction waits one cycle. Immediately after a producing load, it waits two. Earlier resolution trades fewer lost fetch slots for more demanding operand delivery.

Static prediction fixes a rule in advance. Common rules are always not taken, always taken, and backward taken/forward not taken. A backward branch at a loop's bottom often repeats the loop, making that direction a useful clue.

RISC-V has no branch delay slot. If a branch is taken, its sequential successor is not executed merely because it was fetched. Some older MIPS designs made that successor execute as a defined delay-slot instruction; that is a different ISA rule.

Preserve a precise exception boundary

An illegal instruction or ecall transfers control to a handler. Older instructions finish; the faulting instruction and younger instructions do not commit their normal effects. The processor records the faulting PC and cause, using registers such as sepc/scause in supervisor mode or mepc/mcause in machine mode, then fetches from the handler. This precise exception presents the state as a boundary between completed older instructions and uncompleted later work.

Dynamic prediction learns from outcomes observed while a program runs. A branch history table (BHT) stores small state entries selected using bits from a branch address. Predict first, compare with the real outcome later, then update the entry.

See why one bit loses twice on a loop

A 1-bit predictor stores the previous outcome. If the last branch was taken, it predicts taken next time; otherwise it predicts not taken. For a repeatedly invoked loop whose branch is taken nine times and then not taken once, the exit leaves the bit at not taken.

On the next invocation, the first taken branch is mispredicted. The intervening taken branches train the bit to taken, so the final not-taken exit is also mispredicted. In steady state that is two errors in ten outcomes, or 80% accuracy.

Add a second bit for persistence

A 2-bit saturating counter has states 0 through 3. States 0 and 1 predict not taken; 2 and 3 predict taken. A taken outcome increments the counter, and a not-taken outcome decrements it. Values stop at 0 and 3.

From state 3, one not-taken exit moves the state to 2, which still predicts taken. The next loop entry is therefore predicted correctly. The same ten-outcome loop has one error per invocation in steady state, or 90% accuracy. Two consecutive contrary outcomes are needed to reverse a prediction starting from a strong state.

Trace before updating

Start in state 1 and observe taken, taken, not taken, taken:

1. State 1 predicts not taken: wrong. Increment to 2.
2. State 2 predicts taken: correct. Increment to 3.
3. State 3 predicts taken: wrong. Decrement to 2.
4. State 2 predicts taken: correct. Increment to 3.

There are two errors and the final state is 3. Updating before predicting would incorrectly give the predictor access to the outcome it is supposed to guess.

Distinguish direction, target, and interference

Two branch addresses can index the same BHT entry. This aliasing lets their outcomes interfere. A wrong guess costs cycles, but recovery checks the real outcome and preserves correctness.

A branch target buffer (BTB) supplies an address, not just a direction bit. Looked up by PC during IF, it can provide the predicted taken target for the next fetch cycle before decode. The direction prediction decides whether to use that target.

Simple history has limits. For a strictly alternating taken/not-taken pattern, a 1-bit predictor stays wrong after it follows the pattern. A 2-bit counter is at most half correct; starting in state 1 before a taken outcome makes it wrong every time. Correlating predictors add recent branch history, tournament predictors select between predictors, and a return address stack predicts procedure-return targets. Deeper pipelines make recovery more expensive because more younger work accumulates before resolution.

Pipeline speed depends on both the clock period and the cycles spent waiting or recovering. Effective CPI measures those extra cycles averaged across the instruction stream.

Weight each cost by the affected instructions

For a long single-issue sequence, start with ideal CPI 1. Add each distinct, nonoverlapping source of lost cycles as an affected-instruction fraction times cycles lost per event. A conditional rate needs its parent fraction too.

Suppose 25% of instructions are loads and 40% of those loads have an immediate consumer. Each such pair stalls once, so the load-use contribution is 0.25 × 0.40 × 1 = 0.10 cycles per instruction. Suppose 15% are branches, 10% of those are mispredicted, and recovery costs two cycles. The branch contribution is 0.15 × 0.10 × 2 = 0.03.

Adding the independent costs gives CPI = 1 + 0.10 + 0.03 = 1.13. Charging one stall to every load would produce 0.25 instead of 0.10. Applying the 10% branch-error rate to every instruction would similarly overcount.

Include clock period and instruction count

Execution time equals instruction count × CPI × clock period. A 4 GHz clock has a period of 0.25 ns. For 10⁹ instructions at CPI 1.13, execution takes 10⁹ × 1.13 × 0.25 ns = 0.2825 s. The average time per instruction is 0.2825 ns.

For a short sequence, count fill, drain, and hazard cycles explicitly. The ideal base CPI of 1 describes steady throughput; a five-stage pipeline executing only a few instructions also has its four-cycle fill-and-completion contribution.

Compare branch strategies on equal terms

Keep the load-use cost of 0.10, branch fraction of 0.15, and two-cycle penalty:

At the same clock period and instruction count, dynamic prediction is about 1.24 times as fast as waiting, because 1.40/1.13 ≈ 1.24.

Across different processors, compare CPI × period. A single-cycle design at 1000 ps takes 1000 ps per instruction. A pipeline at 270 ps and CPI 1.13 takes 305.1 ps per instruction, a speedup of about 3.28. Comparing CPI alone would favor the single-cycle CPI of 1 and reach the wrong conclusion.

Understand the next design tradeoff

More pipeline stages can shorten the combinational work per cycle. They also introduce register overhead and can increase load-use and misprediction penalties. Clock frequency alone cannot decide whether the deeper design wins.

Multiple issue starts several instructions per cycle, allowing CPI below 1 and instructions per cycle (IPC) above 1. Static issue groups are chosen by the compiler; dynamic issue, or superscalar execution, is chosen by hardware and often uses speculation and out-of-order execution. Data dependences and branch prediction still limit the useful overlap.