An Efficient Method for Large-Scale Gate SizingS. Joshi and S. Boyd
IEEE Transactions on Circuits and Systems I, 55(9):2760–2773, October 2008. We consider the problem of choosing the gate sizes or scale factors in a combinational logic circuit in order to minimize the total area, subject to simple RC timing constraints, and a minimum allowed gate size. This problem is well known to be a geometric program (GP), and can be solved using standard interior-point methods for small and medium size problems with up to several thousand gates. In this paper we describe a new method for solving this problem that handles far larger circuits, up to a million gates, and is far faster. Numerical experiments show that our method can compute an adequately accurate solution within around 150 iterations; each iteration, in turn, consists of a few passes over the circuit. In particular, the complexity of our method is linear in the number of gates. A simple implementation of our algorithm can size a 10000 gate circuit in 25 seconds, a 100000 gate circuit in 4 minutes, and a million gate circuit in 40 minutes, approximately. For the million gate circuit, the associated GP has 3 million variables and more than 6 million monomial terms in its constraints; as far as we know, these are the largest GPs ever solved. |