L1/13 — The combinatorial droop check

Edge: this file is the theorem the node carries — the combinatorial check (M-matrix monotonicity + lattice Green's function) that discharges 05's power-grid droop budget as an "N-apart"-style layout computation, the digital-crossing edge.

Making the droop check combinatorial: two collapses

The equipotential bound in 05 states what must hold; this section is how it becomes checkable without a full-chip network solve. Verifying "the supply at every cell stays within ΔV_grid under the worst workload" looks like two intractable searches — over all input workloads, and over all ~200k grid nodes. Both collapse, one to physics, one to the lattice, and what remains is combinatorial.

The current bound is structural, not statistical. The residual was written in 05 as "droop under worst-case simultaneous switching," and the honest worry is that a statistical activity estimate is unsound: logic is correlated, and an adversary (a power virus) can drive far more coincident switching than any average. The escape is to bound switching by circuit structure rather than activity. Per clock cycle each flop transitions at most once — and this bound is reachable, since a data pattern toggling every flop on one edge is a legal input, so for the sequential contribution it is not even pessimistic. Each combinational node transitions at most g times, g a structural glitch bound (distinct input arrival times ≤ logic depth). The per-cycle charge is then additive and workload-independent:

Q_cell ≤ Σ_nodes  (transitions · C_node · V) ,   transitions_flop = 1 ,   transitions_comb ≤ g

with the C_node the same L1 parasitics timing already uses. No activity model appears.

Collapse 1 — monotonicity removes the workload dimension. The DC grid is G·v = i, with G the mesh Laplacian plus the pad tie-downs to VDD — a symmetric M-matrix, whose inverse is entrywise non-negative. So the drop at any node, Δv_k = Σ_j R_kj i_j with every transfer resistance R_kj ≥ 0, is monotone in every current source, and the worst case over the admissible box 0 ≤ i_j ≤ i_j^max sits at the corner: every cell at its structural maximum, simultaneously. The exponential space of correlated workloads collapses to a single current vector — and this is the formal statement that the power virus, not a statistical peak, is the object to bound. There is nothing to search.

Collapse 2 — periodicity removes the spatial dimension. Evaluating R·i^max is still a 200k-node solve, until the tap/rail lattice is used: in the bulk G is translation-invariant, so R is a convolution and Δv = 𝒢 ⊛ i^max, with 𝒢 the discrete lattice Green's function of the mesh — for a 2-D resistor mesh a closed form (transfer resistance growing like (ρ_sheet/2π)·ln d). It is computed once on the fundamental domain (one pad's catchment cell, tens of nodes) and lifted by translation — the same quotient-by-the-lattice move that reduces tap coverage to a unit cell. Because the kernel decays, the drop at a point splits into a local term (the max current in that cell's neighbourhood — the dense-datapath worst case) and a slowly varying background (total current × a smaller effective resistance), two additive sums.

The resulting certificate is O(unit cell + defects), not O(200k), and it is sound:

  1. certify the grid is a periodic mesh and read its parameters — per-layer sheet resistance, via resistances, pad pitch — a finite set from the DEF + tech LEF + extraction;
  2. sum the structural Q_cell per unit cell (additive, from Liberty + the switching bound above);
  3. evaluate the unit-cell Green's-function bound ≤ ΔV_grid — a closed form or a tens-of-nodes solve, not a full-chip simulation;
  4. enumerate defects — SRAM holes, die boundary, met4/met5 strap-pitch changes — as a finite list of special cells with edge corrections.

What this changes for P_droop. If step 3 passes under the structural (worst-case) current, the droop residual is not a probability at all — it is discharged deterministically, and P_droop leaves ε. If it fails, the honest reading is that the grid was sized for a statistical peak and the design is only conditionally safe — exactly the power-virus exposure — which is a finding, not a modelling gap. Either way the probabilistic P_droop is replaced by a sound verdict.

Two caveats, stated plainly. Monotonicity is a DC fact; it discharges static IR-drop cleanly. The transient droop (L·dI/dt from package inductance, decap ringing) is not monotone — inductance overshoots — so it needs the unit-cell RLC response and an energy/damping bound, with the shared package L entering as a single global L·dI_total/dt term and the decap density as a lattice parameter. And the whole argument is conditional on the extracted parameters being trustworthy and the periodicity being verified rather than assumed. So: DC drop is fully combinatorial; di/dt is a small per-unit-cell dynamical bound plus one global inductive term.

Obligations

  1. The combinatorial droop certificate (the two-collapses section): the M-matrix monotonicity lemma (worst case = all-cells-max), the lattice Green's-function reduction (unit cell + defect list), the structural switching bound (flops ≤ 1/cycle, comb ≤ g), and the parameter extraction (sheet/via resistances, pad pitch). Together these replace the probabilistic P_droop with a sound verdict — a pass, or a power-virus finding.
  2. The transient (di/dt) piece: the unit-cell RLC bound plus the global L·dI_total/dt term — the one part that is not a pure DC sum.

Effort

Months, mostly tooling over DEF/extraction data; the two lemmas here — M-matrix monotonicity and the lattice Green's function — are the theory, and both lean on the lattice machinery (L0/06) other files already need. The node's equipotential bound (05) is what this certificate discharges combinatorially.