Static timing analysis

Deep dive

How it works

Parts:

• timing graph — nodes (pins, events, tasks) and arcs with a [min, max] delay; in a chip, cell arcs and net arcs between pins
• constraints — arrival at sources, required times at endpoints (period, setup, hold), exceptions
• delay calculator — fills arc delays; Liberty tables look delay up by input slew and output load, with interpolation
• propagator — topological order, forward and backward passes
• reporter — slack per node, WNS, TNS, path extraction

Steps:

1. Kahn topological sort; leftover nodes mean a loop.
2. Forward in order: late[w] = max(late[v] + max), early[w] = min(early[v] + min); remember the predecessor that won.
3. Endpoints get required times: setup T - t_setup (plus clock skew), hold t_hold (plus skew).
4. Backward in reverse order: req_max[v] = min(req_max[w] - max), req_min[v] = max(req_min[w] - min).
5. Setup slack req_max - late, hold slack early - req_min; every node on one critical path has the same minimum slack.
6. Back-track predecessors from the worst endpoint; report WNS (worst, clamped at 0 by OpenSTA) and TNS.
7. After an edit, recompute only nodes whose arrival or required time changes.

 sources --(min,max)--> [v] --(min,max)--> endpoint
   late/early  ->  forward pass           required: T - setup  /  hold
   slack(v) = req_max(v) - late(v)   <-  backward pass

Chip-specific: OpenSTA's default analysis type is on-chip variation, where setup uses max for data and min for clock paths and hold the opposite; set_timing_derate scales early or late delays, and bc_wc or single select corners. set_false_path disables timing along from/through/to objects; set_multicycle_path allows several clock cycles for a check. These are per-pair rules, so tools carry extra state per node instead of one number.

Code

const INF: i64 = i64::MAX / 4;
pub struct Edge { pub to: usize, pub min: i64, pub max: i64 }
pub struct Timing { pub from: Vec<usize>, pub late: Vec<i64>, pub early: Vec<i64>, pub req_max: Vec<i64>, pub req_min: Vec<i64> }
impl Timing {
    pub fn setup_slack(&self, v: usize) -> i64 { self.req_max[v] - self.late[v] }
    pub fn hold_slack(&self, v: usize) -> i64 { self.early[v] - self.req_min[v] }
}
/// start[v]: arrival at sources (-INF elsewhere); end_max/end_min: required times at endpoints (INF / -INF elsewhere).
pub fn analyze(adj: &[Vec<Edge>], start: &[i64], end_max: &[i64], end_min: &[i64]) -> Option<Timing> {
    let n = adj.len();
    let mut indeg = vec![0u32; n];
    for e in adj.iter().flatten() { indeg[e.to] += 1; }
    let mut order: Vec<usize> = (0..n).filter(|&v| indeg[v] == 0).collect();
    let mut i = 0;
    while i < order.len() { // Kahn
        let u = order[i]; i += 1;
        for e in &adj[u] { indeg[e.to] -= 1; if indeg[e.to] == 0 { order.push(e.to); } }
    }
    if order.len() != n { return None; } // combinational loop
    let mut late = start.to_vec();
    let mut early: Vec<i64> = start.iter().map(|&s| if s == -INF { INF } else { s }).collect();
    let mut from = vec![usize::MAX; n];
    for &v in &order {
        for e in &adj[v] {
            if late[v] > -INF / 2 && late[v] + e.max > late[e.to] { late[e.to] = late[v] + e.max; from[e.to] = v; }
            early[e.to] = early[e.to].min(early[v] + e.min);
        }
    }
    let (mut req_max, mut req_min) = (end_max.to_vec(), end_min.to_vec());
    for &v in order.iter().rev() {
        for e in &adj[v] {
            req_max[v] = req_max[v].min(req_max[e.to] - e.max);
            req_min[v] = req_min[v].max(req_min[e.to] - e.min);
        }
    }
    Some(Timing { from, late, early, req_max, req_min })
}
pub fn critical_path(t: &Timing, end: usize) -> Vec<usize> {
    let mut p = vec![end];
    while t.from[*p.last().unwrap()] != usize::MAX { p.push(t.from[*p.last().unwrap()]); }
    p.reverse(); p
}
fn main() {
    let g = |a: &[(usize, usize, i64, i64)], n| {
        let mut adj: Vec<Vec<Edge>> = (0..n).map(|_| vec![]).collect();
        for &(u, v, min, max) in a { adj[u].push(Edge { to: v, min, max }); }
        adj
    };
    // Chip-style, ps: period 10, setup 1, hold 2; arcs (from, to, min, max)
    let mut adj = g(&[(0, 1, 1, 2), (0, 2, 2, 5), (1, 3, 1, 3), (2, 3, 1, 4), (3, 4, 1, 2), (1, 5, 1, 1)], 6);
    let mut start = vec![-INF; 6]; start[0] = 0;
    let (mut em, mut en) = (vec![INF; 6], vec![-INF; 6]);
    for v in [4, 5] { em[v] = 10 - 1; en[v] = 2; }
    let t = analyze(&adj, &start, &em, &en).unwrap();
    // late = [0,2,5,9,11,3]; req_max = [-2,4,3,7,9,9]; slack = [-2,2,-2,-2,-2,6]
    assert_eq!(t.late, [0, 2, 5, 9, 11, 3]);
    assert_eq!((0..6).map(|v| t.setup_slack(v)).collect::<Vec<_>>(), [-2, 2, -2, -2, -2, 6]);
    assert_eq!(critical_path(&t, 4), [0, 2, 3, 4]);
    assert_eq!((t.hold_slack(4), t.hold_slack(5)), (1, 0)); // early = 3, 2 against hold 2
    adj[2][0].max = 2; // edit one arc and re-run
    assert_eq!(analyze(&adj, &start, &em, &en).unwrap().setup_slack(4), 0);
    // Project schedule (CPM), same function: events and activities with min = max = duration
    let p = g(&[(0, 1, 3, 3), (0, 2, 2, 2), (1, 3, 4, 4), (2, 3, 6, 6), (3, 4, 1, 1)], 5);
    let mut s = vec![-INF; 5]; s[0] = 0;
    let mut pm = vec![INF; 5]; pm[4] = 9; // deadline = project duration
    let c = analyze(&p, &s, &pm, &vec![-INF; 5]).unwrap();
    assert_eq!(critical_path(&c, 4), [0, 2, 3, 4]); // activities B, D, E
    assert_eq!(c.setup_slack(1), 1); // A has 1 unit of float
}

