Paper Info
Title
An efficient dual algorithm for vectorless power grid verification under linear current constraints
Abstract
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.
Year
DOI
Venue
2010
10.1145/1837274.1837484
DAC
Keywords
Field
DocType
convex problem,efficient dual algorithm,voltage drop,linear current constraint,linear programming,large problem size,power grid,lp problem,grid analyzer,dual problem,worst-case voltage drop,preconditioned conjugate gradient power,rc power grid,vectorless power grid verification,formal verification,linear program,noise,optimization,cutting plane method,symmetric matrices,voltage,algorithm design and analysis,algorithms,grid computing,electric potential
Conjugate gradient method,Diffusing update algorithm,Mathematical optimization,Algorithm design,Grid computing,Computer science,Voltage drop,Electronic engineering,Duality (optimization),Linear programming,Convex optimization
Conference
ISSN
ISBN
Citations 
0738-100X
978-1-4244-6677-1
16
PageRank 
References 
Authors
0.77
19
2
Name
Order
Citations
PageRank
Xuanxing Xiong1845.90
Jia Wang23322301.29