Timing graph & longest-path analysis

Underneath static timing analysis lies a beautiful graph algorithm. The whole chip is modelled as a directed acyclic graph — nodes are pins, edges carry delay — and the question 'will the circuit run at the target clock?' becomes 'what is the longest delay path from any launch flip-flop to any capture flip-flop?' Instead of tracing the billions of possible paths one by one (which would take longer than the age of the universe), the tool computes a single number at every node and propagates it forward in one sweep.

This is block-based STA, essentially the PERT/critical-path method from project scheduling: visit nodes in topological order, and at each node set its arrival time to the maximum over all incoming edges of (predecessor arrival + edge delay). One linear-time forward pass yields the worst arrival at every endpoint; a backward pass propagates required times, and arrival-minus-required gives the slack at every point — instantly exposing the critical path. The genius is that taking the MAX at each node folds exponentially many paths into a linear computation, which is why STA can sign off a billion-gate chip in minutes.