Digital Design / Module 8: Arithmetic and datapaths
47. Pipelining
Increase throughput with registers.
See it move
The idea
If a calculation takes too long for one clock cycle, split it into stages with registers between them. Each stage does part of the work, so the clock can run faster. Think of a car assembly line: a car still takes the same total labour, yet a finished car leaves every few minutes.
What changes
- Throughput improves: one result per cycle, at a higher clock rate.
- Latency gets worse: each result takes more cycles, and usually slightly more time overall.
For total logic delay T and flop overhead t ( plus setup), k stages give a clock period of about T/k + t.
Diminishing returns
With T = 12 ns and t = 0.5 ns:
| Stages | Period | Relative speed |
|---|---|---|
| 1 | 12.5 ns | 1.0 x |
| 3 | 4.5 ns | 2.8 x |
| 6 | 2.5 ns | 5.0 x |
| 12 | 1.5 ns | 8.3 x |
More stages never quite pay off in proportion, since the flop overhead stays constant, and logic can't always be cut evenly. Flops also cost area and clock power.
Keeping things aligned
Any signal that belongs with the data must be delayed by the same number of stages.
always_ff @(posedge clk) begin
s1 <= a + b; v1 <= in_valid;
s2 <= s1 * c; v2 <= v1;
endIf the valid bit takes a different path, it will pair with the wrong data. This is a very common pipelining bug.
Hazards
In a CPU, a later instruction might need a result still in the pipeline. That is a hazard, and it requires forwarding or stalling. A pure streaming pipeline with no feedback avoids this.
Common mistake
Pipelining a path that has feedback, such as a counter or an accumulator, without considering the consequences. Registers inside a feedback loop change the function: each result arrives too late for the next calculation.
Key ideas
- Cut long combinational paths into stages.
- Latency increases; clock rate may rise.
- Keep valid signals and data aligned.
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
out_valid <= v1;
Why it failed
The data passes through two registers, while valid passes through one. Anything that travels with the data needs the same number of stages. When a pipeline gets another stage, this is exactly the line people forget.
Interview questions
coreLatency or throughput: which does pipelining improve?
Throughput, usually at the cost of more latency.
basicA calculation has 12 ns of logic, and each flop adds 0.5 ns of overhead. What are the clock period, frequency and latency with 4 equal stages?
Each stage has 12 / 4 = 3 ns of logic, plus 0.5 ns, giving a 3.5 ns period, about 285.7 MHz. Unpipelined, the period is 12.5 ns (80 MHz). The latency is 4 x 3.5 = 14 ns, which is longer than 12.5 ns, because every stage pays the flop overhead. Throughput rises about 3.6 times, while each single result takes slightly longer.
basicWhen you pipeline a datapath, why must the valid bit also pass through the same number of registers?
The valid bit says which cycles carry real data. If the data takes two cycles and valid takes one, valid rises a cycle early, and the consumer captures whatever is in the pipeline then, usually the previous or an empty value. Every signal that belongs to a piece of data, such as valid, tags or other operands, must be delayed by exactly the same number of stages.
coreThis two-stage pipeline computes (a + b) x c. With inputs (3, 4, 5), then (1, 1, 9), then (2, 6, 3), the outputs are 63, 6 and 0 instead of 35, 18 and 24. Why?
always @(posedge clk) begin s1 <= a + b; s2 <= s1 * c; end
Stage 2 uses c directly, but by then c belongs to the next input, because a + b was registered and c was not. So the first result is (3 + 4) x 9 = 63 instead of 35. The fix is to register c alongside the sum (c1 <= c) and use s1 * c1. Simulation shows 63, 6 and 0 with the bug, and 35, 18 and 24 with the fix.
core12 ns of logic is cut into three stages of 5, 3 and 4 ns, and each flop adds 0.5 ns. What clock period do you get, and what would perfect balance give?
The slowest stage sets the clock: 5 + 0.5 = 5.5 ns, about 181.8 MHz. Perfectly balanced stages of 4 ns each would give 4.5 ns, about 222 MHz. Unbalanced cuts waste the extra stages, which is why moving logic between stages, or retiming, matters.
coreA 3-stage pipeline runs at 4.5 ns. How long does it take to process 1000 independent items, and how does that compare with an unpipelined 12.5 ns design?
The first result appears after 3 cycles, and then one result comes out every cycle, so 1000 items take 1000 + 2 = 1002 cycles. That is 1002 x 4.5 = 4509 ns. Unpipelined, it takes 1000 x 12.5 = 12500 ns, so the speedup is about 2.77 times. The fill time only matters for short runs.
coreAn accumulator is 'pipelined' by adding a register inside its feedback loop. With inputs 1 to 8, what does the output become?
always @(posedge clk) begin r <= accp + x; // adder output registered accp <= r; // fed back one cycle later end
It no longer computes a running total. Each sum now reaches the adder one cycle late, so the loop holds two independent sums that alternate: one adds the odd-numbered inputs, the other the even-numbered ones. With inputs 1 to 8, the final values are 1 + 3 + 5 + 7 = 16 and 2 + 4 + 6 + 8 = 20, instead of a single total of 36. Simulation shows the sequence 1, 2, 4, 6, 9, 12, 16, 20. Registers inside a loop change the function, so loops need a different technique.
advancedWith 12 ns of logic and 0.5 ns of flop overhead, what speedup do 100 stages give, and what is the limit?
With 100 stages, the period is 0.12 + 0.5 = 0.62 ns, a speedup of 12.5 / 0.62, about 20 times, not 100. Even with endless stages, the period can't go below the 0.5 ns overhead, so the limit is 12.5 / 0.5 = 25 times. In practice, uneven logic cuts, clock skew, and the area and clock power of many flops stop you well before that.
advancedIn a classic five-stage CPU pipeline, why can't forwarding alone remove the stall after a load whose result is used by the very next instruction?
A load's data is available only at the end of the memory stage, but the next instruction needs it at the start of its execute stage, which happens in that same cycle. Forwarding moves data across stages, but it can't send it backward in time. So the pipeline must insert one bubble, and then forward from the memory stage's output. Compilers try to schedule an independent instruction into that slot.