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 language | English (US) |
---|---|
Article number | 5956869 |
Pages (from-to) | 1152-1162 |
Number of pages | 11 |
Journal | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
Volume | 30 |
Issue number | 8 |
DOIs | |
State | Published - 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