An efficient dual algorithm for vectorless power grid verification under linear current constraints

Vectorless power grid verification makes it possible to evaluate worst-case voltage drops without enumerating possible current waveforms. Under linear current constraints, the vectorless power grid verification problem can be formulated and solved as a linear programming (LP) problem. However, previous approaches suffer from long runtime due to the large problem size. In this paper, we design the DualVD algorithm that efficiently computes the worst-case voltage drops in an RC power grid. Our algorithm combines a novel dual approach to solve the LP problem, and a preconditioned conjugate gradient power grid analyzer. Our dual approach exploits the structure of the problem to simplify its dual problem into a convex problem, which is then solved by the cutting-plane method. Experimental results show that our algorithm is extremely efficient — it takes less than an hour to complete the verification of a power grid with more than 50K nodes and it takes less than 1 second to verify one node in a power grid with more than 500K nodes.