A Retiming Model and the Tool Flow · synthesis

Part 4 · Sequential, FSM and Memory · Intermediate

On this page

A stage-graph model

A stage graph lists block delays and register positions. The period is the largest stage sum, and a move shifts one block across a boundary.

Item	Meaning
Block delay	EXAMPLE combinational delay in ns for one logic block.
Stage	The blocks between two consecutive registers; its sum sets its share of the period.
Period	The largest stage sum; the move below shrinks it from 8 ns to 6 ns.
Register count	Registers on the path, plus the fanout-duplication variant the program checks.

What the program checks

The program below recomputes the balanced pair from the first lesson. It checks the period before and after the move and both register counts.

example.py

import sys

A = 6.0
B = 2.0
C = 4.0

def stage_max(stages):
    m = stages[0]
    for s in stages[1:]:
        if s > m:
            m = s
    return m

before = [A + B, C]
after = [A, B + C]
p_before = stage_max(before)
p_after = stage_max(after)

regs_before = 1
regs_moved = 1
regs_fanout = 2

problems = []
if p_before != 8.0:
    problems.append("before period")
if p_after != 6.0:
    problems.append("after period")
if regs_moved != regs_before:
    problems.append("moved count")
if regs_fanout != regs_before + 1:
    problems.append("fanout count")

if not problems:
    print("PASS: period 8.0 ns before and 6.0 ns after, registers 1 to 1 moved and 1 to 2 across fanout")
    sys.exit(0)
print("FAIL: " + ", ".join(problems))
sys.exit(1)

What the tool flow sketches

The script below is not run: flop-retiming results were not verified on this build, so it is shown as a sketch only.

yosys

# not-run: flop-retiming result not verified on this build, shown as a sketch
read_verilog <<EOV
module pipe2sk(input clk, input [3:0] a, b, output reg [4:0] y1, y2);
  always @(posedge clk) begin
    y1 <= a + b;
    y2 <= y1;
  end
endmodule
EOV
hierarchy -check -top pipe2sk
proc
opt
abc -liberty course.lib -dff
stat -liberty course.lib

A synthesis tool would balance the stages, re-derive reset values and recheck equivalence. The sketch maps with ABC after generic optimization but proves nothing until its assertions run.

Common mistakes

Check yourself All four program checks pass. What does that prove about the real tool flow?

Only that the hand arithmetic is exact. Legality of the move still depends on enables, resets and clocks the model cannot see.

Check yourself Why is the Yosys block marked not-run instead of asserting a smaller area?

Its flop-retiming result was not verified on this build. An unrunnable claim would fail the checker, so the block stays a sketch.

Related topics

Up nextDatapath Synthesis

Practice this lesson Report an error

A stage-graph model

A stage graph lists block delays and register positions. The period is the largest stage sum, and a move shifts one block across a boundary.

Item	Meaning
Block delay	EXAMPLE combinational delay in ns for one logic block.
Stage	The blocks between two consecutive registers; its sum sets its share of the period.
Period	The largest stage sum; the move below shrinks it from 8 ns to 6 ns.
Register count	Registers on the path, plus the fanout-duplication variant the program checks.

What the program checks

The program below recomputes the balanced pair from the first lesson. It checks the period before and after the move and both register counts.

example.py

import sys

A = 6.0
B = 2.0
C = 4.0

def stage_max(stages):
    m = stages[0]
    for s in stages[1:]:
        if s > m:
            m = s
    return m

before = [A + B, C]
after = [A, B + C]
p_before = stage_max(before)
p_after = stage_max(after)

regs_before = 1
regs_moved = 1
regs_fanout = 2

problems = []
if p_before != 8.0:
    problems.append("before period")
if p_after != 6.0:
    problems.append("after period")
if regs_moved != regs_before:
    problems.append("moved count")
if regs_fanout != regs_before + 1:
    problems.append("fanout count")

if not problems:
    print("PASS: period 8.0 ns before and 6.0 ns after, registers 1 to 1 moved and 1 to 2 across fanout")
    sys.exit(0)
print("FAIL: " + ", ".join(problems))
sys.exit(1)

What the tool flow sketches

The script below is not run: flop-retiming results were not verified on this build, so it is shown as a sketch only.

yosys

# not-run: flop-retiming result not verified on this build, shown as a sketch
read_verilog <<EOV
module pipe2sk(input clk, input [3:0] a, b, output reg [4:0] y1, y2);
  always @(posedge clk) begin
    y1 <= a + b;
    y2 <= y1;
  end
endmodule
EOV
hierarchy -check -top pipe2sk
proc
opt
abc -liberty course.lib -dff
stat -liberty course.lib

A synthesis tool would balance the stages, re-derive reset values and recheck equivalence. The sketch maps with ABC after generic optimization but proves nothing until its assertions run.

Common mistakes

Check yourself All four program checks pass. What does that prove about the real tool flow?

Only that the hand arithmetic is exact. Legality of the move still depends on enables, resets and clocks the model cannot see.

Check yourself Why is the Yosys block marked not-run instead of asserting a smaller area?

Its flop-retiming result was not verified on this build. An unrunnable claim would fail the checker, so the block stays a sketch.