Transition-Aware Critical Path Selection Under Process Variation

Chips are tested by driving signals down a small set of "critical paths," the chains of logic gates most likely to be too slow. Picking that set on a design with millions of paths is a large graph optimization problem. Manufacturing variation makes it statistical, because every die is slightly different. The best-known statistical selection method, Testable Critical Path Selection Considering Process Variation, shrinks the candidate set on the ISCAS'89 circuit S38584 from over a million paths to about 18,000. Its authors state that its delay model treats a rising signal edge and a falling signal edge as identical.

Physically they are not identical. Rising edges are pulled up by PMOS transistors, which move holes. Falling edges are pulled down by NMOS transistors, which move electrons. The two device types also vary partly independently during fabrication. This is why the "slow-NMOS / fast-PMOS" corner exists. The same asymmetry shows up well outside logic testing. In FPGA delay chains, unequal edge speeds shrink a pulse until it vanishes (High-resolution time-to-digital converters (TDCs) with a bidirectional encoder). In a gate-driver delay generator, process corners swing a nominal 62 ns delay between 50 and 90 ns (An Active Dead-Time Control Circuit With Timing Elements for a 45-V Input 1-MHz Half-Bridge Converter).

This note proposes to measure how often symmetric statistical pruning throws away paths that are actually critical on real dies. It also proposes a transition-aware selection method that fixes the problem at close to the same graph size and runtime.

Core Claim

A signal moving through a chain of inverting gates alternates between rising and falling at each stage. A structural path is therefore really two timing paths: one launched by a rising input and one launched by a falling input. Each sums a different mix of PMOS-dominated and NMOS-dominated delays.

We write each gate's delay for output transition $s \in \{r, f\}$ in first-order form: $d_g^s = \mu_g^s + a_g^s \Delta P + b_g^s \Delta N + e_g^s$. Here $\Delta P$ and $\Delta N$ are global PMOS and NMOS parameter shifts with correlation $\rho$, and $e_g^s$ is local random mismatch. Rise delays have large $a$, and fall delays have large $b$.

The delay of path $p$ launched with polarity $s$ is then

$$D_p^s = \sum_{g \in p} d_g^{\sigma_g(s)},$$

where $\sigma_g(s)$ is the transition polarity at gate $g$, fixed by $s$ and the number of inversions before $g$.

A symmetric model replaces $d_g^r$ and $d_g^f$ with one averaged variable. That is harmless when $\rho \approx 1$ and rise and fall delays are balanced. When $\rho < 1$, the ranking of paths changes from die to die. On a slow-PMOS die, the rising-launched version of one path can overtake a path that a symmetric model ranks higher.

Our first hypothesis is that the rate at which symmetric pruning misses true critical paths grows as $\rho$ falls and as the rise/fall imbalance grows. Our second is that it is near zero at $\rho = 1$, which gives the study a built-in control.

The contribution is diagnostic as well as methodological. Fu et al. classify edges as completely critical (every path through the edge is critical) or partially critical (only some are), and build test sets greedily from that classification. We make this classification per polarity. An edge can be completely critical for falling transitions and irrelevant for rising ones. That matters because a delay test launches a specific transition, and the test generator must be told which one.

Where Each Direction Sits

Process variation is the regime and the source of the effect. Asymmetric edge propagation is the physical mechanism that the current pruning model drops. Large-scale network optimization enters as the computational problem itself. Statistical pruning computes a statistical maximum over a directed acyclic graph with millions of source-to-sink paths. Splitting each node by polarity doubles the graph, so the method must keep the scaling tricks that made Fu et al. fast: slack-threshold pruning, then decomposition into single-output logic cones.

We deliberately did not build the proposal on power-grid dispatch, even though the research file flags that gap. Grid optimizers such as Scalable Optimization Methods for Distribution Networks With High PV Integration and A Data-Driven Real-Time Optimal Power Flow Algorithm Using Local Feedback do treat inverters as ideal actuators. However, the simplest counter-argument is strong, and we found no evidence against it. Local compensation, such as the disturbance observer in Analysis and Compensation Control of Dead-Time Effect on Space Vector PWM, plus per-unit dead-time tuning as in A 9.2-ns to 1-s Digitally Controlled Multituned Deadtime Optimization for Efficient GaN HEMT Power Converters, would plausibly absorb most of the dead-time error before the grid ever sees it. The timing-graph question has no such easy escape.

