An exact gate assignment algorithm for tree circuits under rise and fall delays

Abstract

In most libraries, gate parameters such as the pin-to-pin intrin-sic delays, load-dependent coecients, and input pin capacitances have dierent values for rising and falling signals. The performance optimization algorithms, however, assume a single value for each parameter. It is known that under the load-independent delay model, the gate assignment (or resizing) problem is solvable in time polynomial in the circuit size when a single value is assumed for each parame-ter [5]. In the presence of dierent rise and fall parameter values, this problem was recently shown to be NP-complete even for chain and tree topology circuits under the simple load-independent delay model [8]. In this paper, we propose a dynamic programming algo-rithm for solving this problem exactly in pseudo-polynomial time for tree circuits. More specically, we show that the problem can be solved in time proportional to the size of the tree circuit, the number of choices available in the library for each gate, and the delay of the circuit. To the best of our knowledge, this is the rst pseudo-polynomial exact algorithm for the gate assignment prob-lem for trees in the presence of dierent rise and fall delays. We present a straightforward way of extending this algorithm to gen-eral directed acyclic graphs. We present experimental results on a set of benchmark problems using a standard commercial library and show that our algorithm generates provably optimum delays for 72 out of 76 circuits. We also compare our technique with two approaches traditionally used to solve this problem in the indus-try & academia and show that it is slightly better than these two. Interestingly, both traditional approaches also yield delays not far from the optimum. 1