The unpipelined circuit below has a latency of 53 ns and a throughput of one result every 53 ns, because its slowest register-to-register path (blocks 1, 30, 20 and 2) adds up to 53 ns. Pipelining it for maximum throughput means giving the 30 ns block a stage of its own: the clock period drops to 30 ns, so throughput rises to one result every 30 ns (about 33.3 million results per second), while latency grows to three cycles, or 90 ns. The rest of this post works through why, how to place the registers with retiming, and what interviewers usually ask next.
Key takeaways
- Latency is the time for one input to reach the output. Throughput is how many results come out per second.
- With ideal registers, the clock period equals the delay of the slowest register-to-register path.
- Pipelining adds registers; retiming moves them across logic without changing what the circuit computes.
- The largest indivisible block sets a floor on the clock period. Here that is 30 ns.
- Pipelining raises throughput but never reduces latency, and here it increases it from 53 ns to 90 ns.
- A quick correctness check: every path from input to output must cross the same number of registers.
The problem
Pipelining is a particular form of retiming where the goal is to increase the throughput (number of results per second) of a circuit. Consider the circuit diagram below: the solid rectangles are registers and the square boxes are blocks of combinational logic.
Each combinational block is labelled with its propagation delay in ns. Assume the registers are ideal: zero propagation delay and zero setup and hold times. Reading the diagram, block 1 feeds blocks 30 and 4; block 30 feeds blocks 3 and 20; block 4 feeds block 20; blocks 3 and 20 both feed block 2, which drives the output register.
- What are the latency and throughput of the circuit above? Latency is how long it takes for a value in the input register to be processed and the result to appear at the output register. Throughput is the number of results per second.
- Pipeline the circuit for maximum throughput. Pipelining adds registers to a circuit; we do this by adding registers at the output and then using the retiming transformation to move them between the combinational blocks. What are the latency and throughput of the resulting circuit?
Solution part 1: the unpipelined circuit
The clock period is set by the longest path, in time, through the combinational logic between the two registers. There are three input-to-output paths:
| Path | Delay sum | Total |
|---|---|---|
| 1, 30, 20, 2 | 1 + 30 + 20 + 2 | 53 ns (critical) |
| 1, 30, 3, 2 | 1 + 30 + 3 + 2 | 36 ns |
| 1, 4, 20, 2 | 1 + 4 + 20 + 2 | 27 ns |
So the register-to-register TPD is 53 ns. A value in the input register is processed in one clock cycle, giving a latency of 53 ns, and the circuit produces one output every cycle, giving a throughput of 1 result per 53 ns (about 18.9 million results per second).
Solution part 2: pipelining for maximum throughput
Find the floor first
No amount of pipelining can make the clock period shorter than the slowest single block, because a register cannot be placed inside a block. The 30 ns block is the floor, so the best achievable period is 30 ns, and the goal is to get the 30 block into its own pipeline stage. Block 1 cannot share a stage with it (1 + 30 = 31 ns), and block 20 cannot either (30 + 20 = 50 ns).
Draw the retiming contours
Add two registers at the output, then retime them backwards into the logic using contours. Each contour is a closed line; wherever it cuts a wire, one register is placed on that wire, and the register it consumed at the output disappears. The contours look like this:
There is an alternative way to draw the contours that also isolates the 30 block, and other implementation considerations, such as register count or which signals are wide, might make one choice more attractive. We could equally have added registers at the input and retimed them forwards into the circuit.
The pipelined circuit
The contours above lead to the following pipelined circuit:
The stages are now:
| Stage | Blocks | Longest path |
|---|---|---|
| 1 | 1 | 1 ns |
| 2 | 30 (and 4 in parallel) | 30 ns |
| 3 | 20 then 2 (and 3 then 2) | 22 ns |
A good check that the retiming is correct is to confirm that every path from input to output crosses the same number of registers. Counting the output register, each of the three paths passes through three registers after the input register, so the data on all branches stays aligned.
The register-to-register TPD is now 30 ns, so the throughput of the pipelined circuit is 1 result per 30 ns (about 33.3 million results per second), a speed-up of 53/30, or about 1.77 times. The latency has increased to 3 clock cycles, or 90 ns.
Why latency went up
Pipelining never reduces latency, and in practice it almost always increases it. Every stage must last a full clock period, even a stage with very little logic in it. Stage 1 here does 1 ns of work but still takes 30 ns, and stage 3 does 22 ns of work in a 30 ns slot. Only if every stage were perfectly balanced and the registers were ideal would latency stay at the original 53 ns. Fortunately latency matters less than throughput for many digital processing circuits, microprocessors and signal processing pipelines among them, where the number of results per second counts for more than the time taken by any single result.
Comparing the options
Interviewers often ask whether a cheaper pipeline would do. A two-stage version with registers after block 30 and after block 4 puts blocks 1 and 30 in the first stage and blocks 20 and 2 in the second:
| Design | Clock period | Throughput | Latency | Added registers |
|---|---|---|---|---|
| Unpipelined | 53 ns | 1 per 53 ns | 53 ns (1 cycle) | 0 |
| Two stages | 31 ns | 1 per 31 ns | 62 ns (2 cycles) | 3 |
| Three stages | 30 ns | 1 per 30 ns | 90 ns (3 cycles) | 5 |
The two-stage design gets within 1 ns of the best period with less added latency and fewer registers. The third stage buys only about 3 percent more throughput for 28 ns of extra latency. In a real design that trade-off would usually favour two stages unless the 30 ns figure is a hard target.
Adding real register overhead (illustrative)
Real flip-flops are not ideal. Suppose, as an illustrative figure, each register adds 0.5 ns of clock-to-Q delay plus 0.3 ns of setup time, 0.8 ns per stage. The unpipelined period becomes 53.8 ns, the two-stage period 31.8 ns and the three-stage period 30.8 ns. The speed-up of the three-stage design drops from 1.77 to about 1.75, and the gap to two stages narrows further. As stages get shorter, this fixed overhead takes a larger share of each cycle, which is why very deep pipelines give diminishing returns.
A Verilog model of the retiming
The model below replaces each block with a simple arithmetic function so the two versions can be compared cycle by cycle. The pipelined module places registers exactly where the contours cut the wires. The testbench checks that the pipelined output always equals the unpipelined output two cycles later, which is the extra latency the retiming adds. It compiles and passes in Icarus Verilog 12.0.
// Block functions stand in for the six combinational blocks
// (names follow the delays in the figure: B1, B30, B3, B4, B20, B2).
module unpiped (input clk, input [7:0] din, output reg [7:0] dout);
reg [7:0] in_r;
wire [7:0] n1 = in_r + 8'd1; // block "1"
wire [7:0] n30 = n1 * 8'd3; // block "30"
wire [7:0] n3 = n30 ^ 8'h5A; // block "3"
wire [7:0] n4 = n1 + 8'd4; // block "4"
wire [7:0] n20 = n30 + n4; // block "20"
wire [7:0] n2 = n3 + n20; // block "2"
always @(posedge clk) begin
in_r <= din;
dout <= n2;
end
endmodule
module piped (input clk, input [7:0] din, output reg [7:0] dout);
reg [7:0] in_r;
reg [7:0] r1a, r1b; // contour 1: after block 1 (to 30 and to 4)
reg [7:0] r30a, r30b; // contour 2: after block 30 (to 3 and to 20)
reg [7:0] r4; // contour 2: after block 4
wire [7:0] n1 = in_r + 8'd1;
wire [7:0] n30 = r1a * 8'd3;
wire [7:0] n4 = r1b + 8'd4;
wire [7:0] n3 = r30a ^ 8'h5A;
wire [7:0] n20 = r30b + r4;
wire [7:0] n2 = n3 + n20;
always @(posedge clk) begin
in_r <= din;
r1a <= n1; r1b <= n1;
r30a <= n30; r30b <= n30; r4 <= n4;
dout <= n2;
end
endmodule
module tb;
reg clk = 0;
always #5 clk = ~clk;
reg [7:0] din = 0;
wire [7:0] u, p;
reg [7:0] u_d1, u_d2;
integer i, errors = 0;
unpiped U (.clk(clk), .din(din), .dout(u));
piped P (.clk(clk), .din(din), .dout(p));
always @(posedge clk) begin u_d1 <= u; u_d2 <= u_d1; end
initial begin
for (i = 0; i < 40; i = i + 1) begin
@(negedge clk);
if (i > 5 && p !== u_d2) begin
errors = errors + 1;
$display("Mismatch at cycle %0d: piped=%0d expected=%0d", i, p, u_d2);
end
din = $random;
end
if (errors == 0) $display("PASS: pipelined output equals unpipelined output two cycles later");
$finish;
end
endmoduleHow interviewers probe this question
- What limits the best clock period? The slowest block that cannot be split, here 30 ns, plus register overhead in a real design.
- How do you know the retimed circuit is correct? Equal register counts on every input-to-output path; in a design flow, sequential equivalence checking.
- Why not cut the 30 ns block? You can if you own its internals. Splitting it into two 15 ns halves would let the period fall to 22 ns, set by blocks 20 and 2 together, until those are split too.
- What about feedback loops? Retiming cannot change the number of registers around a loop, so a loop with one register cannot be pipelined this way. Techniques such as look-ahead or interleaving are needed.
- What does it cost? More registers, more clock power, more latency, and in processors more hazards and a larger branch penalty.
Common mistakes
- Adding the delays of all blocks (60 ns) instead of finding the longest path (53 ns).
- Forgetting that parallel branches need matching registers, which leaves block 20 or block 2 combining data from different input samples.
- Claiming latency stays the same after pipelining; it is the number of cycles times the new period.
- Ignoring register setup and clock-to-Q delays when quoting real speed-ups.
FAQ
Is pipelining the same as retiming?
Not quite. Retiming moves existing registers without changing the circuit's input-output behaviour. Pipelining first adds registers, which changes latency, and then uses retiming to place them well.
Does pipelining always improve throughput?
Only when the critical path is split. Adding a stage around a short path, or a stage that the slowest block still dominates, adds latency without raising throughput.
What is the maximum throughput of this circuit?
With ideal registers and indivisible blocks, one result every 30 ns, about 33.3 million results per second.
How many registers does the three-stage version add?
Five, one on each wire the contours cut: two after block 1, two after block 30 and one after block 4. The two-stage version adds three.
Your comments will be moderated before it appears here.