Graph Traversal & Slack · sta

Part 3 · Delay Graph and Path Analysis · All levels

4topics
4lessons

Every slack number comes from two propagations through the timing graph: arrival times forward from the startpoints and required times backward from the endpoints. This topic works both by hand, shows why the traversal scales to billions of paths, and ends with a complete timing engine in about forty lines of Python that you can run and change.

Lesson	After it you can...
Arrival and Required Times	Compute both times at every node and the slack there.
Forward and Backward Propagation	Explain why the cost is linear in design size.
Slack Worked Example	Find the critical path of a small circuit by hand.
A Tiny Timing Engine	Read and extend a working engine.

The first model of the graph is in The Timing Graph; here it becomes an algorithm.

Check yourself Why are two passes needed, forward and backward?

Arrival times depend on what comes before a node and required times on what comes after it. Slack needs both at the same node, so the arrivals are computed forward and the required times backward.

Up nextArrival and Required Times

Practice this lesson Report an error