MSV-driven floorplanning

Qiang Ma*, Zaichen Qian, Evangeline F.Y. Young, Hai Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

Power consumption has become a crucial problem in modern circuit design. Multiple supply voltage (MSV) design is introduced to provide higher flexibility in controlling the power and performance tradeoff. One important requirement of MSV design is that timing constraints of the circuit must be satisfied after voltage assignment of the cells. In this article, we develop two algorithms to solve the voltage assignment problem under timing constraints, namely, min-cost flow (MCF) and value-oriented branch-and-bound (VOBB). In the MCF algorithm, the voltage assignment problem is formulated as a convex cost dual network flow problem, and can be solved optimally in polynomial time under certain conditions by calling a MCF solver. The VOBB algorithm, which is a VOBB-based searching method, solves the voltage assignment problem optimally in general cases by employing the MCF algorithm and a linear programming solver as subroutines. At last, we propose a MSV-driven floorplanning framework that optimizes power consumption and physical layout of a circuit simultaneously during the floorplanning stage, by embedding the MCF algorithm into a simulated annealing-based floorplanner and applying the VOBB algorithm as a postprocessing step. We compared our approach with the latest works on this problem, and the experimental results show that, using our approach, significant improvement on power saving can be achieved in much less running time, which confirms the effectiveness and efficiency of our method.

Original languageEnglish (US)
Article number5956869
Pages (from-to)1152-1162
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume30
Issue number8
DOIs
StatePublished - Aug 2011

Keywords

  • Algorithms
  • floorplanning
  • linear programming
  • min-cost flow
  • multi-supply voltage

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'MSV-driven floorplanning'. Together they form a unique fingerprint.

Cite this