Compiled and run here: asserts pass. Hand check: node 4 arrives at 5+4+2 = 11, required 9, slack -2. Cutting arc 2-3 to 2 gives arrival 9, slack 0. In the schedule, B+D+E = 9 versus A+C+E = 8.

Complexity and constants

• Time O(V+E) per pass, space O(V+E). With the arrays above: 24 bytes per arc, 40 bytes per node plus a Vec header.
• Slack at a node equals the slack of the worst path through it, so one number per node covers all paths.
• Cost drivers: random access into the node arrays, delay calculation (outside this code) and the number of corners times modes.

Efficiency

• Cost: measured on this Mac (Apple M4 Pro), single thread: 200k nodes and 1M random arcs (arcs span at most 1000 node indices, delays 1-100), topological sort plus both passes, graph already built: 35-38 ms in release mode, about 36 ns per arc (derived). Bound: probably memory access (not profiled here).
• Levers:
  • incremental update — only the cones of an edit are recomputed (OpenSTA README: query-based incremental update of delays, arrival and required times) — repeated edits during optimization
  • parallel levelized passes — OpenTimer is built for parallel incremental timing (README) — large netlists
  • graph-based first, path-based only where slack is small — GBA merges worst slews and is pessimistic but quick, PBA is accurate but slow (patent US11222155) — signoff
  • GPU for path-based analysis — Guo et al., DAC 2021 — many paths to recompute
  • fewer corners/modes — analysis cost scales with their count (follows from one run per scenario) — early design
• Naive → standard → state of the art:
  • enumerate every path and sum delays · cost grows with the number of paths, which can be exponential
  • two passes over a topological order · O(V+E), about 36 ns/arc here
  • incremental and parallel engines (OpenSTA, OpenTimer) · work proportional to the changed cones

Implementation notes

• Use integers (ps) so ties and zero slack are exact; floats make "slack = 0" fuzzy.
• Store arcs in CSR arrays for locality; the Vec<Vec<_>> here is for clarity (gain not measured here).
• Keep late and early in one pass over the arcs; keep clock and data paths in the same graph so skew falls out of the arithmetic.
• Delay of an arc depends on slew and load, so a changed arc can change its fan-out delays: the incremental frontier grows through the cone until values stop changing.
• nextpnr's analyser runs this sequence: topo_sort, walk_forward, walk_backward, compute_slack, compute_criticality.

Pitfalls

• -INF + delay for unreached nodes becomes a plausible number; the guard above prevents it.
• Loops (latches, feedback) fail Kahn; real tools cut them at chosen arcs.
• A false path cannot be removed by deleting arcs: it applies to a from/to pair while other paths through the same arcs stay live.
• Under OCV setup and hold take opposite bounds for clock paths (OpenSTA doc above); one bound for both mis-states skew.
• Reporting WNS alone hides many small violations; TNS and endpoint counts show breadth.

Variants and alternatives

In production

• Chip flows: OpenSTA inside OpenROAD; Yosys sta for a flattened netlist; commercial signoff tools such as PrimeTime and Tempus exist (vendor pages not verified here).
• FPGA: nextpnr's timing-driven placement and routing.
• Schedules, builds, traces: CPM, Bazel's JSON profile, Grafana trace view.

Implementations

Sources

• Hitchcock, Smith and Cheng, Timing Analysis of Computer Hardware, IBM J. Res. Dev. 1982. doi
• Hitchcock, Timing Verification and the Timing Analysis Program, DAC 1982. doi
• Kelley and Walker, Critical-path planning and scheduling, Eastern Joint Computer Conference 1959. doi
• Huang and Wong, OpenTimer: A high-performance timing analysis tool, ICCAD 2015. doi · code
• Guo, Huang, Lin and Wong, GPU-accelerated Path-based Timing Analysis, DAC 2021. doi
• OpenSTA command reference · Liberty table model
• nextpnr timing.cc · Yosys sta.cc
• Bazel JSON trace profile · Grafana trace view · US11222155