On this page 13 sections
- What is graph-based analysis (GBA)?
- What is path-based analysis (PBA)?
- GBA vs PBA at a glance
- Worked example A: slew merging at a reconvergent gate (illustrative)
- Path mode vs exhaustive mode
- Worked example B: why path mode can be optimistic (illustrative)
- Where GBA and PBA fit in the flow
- Common problems and fixes
- Debug flowchart: is this GBA violation real?
- Interview Q&As
- FAQ
- Summary
- References
Graph-based analysis (GBA) and path-based analysis (PBA) are the two ways a static timing analysis (STA) tool can work out the slack of a timing path. GBA is fast and covers the whole design in one pass, but it is pessimistic. PBA re-times individual paths with their own slews and context, so it is more accurate, but it costs much more runtime. Knowing when to trust each one, and how to use PBA without fooling yourself, is a core sign-off skill and a common interview topic.
This guide covers where GBA pessimism comes from, what PBA recalculates, path mode vs exhaustive mode, the sign-off flow, worked examples, a debug flowchart and interview Q&As. The worked examples are illustrative: the delay models and numbers show the method and are not taken from any foundry, library or project. Tool commands are simplified sketches; check your tool's documentation for exact options. Related reading on iVLSI: Static Timing Analysis (STA) in VLSI, OCV, AOCV and POCV in STA, Setup and Hold Violations and MMMC in STA.
What is graph-based analysis (GBA)?#
An STA tool models the netlist as a timing graph. Pins are nodes. Cell arcs (input pin to output pin) and net arcs (driver pin to load pin) are edges. The tool propagates arrival times and transition times (slews) forward from the launch points, and required times backward from the capture points.
In graph-based analysis, each node stores a small, fixed amount of data per clock and per rise/fall edge: essentially the worst arrival time and the worst slew among all the signals that reach it. For setup (late) analysis that means the latest arrival and the slowest slew. For hold (early) analysis it means the earliest arrival and the fastest slew. Every downstream arc then computes its delay from that stored worst slew.
That is why GBA is fast: each arc is evaluated once per edge and corner, so runtime grows with the size of the graph, not with the number of paths (which can grow exponentially with reconvergence). It is also why GBA is safe: the stored values bound every path through that node, so GBA does not report a path as better than it is.
The catch is that the worst arrival and the worst slew at a node often come from different inputs. GBA combines them anyway. The path with the latest arrival is then timed as if it also had the slowest slew, even though no real signal has both. Kahng, Mallappa and Saul describe exactly this effect in their ICCD 2018 paper on predicting PBA slack: the worst input transition at a cell is propagated even when it occurs on a pin that is not on the path being analysed, the pessimistic slew feeds the next cell's delay calculation, the pessimism accumulates along the path, and the endpoint slew also affects the capture flop's setup requirement.
What is path-based analysis (PBA)?#
Path-based analysis takes one specific path, from launch to capture, and recalculates it in isolation. Along that path it propagates only the slews that the path itself produces, ignoring side inputs, and redoes the delay calculation stage by stage. The result is the slack that path would really see, under the same models and constraints.
PBA can remove more than slew merging. Depending on the tool and settings, path re-timing can also refine:
- AOCV derates. Depth and distance based derates can use the exact depth and distance of the path instead of a conservative value computed for the graph. See OCV, AOCV and POCV in STA.
- POCV / statistical delay. The variation of the path can be combined from its own stages instead of from merged worst values.
- Clock reconvergence pessimism removal (CRPR / CPPR). The common clock segment can be computed for the exact launch and capture pair.
- Signal integrity (SI) delta delay. Crosstalk effects depend on slews and timing windows, so they can be recomputed with the path's own slews. See Crosstalk in VLSI.
PBA does not decide whether a path is functional: false paths and case analysis belong in the constraints. See Multicycle Path and False Path in STA.
The cost is runtime. The number of distinct paths to an endpoint can be enormous, and each re-timed path needs its own delay calculation. Kahng et al. report that PBA incurs runtime overheads of 4X or more relative to GBA, and that a commercial sign-off STA tool showed PBA slowdowns as high as 15X on the leon3mp benchmark (108K flip-flops, 450K signal nets) and 150X on megaboom (350K flip-flops, 960K signal nets) in 28nm FDSOI, measured with exhaustive PBA. They also note that the lighter "path" mode can have as little as 2X overhead with nworst 1. Your numbers will differ by design, tool version, corner count and settings, but the direction is always the same: PBA is much slower than GBA.
GBA vs PBA at a glance#
| GBA (graph-based) | PBA (path-based) | |
|---|---|---|
| What it times | Every node in one pass | Selected paths, one by one |
| Slew used for each arc | Worst slew stored at the input node | The slew this path actually produces |
| Pessimism | Higher (merged worst values) | Lower (path-specific values) |
| Safety | Bounds every path; never optimistic | Accurate per path; coverage depends on the mode |
| Runtime | Fastest; scales with graph size | Much slower; scales with paths re-timed |
| Typical use | Implementation, optimization, full-chip reports | Sign-off on near-critical paths, ECO decisions |
For the same path, under the same settings, PBA slack should be equal to or better than GBA slack, because PBA only removes merged-in pessimism. If PBA reports a worse slack than GBA for the same path, treat it as a sign that the two runs do not use the same settings (for example a different SI, AOCV or clock-path setting) and investigate before trusting either number.
Worked example A: slew merging at a reconvergent gate (illustrative)#
Use the circuit in Figure 1 with simple made-up linear models (real tools use library tables and waveform-based delay calculation):
- NAND2 U3 arcs: delay = 40 + 0.3 × input slew; output slew = 25 + 0.2 × input slew (ps).
- Buffers U4 and U5: delay = 30 + 0.35 × input slew; output slew = 20 + 0.3 × input slew (ps).
- Capture flop setup time = 15 + 0.1 × data slew (ps). Capture clock edge at 555 ps, ideal clock, no uncertainty, wire delay ignored.
Two paths reach U3:
- P1 reaches U3/A at 400 ps with a sharp 30 ps slew.
- P2 reaches U3/B at 300 ps with a slow 120 ps slew (it comes from a heavily loaded net).
At U3/Y:
- Arc A→Y: delay 40 + 0.3 × 30 = 49 ps, so P1 arrives at 449 ps with output slew 25 + 6 = 31 ps.
- Arc B→Y: delay 40 + 0.3 × 120 = 76 ps, so P2 arrives at 376 ps with output slew 25 + 24 = 49 ps.
GBA stores the latest arrival (449 ps, from P1) and the slowest slew (49 ps, from P2) at U3/Y. PBA for P1 keeps P1's own 31 ps slew.
| Stage | GBA input slew | GBA delay | PBA input slew | PBA delay |
|---|---|---|---|---|
| U4 | 49.0 ps | 47.2 ps | 31.0 ps | 40.9 ps |
| U5 | 34.7 ps | 42.1 ps | 29.3 ps | 40.3 ps |
| Data slew at D | 30.4 ps | setup 18.0 ps | 28.8 ps | setup 17.9 ps |
- GBA arrival at D: 449 + 47.2 + 42.1 = 538.3 ps. Required: 555 − 18.0 = 537.0 ps. Slack ≈ −1.3 ps (violation).
- PBA arrival at D: 449 + 40.9 + 40.3 = 530.1 ps. Required: 555 − 17.9 = 537.1 ps. Slack ≈ +7.0 ps (passes).
About 8.4 ps of the GBA violation was pessimism: P1 was charged for P2's slow slew. Notice that the difference shrinks at each stage after the merge point, because each stage partly "forgets" its input slew. Real paths have many merge points, so the real gap can be larger or smaller.
Path mode vs exhaustive mode#
Sign-off tools generally offer two ways to run PBA. Synopsys PrimeTime calls them -pba_mode path and -pba_mode exhaustive on report_timing (the Kahng et al. paper refers to both modes); Cadence's timer exposes path re-timing through report_timing -retime path_slew_propagation, as shown in a Cadence blog on SPICE correlation in Encounter Timing System, Tempus's predecessor. The idea behind the two styles is the same in every tool:
- Path mode takes the paths that GBA already selected (for example the worst GBA path to each endpoint) and re-times only those. It is relatively quick, but it is not guaranteed to find the worst PBA path to an endpoint. After recalculation the ranking of paths can change. A path that was second or tenth in GBA can become the worst in PBA, and path mode never looks at it. So path mode can be optimistic.
- Exhaustive mode keeps searching paths to each endpoint until it can guarantee that the reported paths are the worst after recalculation. That is the result to base sign-off decisions and waivers on. It is also the slowest.
Synopsys has described further speed-ups to exhaustive PBA in PrimeTime, including a graph-based refinement and a machine-learning PBA mode that converges to exhaustive results near sign-off (SemiEngineering, 2020). Treat any accelerated or approximate mode the way your sign-off methodology says to; if in doubt, confirm final waivers with a full exhaustive run.
Worked example B: why path mode can be optimistic (illustrative)#
Endpoint u_core/r_q_reg[7]/D has three paths reaching it. GBA reports:
| Path | GBA slack | PBA slack |
|---|---|---|
| P1 (worst in GBA) | −8 ps | +4 ps |
| P2 | −5 ps | −2 ps |
| P3 | −3 ps | +1 ps |
- GBA says the endpoint fails at −8 ps.
- Path mode with one path per endpoint re-times only P1 and reports +4 ps. Someone reading this report would waive the endpoint.
- Exhaustive mode keeps going, finds that P2 is still at −2 ps after re-timing, and reports −2 ps. The endpoint really fails.
P1 had a lot of slew-merge pessimism and P2 had little. That is normal, not a tool bug, and it is why sign-off numbers come from exhaustive PBA while path mode is used for triage.
Where GBA and PBA fit in the flow#
A practical sign-off flow uses both, each where it is strong:
- Implementation and optimization run in GBA. Placement, CTS and routing optimizers work on graph timing because it is fast and covers everything. Over-fixing here costs area and power but not correctness.
- Full-chip sign-off STA runs GBA first in every MMMC view, to get complete coverage and the list of violating and near-critical endpoints.
- Path-mode PBA on that list for a quick view of how much is pessimism. If GBA and PBA agree, the violations are real and need fixing.
- Exhaustive PBA on what is still close (for example, endpoints with slack below a small positive margin after path mode). Use these numbers for sign-off decisions.
- ECO against PBA-aware timing. Fixing only the real violations avoids upsizing and buffering that the design does not need. The Synopsys 2016 PrimeTime release announcement framed better GBA-to-PBA correlation (through POCV) as a way to spend less time on runtime-costly PBA to eliminate false violations; the same thinking drives PBA-based ECO.
- Re-run GBA after each ECO so the full design is covered again, then re-confirm the remaining close paths with PBA.
A few habits make this flow trustworthy:
- Same settings in GBA and PBA. SI, OCV mode, CRPR and clock-path handling must match, or the comparison means nothing.
- Know what is re-timed. Some tools re-time only the data portion of a path by default and keep the clock path from the graph. Check your tool's setting and your team's sign-off rule.
- Bound the exhaustive search sensibly. Limit it to failing or near-failing endpoints by slack, not to an arbitrary top-N count, so nothing that matters is left out.
- Report the mode. A slack without "GBA", "PBA path" or "PBA exhaustive" next to it is not a sign-off number. GBA over-fixing applies to hold as well as setup (see Q7).
Common problems and fixes#
| Symptom | Likely cause | Fix |
|---|---|---|
| Large GBA violations everywhere, PBA clean | Slow slews on high-fanout or long nets merging into many paths | Fix the slews at the source (sizing, buffering, net splitting); this also helps GBA and implementation correlation. See DRVs in VLSI |
| Endpoint passes in path mode, fails in exhaustive | Worst PBA path was not the worst GBA path | Use exhaustive results for sign-off; fix the path exhaustive reports |
| PBA slack worse than GBA for the same path | Settings differ between the runs | Align SI, OCV/AOCV/POCV, CRPR and clock-path settings, then compare again |
| Exhaustive run never finishes | Search scope too wide (whole design, huge nworst) | Restrict to violating endpoints by slack; run path mode first; split by path group or view |
| PBA does not remove a "false" failure | The path is structurally real; it is a constraint issue | Add the correct case analysis, false path or multicycle constraint; PBA cannot remove functional false paths |
| PBA gain disappears after an ECO | ECO changed slews or loads on side paths | Re-run GBA, then re-confirm with PBA |
Debug flowchart: is this GBA violation real?#
In short: fix constraints first, make sure GBA and PBA use the same settings, use path mode for triage, confirm with exhaustive (which may report a different path), and record PBA-clean endpoints with the mode stated, re-checking after every ECO.
A tool sketch, with options simplified (check your own tool's documentation):
# PrimeTime-style sketch report_timing -delay_type max -max_paths 1000 -slack_lesser_than 0 ;# GBA report_timing -delay_type max -pba_mode path -slack_lesser_than 0 ;# triage report_timing -delay_type max -pba_mode exhaustive -slack_lesser_than 0 ;# sign-off # Cadence-style sketch report_timing -late -max_paths 1000 -retime path_slew_propagationInterview Q&As#
Q1. What is the difference between GBA and PBA? GBA stores the worst arrival and worst slew at every node and times the whole graph in one pass. It is fast and safe but pessimistic. PBA re-times a specific path with the slews that path really produces, so it is more accurate and much slower.
Q2. Where does GBA pessimism come from? Mainly from slew merging. At a multi-input cell, the latest arrival and the slowest slew can come from different inputs, and GBA uses both together. The slow slew then increases every downstream delay and the capture setup time. AOCV depth, CRPR and SI can add more graph-level pessimism.
Q3. Is GBA ever optimistic? Not by design. It bounds every path through each node. That is why it is used for full coverage.
Q4. Why not run PBA on everything? Path counts grow exponentially with reconvergence, and each path needs its own delay calculation. Published work reports PBA runtimes from several times to over a hundred times GBA on large designs.
Q5. What is the difference between path mode and exhaustive mode? Path mode re-times only the paths GBA selected. Exhaustive searches until the reported paths are guaranteed to be the worst after re-timing. Path mode can be optimistic because the path order can change after re-timing.
Q6. Can PBA fix a false path?
No. PBA removes analysis pessimism, not functional impossibility. False paths need constraints such as set_false_path or set_case_analysis.
Q7. Does PBA help hold? Yes. For hold, GBA uses the fastest slews, which makes delays shorter and hold look worse. PBA uses the real slews and can recover hold margin, avoiding unnecessary hold buffers.
Q8. Your PBA slack is worse than GBA for the same path. What do you check? That the runs are comparable: the same SI, OCV mode, CRPR, clock-path handling, parasitics and view. With identical settings, PBA should not be worse than GBA for the same path.
Q9. How would you reduce the GBA-PBA gap at the design level? Fix slow slews at their source (high-fanout nets, long wires, weak drivers), because one slow side input can penalise many paths through a merge point. Better variation modelling, such as POCV, also narrows the gap.
FAQ#
Is PBA required for sign-off? That is a methodology decision for each team and each foundry flow. Many teams sign off on PBA for near-critical paths and GBA for the rest, but the rule should be written in your sign-off checklist.
Does every STA tool support PBA? Sign-off timers from the major EDA vendors do, with their own commands and defaults. Results can differ slightly between tools, a point Kahng et al. also make, so compare like with like.
Summary#
- GBA stores worst arrival and worst slew per node: fast, full coverage, never optimistic, but pessimistic where paths reconverge.
- PBA re-times one path with its own slews (and can refine AOCV, POCV, CRPR and SI): accurate but much slower.
- Path-mode PBA is for triage; exhaustive PBA is for sign-off decisions and waivers.
- Use the same settings in GBA and PBA, state the mode in every report, and re-check after each ECO.
- PBA removes pessimism, not real or functional problems. Fix slow slews at the source and fix false paths in the constraints.
References#
- A. B. Kahng, U. Mallappa and L. Saul, "Using Machine Learning to Predict Path-Based Slack from Graph-Based Timing Analysis", IEEE ICCD 2018, DOI 10.1109/ICCD.2018.00096: https://vlsicad.ucsd.edu/Publications/Conferences/361/c361.pdf
- Synopsys news release, "Synopsys' PrimeTime Speeds Timing and Power Closure for Complex SoC and IoT Designs" (March 23, 2016): https://news.synopsys.com/2016-03-23-Synopsys-PrimeTime-Speeds-Timing-and-Power-Closure-for-Complex-SoC-and-IoT-Designs
- R. Deokar (Synopsys), "The Challenge Of Balancing Performance And Accuracy For Advanced Node Timing Signoff", SemiEngineering, November 10, 2020: https://semiengineering.com/the-challenge-of-balancing-performance-and-accuracy-for-advanced-node-timing-signoff/
- Cadence Community blog, "SPICE Correlation Made Easy by Encounter Timing System (ETS)" (December 10, 2012; shows
report_timing -retime path_slew_propagation): https://community.cadence.com/cadence_blogs_8/b/di/posts/spice-correlation-made-easy-by-ets - Related iVLSI posts: Parasitic Extraction and SPEF in VLSI, Useful Skew in VLSI, ECO in VLSI Physical Design, Time Budgeting in VLSI, Timing Library (.lib)




