The number of distinct paths in a design is astronomically large, far beyond enumeration. STA can still report the worst of them because it never lists paths: it propagates times node by node. Understanding that is what lets you reason about runtime, incremental analysis and why a small ECO re-times only part of the design.
# A chain of k diamonds (two parallel routes per stage): paths double per stage, edges grow linearly.
def stats(k):
paths, edges = 1, 0
for _ in range(k):
paths *= 2 # two routes through each diamond
edges += 4 # in->a, in->b, a->out, b->out
return paths, edges
for k in (1, 10, 20):
p, e = stats(k)
print(f"k={k:2d}: paths={p:>9,} edges visited per pass={e}")
p20, e20 = stats(20)
assert p20 == 1_048_576 and e20 == 80
assert stats(10) == (1024, 40)
print("PASS: 20 diamonds have", p20, "paths but a pass touches only", e20, "edges")Twenty simple diamonds already give over a million paths, while one propagation pass touches 80 edges. Real blocks have millions of nodes and unimaginably many paths; the cost of STA tracks nodes plus edges. Path-based reports (the top-N worst paths) are generated from the propagated data by backtracking from the worst endpoints, not by searching all paths. Backtracking along the worst predecessor at each node recovers only the single worst path per endpoint; further paths come from enumerating near-worst deviations (k-best path enumeration).
Change | What must be recomputed |
|---|---|
Resize one cell | Arrival times in its fanout cone; required times in its fanin cone; the slews it changes |
Add a buffer | The same cones, plus the net it splits |
Change a constraint | Potentially everything it touches (a clock change touches all its flops) |
Change a parasitic | The net and the stages around it |
Runtime growth is roughly linear with size; an unexplained jump points to a constraint or a loop problem.
Incremental results are validated by a periodic full re-time, since incremental updates can drift.
Path-based analysis (more accurate, slower) is used on the worst endpoints for final signoff, graph-based for everyday runs.
The forward and backward propagations produce arrival, required and slack at every node. The worst endpoints are known from them, and the single worst path to each of those endpoints is recovered by backtracking along the worst predecessor at each node; further paths come from enumerating near-worst deviations (k-best path enumeration).