A fast algorithm for power grid design

Jaskirat Singh, Sachin S. Sapatnekar

Research output: Contribution to conferencePaperpeer-review

5 Scopus citations


This paper presents an efficient heuristic algorithm to design a power distribution network of a chip by employing a successive partitioning and grid refinement scheme. In an iterative procedure, the chip area is recursively bipartitioned, and the wire pitches and the wire widths of the power grid in the partitions are repeatedly adjusted to meet the voltage drop and current density specifications. By using the macromodels of the power grid constructed in the previous levels of partitioning, the scheme ensures that a small global power grid system is simulated in each iteration. A post-processing step at the end of the optimization is employed to maximize the alignment of wires in adjacent partitions. The effectiveness of the scheme is demonstrated by designing various power grids with real circuit parameters and realistic input current values. The proposed algorithm is able to design power grids comprising thousands of wires and more than a million electrical nodes in about 7-16 minutes. The proposed design scheme as compared to u multigrid-based power grid design scheme saves about 7%-12% of wire area.

Original languageEnglish (US)
Number of pages8
StatePublished - 2005
Event2005 International Symposium on Physical Design, ISPD'05 - San Francisco, CA, United States
Duration: Apr 3 2005Apr 6 2005


Other2005 International Symposium on Physical Design, ISPD'05
Country/TerritoryUnited States
CitySan Francisco, CA


  • Bipartitioning
  • Locality
  • Macromodel
  • Wire pitch


Dive into the research topics of 'A fast algorithm for power grid design'. Together they form a unique fingerprint.

Cite this