Advanced Krylov subspace reduction for million-node transient power-grid analysis

1 / THE PROBLEM

The transient sign-off bottleneck

Dynamic IR-drop is decided by the full time-domain response of a mesh with millions of nodes, thousands of switching current sources and thousands of time steps.

Three properties of the problem make it resist brute force:

• The grid is enormous. Modern power grids reach millions of RC nodes across many metal layers. Every added node grows the linear system that must be solved at each of thousands of transient time points.
• Direct transient solves crawl. Back-Euler with a sparse factorization is the trusted reference, but it re-solves the full mesh step after step. On the largest IBM grid that is over three minutes for a single run — impossible for the thousands of scenarios sign-off demands.
• IR-drop must be in the loop. Floorplanning, decap budgeting and power delivery all need dynamic-IR feedback per iteration. Without a fast, accurate transient engine, IR-drop gets checked last, when it is most expensive to fix.

The goal is therefore not a faster linear solver, but a way to avoid solving the full system at every time step while preserving the waveforms a sign-off flow depends on.

2 / METHOD

Solve a tiny model, not the whole grid

The speed comes from never re-solving the full mesh.

GridStack builds a compact reduced-order model that captures the grid's dominant dynamics with an advanced Krylov subspace reduction method, marches that small model through time, and projects the answer back onto the nodes that were asked for.

Because the reduced model is built once and is independent of the stimulus, re-running a new current scenario on the same grid costs only the reduced-model march — which is what makes large sweeps over power profiles, decap placements or floorplans practical.

3 / SOLVER MODES

Two points on the speed–accuracy trade

The engine ships in two modes, both measured against the same direct back-Euler reference.

A direct back-Euler transient solver ships alongside as the ground-truth reference, and every GridStack result below is validated against it on the same netlist.

4 / EXPERIMENTAL SETUP

What was measured, and how

All measurements use the published IBM transient power-grid benchmarks.

Each circuit is solved with the direct back-Euler reference and with both reduced-order modes on identical input, and the error is measured on golden probe nodes against the direct result.

Error is reported as normalized waveform error — the deviation from the direct-solve waveform, normalized to the waveform scale — so values are comparable across circuits of different voltage ranges. Reduction order 10 and a rational-Krylov shift time of 1.0 s are used throughout.

5 / RESULTS

Direct, Krylov and GridStack, per circuit

Table 1 is the complete measurement set; the two figures present its accuracy and speedup columns graphically.

Table 1. CPU times in seconds. Reference: direct back-Euler transient. The standard Krylov method reaches machine precision (~10⁻¹⁴) at a moderate speedup; GridStack — the advanced Krylov method — is roughly 2× faster still while keeping the maximum normalized error under 6×10⁻⁶. Direct back-Euler takes 2.3–204 s per circuit; GridStack returns the same transient in 0.41–32.6 s, an average 7.9× speedup.

6 / DISCUSSION

Reading the measurements

Accuracy is sufficient for sign-off

The worst normalized error observed anywhere in the sweep is 5.62×10⁻⁶, on a single probe node of the smallest circuit. On the two larger grids the maximum error falls to 7.4×10⁻⁸ and 7.9×10⁻⁷. At these levels the reduced waveforms are visually indistinguishable from the direct solve, and the error is orders of magnitude below the margins a dynamic-IR sign-off criterion actually turns on.

The two modes trade precision for time predictably

The standard Krylov mode holds machine precision (10⁻¹³–10⁻¹⁴ on the two smaller grids) but only reaches 1.50–4.78× speedup. The advanced rational-Krylov mode gives up precision that was never needed — moving from ~10⁻¹⁴ to ~10⁻⁶ — and buys roughly another 2× in time. For a design loop that is the right side of the trade; for a final correlation run, the standard mode remains available on the same netlist.

Scaling behavior

Speedup is not monotonic in grid size: ibmpg2t shows the largest gain at 11.86×, while the million-node ibmpg3t shows 6.25×. The reduction cost itself grows with the grid, so the net gain depends on the balance between building the subspace and the number of time steps amortizing it. The practical consequence is that GridStack's advantage grows with the number of scenarios run against a grid, not only with grid size — a single reduced model serves an entire sweep.

These measurements cover the published IBM benchmark set at a fixed reduction order. Speedup and error on a proprietary grid depend on its topology, stimulus and the transient window; evaluate both on the design in question rather than transferring these figures to it.

7 / REPRODUCING THESE RESULTS

How the figures were produced

The two figures in §5 are generated directly from the measurement set in Table 1.

gen_plots.py in the project root writes accuracy_comparison.png and speedup_comparison.png into assets/figs/. The underlying runs come from the GridStack transient engine on the published IBM benchmark netlists, with the setup parameters listed in §4. Full-chip visualizations of the same grids are presented separately in GS-WP-02.