Research Program

We will build a gate library in which rise and fall delays are characterized separately as linear functions of NMOS and PMOS parameter shifts plus local mismatch. The characterization will use transistor-level simulation on standard cells. The delays will be propagated through the ISCAS'89 benchmarks with polarity labels attached to every timing edge.

On this transition-split graph we will re-run the Fu et al. pipeline with two changes. First, statistical slack pruning will use the joint distribution of the two polarity copies, rather than one scalar per edge. This follows the first-order canonical form above, which is also the representation Fu et al. use under their Gaussian assumption. Second, completely/partially critical classification and greedy path selection will run per polarity. The selected set will be a list of pairs (path, launch polarity).

The core technical risk is that correlation between a path's two polarity copies makes the pruning bounds loose, so the candidate set balloons. We will handle this with a dominance test. A polarity copy is discarded only if its criticality probability stays below threshold under both the shared-parameter and local-mismatch components.

Two secondary analyses test whether the effect carries over to asymmetric timing chains outside logic testing. The first models a level-shifter and delay chain in the style of A Novel Floating High-Voltage Level Shifter with Pre-Storage Technique. The second uses the FPGA delay line of Xie et al. In both, rise/fall imbalance is large by construction.

Baselines

The naive reference point is the method of Testable Critical Path Selection Considering Process Variation run exactly as published, with a scalar symmetric delay per edge set to the rise/fall average. It is the strongest existing statistical path-selection method in the file. Its reported results on ISCAS'89 are the candidate reduction on S38584 (over 1 million paths to about 18,000), runtimes "under one second for most benchmarks," and "100% coverage in several test cases" under pseudo-exhaustive search. It will run on the same variation-annotated netlists with the same criticality threshold.

The second baseline is a conservative scalar model that uses the maximum of rise and fall delay per gate. This is what a practitioner would do to patch the symmetric assumption cheaply.

The third baseline is deterministic timing analysis at the two skewed corners, slow-NMOS/fast-PMOS and fast-NMOS/slow-PMOS. We take the top-k paths from each corner and form their union.

The oracle is 10,000-die Monte Carlo on the full transition-split graph. For each die we record which (path, polarity) pairs fall in its top-k.

The ablation keeps the transition-split graph but forces $\rho = 1$. This isolates whether partly independent NMOS/PMOS variation, and not mere rise/fall bookkeeping, drives the gain.

All methods get the same netlists, the same variation model, and a threshold tuned for each method so that they select equal numbers of paths. Beating the baselines means a lower per-die miss rate at equal path count, or equal miss rate with fewer paths. We report both, and runtime must stay within a small constant factor of the naive method.

Why not just…?

Why not just use the maximum of rise and fall delay in the existing scalar model? It errs on the safe side for each gate's delay, but it gets the path ranking wrong. It charges every path its worst polarity at every stage, which no real signal does, because polarity alternates. The result should be many paths kept or chosen for the wrong reason, and wrong polarity labels for test generation. This is the most serious competitor. If its miss rate at equal path count matches ours, the proposal reduces to "use max delays," and we will report that.

Why not just run corner analysis at the skewed corners and take the union? Corners capture the global NMOS/PMOS shift but not local mismatch. Modeling and analysis of loading effect on leakage of nanoscaled bulk-CMOS logic circuits shows that interactions ignored by independent-component models widen the leakage spread by over 40%. That is a different quantity, but it is a warning that tails matter. The corner-union baseline will measure how much of the miss rate corners alone recover.

Don't commercial timing tools already separate rise and fall? Deterministic timing does. What we change is the statistical pruning and completely/partially critical selection step, whose published form, as its authors note, does not. The novelty is limited to that step, and we claim nothing broader.

Decisive Checks

We will plot the naive method's per-die miss rate against the correlation $\rho$ and the rise/fall imbalance on S38584 and the other ISCAS'89 circuits. If the miss rate is negligible across realistic $\rho$, the premise fails and we stop. If it is not, the transition-aware selector must close most of the gap to the Monte Carlo oracle. It must also beat the max-delay and corner-union baselines at equal path count, and the $\rho = 1$ ablation must show that the gain disappears when NMOS and PMOS move together.