TY - GEN
T1 - Gate sizing by Lagrangian relaxation revisited
AU - Wang, Jia
AU - Das, Debasish
AU - Zhou, Hai
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2007
Y1 - 2007
N2 - In this paper, we formulate the Generalized Convex Sizing (GCS) problem that unities and generalizes the sizing problems. We revisit the approach to solve the sizing problem by Lagrangian relaxation, point out several misunderstandings in the previous works, and extend the approach to handle general convex delay functions in the GCS problems. We identify a class of proper GCS problems whose objective functions in the simplified dual problem are differentiable and show many practical sizing problems, including the simultaneous sizing and clock skew optimization problem, are proper. We design an algorithm based on the method of feasible directions to solve proper GCS problems. The algorithm will provide evidences for infeasible GCS problems according to a condition derived by us. Experimental results confirm the efficiency and the effectiveness of our algorithm when the Elmore delay model is used.
AB - In this paper, we formulate the Generalized Convex Sizing (GCS) problem that unities and generalizes the sizing problems. We revisit the approach to solve the sizing problem by Lagrangian relaxation, point out several misunderstandings in the previous works, and extend the approach to handle general convex delay functions in the GCS problems. We identify a class of proper GCS problems whose objective functions in the simplified dual problem are differentiable and show many practical sizing problems, including the simultaneous sizing and clock skew optimization problem, are proper. We design an algorithm based on the method of feasible directions to solve proper GCS problems. The algorithm will provide evidences for infeasible GCS problems according to a condition derived by us. Experimental results confirm the efficiency and the effectiveness of our algorithm when the Elmore delay model is used.
UR - http://www.scopus.com/inward/record.url?scp=50249166712&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=50249166712&partnerID=8YFLogxK
U2 - 10.1109/ICCAD.2007.4397252
DO - 10.1109/ICCAD.2007.4397252
M3 - Conference contribution
AN - SCOPUS:50249166712
SN - 1424413826
SN - 9781424413829
T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
SP - 111
EP - 118
BT - 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD
T2 - 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD
Y2 - 4 November 2007 through 8 November 2007
ER -