On the problem of gate assignment under different rise and fall delays
See where this sits in the topic map →Summary AI-generated
- TL;DR
- While circuit cell libraries typically specify different gate parameters for rising and falling signals, most performance optimization algorithms assume a single value for both.
- Problem
- Accounting for distinct rise and fall delays makes the gate assignment and resizing problem NP-complete, even for simple chain and tree circuits under a load-independent delay model.
- Method
- For tree circuits, the researchers show the problem is not NP-complete in the strong sense and propose a dynamic programming algorithm that finds exact solutions in pseudopolynomial time, which can also be extended to general directed acyclic networks.
- Results
- Experiments using a standard commercial library and benchmark problems show that the proposed algorithm achieves provably optimum delays for 69 out of 73 circuits, outperforming two traditional industry and academia approaches.
- Contributions
- Proposing a pseudopolynomial-time dynamic programming algorithm for gate assignment under asymmetric rise and fall delays in tree and directed acyclic circuits.
- Limitations
- Not specified in the abstract.
- Takeaways
- Despite the theoretical worst-case complexity, traditional industrial and academic approaches generally produce delays that remain close to the optimum.
- Applications
- Not specified in the abstract.
- Topics
- Circuit optimization, gate assignment, delay models, electronic design automation
- For industry
- Semiconductor design and electronic design automation (EDA)
- Why it matters
- Not specified in the abstract.
Abstract
In most libraries, gate parameters such as the pin-to-pin intrinsic delays, load-dependent coefficients, and input pin capacitances have different values for rising and falling signals. Most 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 parameter (Kukimoto et al., 1998). We show that, in the presence of different rise and fall parameter values, this problem is NP-complete even for chain and tree topology circuits under the simple load-independent delay model (Murgai, 1999). However, we also show that, for tree circuits, the problem is not NP-complete in the strong sense, and we propose a dynamic programming algorithm that solves it exactly in pseudopolynomial time. More specifically, we show that the problem can be solved in time proportional to the size of the circuit, the number of choices available in the library for each gate and the delay of the circuit. We also present a straightforward way of extending this algorithm to general directed acyclic networks. 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 69 out of 73 circuits. We also compare our technique with two approaches traditionally used to solve this problem in the industry and academia and show that it performs better than these two. Interestingly, both traditional approaches also yield delays that are, in general, not far from the optimum.