Interview Question · Concept
Retiming a Datapath by Hand
The Question
The interviewer asks
A two-stage block computes (a + b) * c, but both registers sit after all the logic. What is retiming, and how would you apply it here?
You have two and a half minutes. Speak or type, then press Get Feedback under your answer. No credits needed.
Speech-to-text runs in your browser. Chrome and Edge may send audio to their own speech service.
You can edit your answer before you send it. Feedback uses AI and checks your answer only against our written answer. No credits are used and your answer is not saved.
Reveal the Model Answer
Retiming moves registers through logic without changing what appears at the outputs, or when. Here the second register buys nothing, so move it back across the multiply. It must go on every path that crosses the cut: the sum and also c. The flop count stays at 34, and the measured depth drops from 42 to 31 levels.
- A: at the output, 29
All three operators sit in stage 1 and stage 2 is a copy. The longest path runs from
a[1]through every operator: 29 levels. - B: after a + b, 23
Stage 1 holds the first add, 15 levels alone. Stage 2 holds the multiply and the second add, 23 alone. c gets a register so its path still crosses two.
- C: after the multiply, 26
Now stage 1 is heavy: the add and the multiply, 26 levels alone, against 20 for stage 2. Worse than B.
- D: inside the multiply, 21
s * 11 is 8s + 3s. Stage 1 computes s and 3s; stage 2 adds 8s, 3s and c. The two stages are 18 and 20 levels alone, 21 together.
Read the diagram as text
- a, b: 8 bits each
- c: 8 bits
- s = a + b: 15 levels alone
- m = s * 11: 19 levels alone
- r = m + c: 20 levels alone
- y: the output register
- a, b → s = a + b: a, b
- s = a + b → m = s * 11: s
- m = s * 11 → r = m + c: m
- c → r = m + c: c
- r = m + c → y: r
From lesson R4.6, a different chain. Moving one register changes the depth of both stages, and levels overlap, so measure each cut.
The original block: both registers after the logic. The bench checks its two-cycle latency.
original: results with a two-cycle latency: 37 of 37Self-Check
Tick each key point you covered in your answer.
What Interviewers Listen For (Mid-Level)
A good mid-level answer moves the register and at once asks which other inputs cross the same cut. It checks the latency and the function against the original.
What Interviewers Listen For (Senior)
A good senior answer mentions that retiming breaks one-to-one flop matching in equivalence checking. It also knows that a register cannot be moved into a feedback loop.
Cross-Questions
Where the interviewer goes next. Open a node to practise that follow-up.
WhyWhat IfProve ItBreak ItCompare
- Retiming a Datapath by Hand
-
WhyEvery Path Must Cross the Same Number of RegistersL2 Mid-Level
Why must a retimed register be placed on every path that crosses the cut?
2:30You have two and a half minutes. Speak or type, then press Get Feedback under your answer. No credits needed.
Speech-to-text runs in your browser. Chrome and Edge may send audio to their own speech service.
You can edit your answer before you send it. Feedback uses AI and checks your answer only against our written answer. No credits are used and your answer is not saved.
Reveal the Model Answer
The output combines values that entered together. If one input crosses one register fewer, it meets the other inputs a cycle early. Then the output mixes data from two different cycles. Counting registers on each input-to-output path is the check.
Self-Check
Tick each key point you covered in your answer.
Misconception
"Only the long path needs the register."
The register count matters on every path, not only the slow one. A short path without it arrives in the wrong cycle.
Source Measured: the twin on this question, Icarus Verilog 12
-
Break ItRetiming into a Feedback LoopL3 Senior
How would retiming break an accumulator,
acc <= acc + x?2:30You have two and a half minutes. Speak or type, then press Get Feedback under your answer. No credits needed.
Speech-to-text runs in your browser. Chrome and Edge may send audio to their own speech service.
You can edit your answer before you send it. Feedback uses AI and checks your answer only against our written answer. No credits are used and your answer is not saved.
Reveal the Model Answer
A loop has a fixed number of registers. Moving one more register into it makes the loop take two cycles to go round. The result is then two interleaved sums, not one. Speeding up a loop needs a different algorithm or a faster adder, not a moved register.
Self-Check
Tick each key point you covered in your answer.
Misconception
"Pipeline the adder inside the accumulator to double the clock."
The adder needs its own previous result every cycle. A register in the loop delays that result, so the sum changes meaning.
Source Lesson R4.6 review claims (a register moved into the accumulator loop splits it into two interleaved sums, measured)
-
What IfTwo Interleaved AccumulatorsL3 Senior
Asked if they suggest pipelining anyway
What if you accept the two interleaved sums? Can that still give a faster accumulator?
2:30You have two and a half minutes. Speak or type, then press Get Feedback under your answer. No credits needed.
Speech-to-text runs in your browser. Chrome and Edge may send audio to their own speech service.
You can edit your answer before you send it. Feedback uses AI and checks your answer only against our written answer. No credits are used and your answer is not saved.
Reveal the Model Answer
Yes. Two partial sums, one for even inputs and one for odd, each get two cycles for their adder. At the end, one more add combines them. This is a real technique, but it changes the design: an extra cycle and an extra adder at the end.
Self-Check
Tick each key point you covered in your answer.
Half-Truth
"The two sums are a bug, so the idea is useless."
They are a bug only if nobody adds them back. Done on purpose, they trade one adder for a faster loop.
Source Lesson R4.6 review claims (the interleaved sums of the split accumulator, measured)
-
CompareRetiming Versus PipeliningL2 Mid-Level
Compare retiming with pipelining.
2:30You have two and a half minutes. Speak or type, then press Get Feedback under your answer. No credits needed.
Speech-to-text runs in your browser. Chrome and Edge may send audio to their own speech service.
You can edit your answer before you send it. Feedback uses AI and checks your answer only against our written answer. No credits are used and your answer is not saved.
Reveal the Model Answer
Pipelining adds registers, so latency grows and the rest of the system must accept it. Retiming only moves existing registers, so latency and the interface stay the same. Retiming is the first thing to try when a stage is badly balanced. Pipelining is for when every stage is already full.
Self-Check
Tick each key point you covered in your answer.
Half-Truth
"Retiming is free."
Moved registers may need more flops when a cut crosses more wires than before. Netlist equivalence checking also gets harder.
Source Seligman, Schubert and Kiran Kumar, Formal Verification (2nd ed., 2023) ch. 8 Types of equivalence to check: combinational and sequential equivalence
-
Prove ItSolve R4.6.1: Retime a Scaler by HandSimulator-graded
Show it, don't just say it: this Silicon Lab problem is graded by the simulator.
What People Get Wrong
Common wrong answers and why they fail. Run It shows the wrong belief failing on a real simulator.
Missed Corner
"Move the register back onto the sum; c goes straight to the multiplier."
Then c is used one cycle earlier than a and b. Every path through the cut needs the register. The twin compares the result with the original.
Run It
The candidate's version (register on the sum only) against the original, every cycle.
retimed version equal to the original: 0 of 37 FAIL: moving the register onto the sum alone changed the function; c also crosses the cutSee the Fix
// y = (a + b) * c with two register stages; both registers sit after all the logic.
module scale_out (input logic clk, input logic [7:0] a, b, c, output logic [16:0] y);
logic [16:0] r_q;
always_ff @(posedge clk) begin
r_q <= (9'(a) + 9'(b)) * c;
y <= r_q;
end
endmodule
// Retimed: the register moved back across the multiply, onto every path that crosses the cut.
module scale_new (input logic clk, input logic [7:0] a, b, c, output logic [16:0] y);
logic [8:0] s_q;
logic [7:0] c_q;
always_ff @(posedge clk) begin
s_q <= 9'(a) + 9'(b);
c_q <= c;
y <= s_q * c_q;
end
endmodule
module tb;
logic clk = 0;
always #5 clk = ~clk;
logic [7:0] a = 0, b = 0, c = 0;
logic [16:0] y_ref, y_new, hist[0:1];
int checked = 0, same = 0, lat2 = 0;
int unsigned seed = 11;
scale_out ref_dut (.clk(clk), .a(a), .b(b), .c(c), .y(y_ref));
scale_new new_dut (.clk(clk), .a(a), .b(b), .c(c), .y(y_new));
initial begin
for (int i = 0; i < 40; i++) begin
@(posedge clk); #1;
if (i >= 3) begin
checked++;
if (y_ref == hist[1]) lat2++;
if (y_new == y_ref) same++;
end
hist[1] = hist[0];
a = $urandom(seed); b = $urandom(seed); c = $urandom(seed);
hist[0] = (a + b) * c;
end
$display("retimed version equal to the original: %0d of %0d", same, checked);
if (same == checked) $display("PASS: with c registered too, the retimed block matches every cycle");
$finish;
end
endmodule
Prints: retimed version equal to the original: 37 of 37 PASS: with c registered too, the retimed block matches every cycle
Misconception
"Retiming means adding a pipeline stage."
Adding a stage changes latency. Retiming keeps the latency and the register count on each path; it only moves where the registers sit.
Source Seligman, Schubert and Kiran Kumar, Formal Verification (2nd ed., 2023) ch. 8 Types of equivalence to check: combinational and sequential equivalence
Wrong Altitude
Says "the tool will retime it" and stops.
Many flows leave retiming off, and the site flow does too. The interviewer wants to see the cut placed by hand and checked.