TY - JOUR
T1 - MSV-driven floorplanning
AU - Ma, Qiang
AU - Qian, Zaichen
AU - Young, Evangeline F.Y.
AU - Zhou, Hai
N1 - Funding Information:
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.
PY - 2011/8
Y1 - 2011/8
N2 - 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.
AB - 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.
KW - Algorithms
KW - floorplanning
KW - linear programming
KW - min-cost flow
KW - multi-supply voltage
UR - http://www.scopus.com/inward/record.url?scp=79960695698&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960695698&partnerID=8YFLogxK
U2 - 10.1109/TCAD.2011.2131890
DO - 10.1109/TCAD.2011.2131890
M3 - Article
AN - SCOPUS:79960695698
VL - 30
SP - 1152
EP - 1162
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
SN - 0278-0070
IS - 8
M1 - 5956869
ER -