Abstract
This paper presents MINFLOTRANSIT, a new transistor sizing tool for fast sizing of combinational circuits with minimal cost. MINFLOTRANSIT is an iterative relaxation-based tool that has two alternating phases. For a circuit with |V| transistors and |E| wires, the first phase (D-phase) is based on minimum cost network flow, which in our application, has a worst case complexity of O(|V∥E|log(log(|V|))). The second phase (W-phase) has a worst case complexity of O(|V∥E|). In practice, during our simulations both the D-phase and W-phase show a near linear run-time dependence on the size of the circuit, comparable to TILOS. Simulation results show excellent run-time behavior for MINFLOTRANSIT on all the ISCAS85 benchmark circuits. For reasonable delay targets, MINFLOTRANSIT shows up to 16.5% area savings (in relatively large circuits) over a circuit sized using a TILOS-like algorithm. In our opinion, the primary contribution of this paper is to take advantage of the structure of the transistor sizing problem and devise an iterative relaxation based gradient descent approach (D-phase) that has excellent convergence properties.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 568-581 |
| Number of pages | 14 |
| Journal | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
| Volume | 21 |
| Issue number | 5 |
| DOIs | |
| State | Published - May 2002 |
Bibliographical note
Funding Information:Manuscript received May 4, 2000; revised May 31, 2001 and January 15, 2002. This work was supported in part by the ARO under Grant DA/DAAG55-98-1-0315 and in part by SRC under Grant 99-TJ-692. This paper was recommended by Associate Editor L. Stok.
Keywords
- Exact algorithms
- Gate sizing
- General/convex delay models
- Gradient descent
- Iterative relaxation
- Minimum cost network flow
- Simple discrete monotonic programming
- Speed of convergence
- Transistor sizing