Everything in STA, from slack to path reports to ECO decisions, comes from one data structure: the timing graph. If you can build it by hand for a small circuit and compute an arrival time, you can read any timing report. The graph is also why STA is fast: it is a single forward pass.
Every pin of every cell, and every port, is a node. Every cell has arcs from its input pins to its output pins, each carrying a delay. Every wire is an arc from a driver pin to a load pin. Startpoints are where timing paths begin: flop clock pins (the launch), input ports. Endpoints are where they end: flop data pins (the capture), output ports. A path is a chain of arcs from a startpoint to an endpoint.
The latest arrival time at a node is how late the signal can get there; the earliest arrival is how early it can get there. Along one path it is the launch clock arrival plus the sum of the arc delays. Where several paths meet, the later one decides the latest arrival (used for setup) and the earlier one decides the earliest arrival (used for hold). One forward pass in topological order computes both for every node.
illustrative arrival times, launch clock arrival = 0.00 ns
FF1/CK 0.00
FF1/Q = 0.00 + 0.40 = 0.40
U1/A = 0.40 + 0.00 = 0.40
U1/Z = 0.40 + 0.30 = 0.70
U2/A = 0.70 + 0.05 = 0.75
U2/Z = 0.75 + 0.15 = 0.90
FF2/D = 0.90 + 0.05 = 0.95 <- data arrival at the capture flop# Tiny timing graph: latest arrival by forward propagation in topological order.
edges = { # (from, to): delay in ns
("ck", "u1a"): 0.40, ("u1a", "u1z"): 0.30, ("u1z", "u2a"): 0.05,
("u2a", "u2z"): 0.15, ("u2z", "d"): 0.05,
("ck", "alt1"): 0.40, ("alt1", "u2a"): 0.50, # a second, slower route into u2a
}
order = ["ck", "u1a", "alt1", "u1z", "u2a", "u2z", "d"] # topological order
arr = {"ck": 0.0}
for node in order[1:]:
ins = [arr[a] + dly for (a, b), dly in edges.items() if b == node]
arr[node] = max(ins)
assert abs(arr["u2a"] - 0.90) < 1e-9 # the slower route wins: 0.40 + 0.50
assert abs(arr["d"] - 1.10) < 1e-9
print("PASS: latest arrival at d =", round(arr["d"], 2), "ns")The second route into U2/A delivers the signal at 0.90 ns instead of 0.75 ns, so it sets the latest arrival at the endpoint: 0.90 + 0.15 + 0.05 = 1.10 ns. The same pass using the minimum instead of the maximum gives the earliest arrival that hold analysis needs.
Every endpoint has an arrival time computed from a real startpoint; an endpoint with no arrival is unconstrained, which is a finding in its own right.
Reconvergent paths are handled by taking the worst (setup) or best (hold) over all routes, not an average.
Arc delays depend on slew and load, so the graph is only as good as the delay calculation feeding it (see the delay models topic).
Because a node's arrival depends only on its predecessors. Visiting nodes in topological order guarantees every predecessor already has its final value when the node is visited, so a single pass is enough.