File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A realistic early-stage power grid verification algorithm based on hierarchical constraints

TitleA realistic early-stage power grid verification algorithm based on hierarchical constraints
Authors
KeywordsHierarchical Constraints
Model Order Reduction
Submodular Polyhedron
Vectorless Power Grid Verification
Worst-Case Voltage Drop
Issue Date2012
PublisherIEEE. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=43
Citation
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2012, v. 31 n. 1, p. 109-120 How to Cite?
AbstractPower grid verification has become an indispensable step to guarantee a functional and robust chip design. Vectorless power grid verification methods, by solving linear programming (LP) problems under current constraints, enable worst-case voltage drop predictions at an early stage of design when the specific waveforms of current drains are unknown. In this paper, a novel power grid verification algorithm based on hierarchical constraints is proposed. By introducing novel power constraints, the proposed algorithm generates more realistic current patterns and provides less pessimistic voltage drop predictions. The model order reduction-based coefficient computation algorithm reduces the complexity of formulating the LP problems from being proportional to steps to being independent of steps. Utilizing the special hierarchical constraint structure, the submodular polyhedron greedy algorithm dramatically reduces the complexity of solving the LP problems from over O(k 3 m) to roughly O(k k m), where k m is the number of variables. Numerical results have shown that the proposed algorithm provides less pessimistic voltage drop prediction while at the same time achieves dramatic speedup. © 2011 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/155714
ISSN
2015 Impact Factor: 1.181
2015 SCImago Journal Rankings: 0.710
ISI Accession Number ID
Funding AgencyGrant Number
NSFCCF-1017864
Hong Kong Research Grants CouncilHKU 718509E
718711E
University Research Committee of the University of Hong Kong
Funding Information:

Manuscript received March 2, 2011; revised May 30, 2011; accepted August 29, 2011. Date of current version December 21, 2011. The work of C.-K. Cheng was supported by NSF CCF-1017864. This work was supported in part by the Hong Kong Research Grants Council, under Projects HKU 718509E and 718711E, and by the University Research Committee of the University of Hong Kong. This paper was recommended by Associate Editor S. Vrudhula.

References
Grants
Errata

 

DC FieldValueLanguage
dc.contributor.authorWang, Yen_US
dc.contributor.authorHu, Xen_US
dc.contributor.authorCheng, CKen_US
dc.contributor.authorPang, GKHen_US
dc.contributor.authorWong, Nen_US
dc.date.accessioned2012-08-08T08:34:58Z-
dc.date.available2012-08-08T08:34:58Z-
dc.date.issued2012en_US
dc.identifier.citationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2012, v. 31 n. 1, p. 109-120en_US
dc.identifier.issn0278-0070en_US
dc.identifier.urihttp://hdl.handle.net/10722/155714-
dc.description.abstractPower grid verification has become an indispensable step to guarantee a functional and robust chip design. Vectorless power grid verification methods, by solving linear programming (LP) problems under current constraints, enable worst-case voltage drop predictions at an early stage of design when the specific waveforms of current drains are unknown. In this paper, a novel power grid verification algorithm based on hierarchical constraints is proposed. By introducing novel power constraints, the proposed algorithm generates more realistic current patterns and provides less pessimistic voltage drop predictions. The model order reduction-based coefficient computation algorithm reduces the complexity of formulating the LP problems from being proportional to steps to being independent of steps. Utilizing the special hierarchical constraint structure, the submodular polyhedron greedy algorithm dramatically reduces the complexity of solving the LP problems from over O(k 3 m) to roughly O(k k m), where k m is the number of variables. Numerical results have shown that the proposed algorithm provides less pessimistic voltage drop prediction while at the same time achieves dramatic speedup. © 2011 IEEE.en_US
dc.languageengen_US
dc.publisherIEEE. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=43-
dc.relation.ispartofIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systemsen_US
dc.rightsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. Copyright © IEEE-
dc.rights©2012 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectHierarchical Constraintsen_US
dc.subjectModel Order Reductionen_US
dc.subjectSubmodular Polyhedronen_US
dc.subjectVectorless Power Grid Verificationen_US
dc.subjectWorst-Case Voltage Dropen_US
dc.titleA realistic early-stage power grid verification algorithm based on hierarchical constraintsen_US
dc.typeArticleen_US
dc.identifier.emailPang, GKH:gpang@eee.hku.hken_US
dc.identifier.emailWong, N:nwong@eee.hku.hken_US
dc.identifier.authorityPang, GKH=rp00162en_US
dc.identifier.authorityWong, N=rp00190en_US
dc.description.naturepublished_or_final_versionen_US
dc.identifier.doi10.1109/TCAD.2011.2167328en_US
dc.identifier.scopuseid_2-s2.0-84255199153en_US
dc.identifier.hkuros209035-
dc.identifier.hkuros210680-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-84255199153&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume31en_US
dc.identifier.issue1en_US
dc.identifier.spage109en_US
dc.identifier.epage120en_US
dc.identifier.isiWOS:000298327500011-
dc.publisher.placeUnited Statesen_US
dc.relation.erratumdoi:10.1109/TCAD.2012.2186340-
dc.relation.erratumeid:eid_2-s2.0-84863173775-
dc.relation.projectCanonical Projector Techniques with Applications in VLSI Modeling and Simulation-
dc.identifier.scopusauthoridWang, Y=35791415800en_US
dc.identifier.scopusauthoridHu, X=24279487400en_US
dc.identifier.scopusauthoridCheng, CK=7404797875en_US
dc.identifier.scopusauthoridPang, GKH=7103393283en_US
dc.identifier.scopusauthoridWong, N=35235551600en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats