A five-node DAG stands in for placed cells: source S feeds A and B, both feed C, and C feeds endpoint OUT. Edge labels are EXAMPLE stage delays in ns.
The endpoint requires 1.50 ns. Every number below is hand-checkable against the diagram.
The forward pass takes the maximum over incoming edges: each arrival is the latest input plus its edge. The backward pass takes the minimum over outgoing edges: each required time is the tightest successor minus its edge.
Slack at each node is required minus arrival. Nodes with the smallest slack form the critical path.
EXAMPLE parameters (not real library values), all in ns
forward (arrival = max over inputs plus edge):
A = 0.00 + 0.30 = 0.30; B = 0.00 + 0.50 = 0.50
C = max(0.30 + 0.40, 0.50 + 0.10) = max(0.70, 0.60) = 0.70
OUT = 0.70 + 0.60 = 1.30
backward (required = min over successors minus edge), OUT required 1.50:
C = 1.50 - 0.60 = 0.90; A = 0.90 - 0.40 = 0.50; B = 0.90 - 0.10 = 0.80
S = min(0.50 - 0.30, 0.80 - 0.50) = min(0.20, 0.30) = 0.20
slack = required - arrival:
S 0.20 - 0.00 = 0.20; A 0.50 - 0.30 = 0.20; B 0.80 - 0.50 = 0.30
C 0.90 - 0.70 = 0.20; OUT 1.50 - 1.30 = 0.20
critical path: S -> A -> C -> OUT at slack 0.20 nsThe program below runs both passes on the example graph. Its fifteen self-checks repeat every hand number from the block above plus the critical path.
import sys
ORDER = ["S", "A", "B", "C", "OUT"]
PREDS = {
"S": [],
"A": [("S", 0.30)],
"B": [("S", 0.50)],
"C": [("A", 0.40), ("B", 0.10)],
"OUT": [("C", 0.60)],
}
REQ_OUT = 1.50
SUCCS = {n: [] for n in ORDER}
for n, plist in PREDS.items():
for p, d in plist:
SUCCS[p].append((n, d))
arrival = {"S": 0.0}
for n in ORDER[1:]:
arrival[n] = max(arrival[p] + d for p, d in PREDS[n])
required = {"OUT": REQ_OUT}
for n in reversed(ORDER[:-1]):
required[n] = min(required[s] - d for s, d in SUCCS[n])
slack = {n: required[n] - arrival[n] for n in ORDER}
cur = "S"
path = ["S"]
while cur != "OUT":
nxt = min(SUCCS[cur], key=lambda pd: (slack[pd[0]], pd[0]))[0]
path.append(nxt)
cur = nxt
def close(got, want):
return abs(got - want) < 1e-9
checks = [
(arrival["A"], 0.30),
(arrival["B"], 0.50),
(arrival["C"], 0.70),
(arrival["OUT"], 1.30),
(required["OUT"], 1.50),
(required["C"], 0.90),
(required["A"], 0.50),
(required["B"], 0.80),
(required["S"], 0.20),
(slack["S"], 0.20),
(slack["A"], 0.20),
(slack["B"], 0.30),
(slack["C"], 0.20),
(slack["OUT"], 0.20),
]
ok = True
for i in range(len(checks)):
got, want = checks[i]
if not close(got, want):
print("FAIL: check " + str(i + 1) + " got " + str(got) + " want " + str(want))
ok = False
if path != ["S", "A", "C", "OUT"]:
print("FAIL: critical path " + str(path))
ok = False
if not ok:
sys.exit(1)
print("PASS: calculator matches hand arrival, required and slack on 15 checks")0.70 ns, set by the A branch. Arrival takes the maximum.
The code agrees with the hand arithmetic on every node and the critical path. It leaves open whether the EXAMPLE delays match any real library.