MSV-driven floorplanning

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

21 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

Funding

Manuscript received July 26, 2010; revised October 16, 2010 and January 7, 2011; accepted February 22, 2011. Date of current version July 20, 2011. This work was supported in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China, under Project 4184/07. The preliminary versions of this article appeared in the Proceedings of ICCAD’08 [14] and ISPD’09 [16]. This paper was recommended by Associate Editor P. Saxena.

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