MINFLOTRANSIT: min-cost flow based transistor sizing tool

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 over a circuit sized using a TILOS-like algorithm.

REFERENCES

• 1: J. P. Fishburn and A. E. Dunlop, "TILOS: A Posynomial Programming Approach to Transistor Sizing," in Proceedings of the 1985 International Conference on Computer-Aided Design, pp. 326-328, November 1985.
• 2: S. Sapatnekar, V. Rao, E Vaidya, and S. Kang, "An Exact Solution to the Transistor Sizing Problem for CMOS Circuits Using Convex Optimization.," IEEE Transactions on Computer- Aided Design, vol. 12, pp. 1621-1634, November 1993.
• 3: J.-M. Shyu, A. L. Sangiovanni-Vincentelli, J. Fishburn, and A. Dunlop, "Optimization-based Transistor Sizing," IEEE Journal on Solid State Circuits, vol. 23, no. 2, pp. 400-409, 1988.
• 4: D. Marple, "Performance Optimization of Digital VLSI Circuits," Technical Report CSL-TR-86-308, Stanford University, October 1986.
• 5: D. Marple, Transistor size optimization in the tailor layout system, Proceedings of the 26th ACM/IEEE conference on Design automation, p.43-48, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74391]
• 6: H. Y. Chen , S. M. Kang, iCOACH: a circuit optimization aid for CMOS high-performance circuits, Integration, the VLSI Journal, v.10 n.2, p.185-212, Jan. 1991 [doi>10.1016/S0167-9260(06)80015-5]
• 7: Z. Dai and K. Asada, "MOSIZ: A Two-Step Transistor Sizing Algorithm based on Optimal Timing Assignment Method for Multi-Stage Complex Gates," in Proceedings of the 1989 Custom Integrated Circuits Conference, pp. 17.3.1-17.3.4, May 1989.
• 8: Chung-Ping Chen , Chris C. N. Chu , D. F. Wong, Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.617-624, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289097]
• 9: Andrew W. Goldberg , Michael D. Grigoriadis , Robert E. Tarjan, Use of dynamic trees in a network simplex algorithm for the maximum flow problem, Mathematical Programming: Series A and B, v.50 n.3, p.277-290, June 1991 [doi>10.1007/BF01594940]
• 10: Marios C. Papaefthymiou, Asymptotically efficient retiming under setup and hold constraints, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.396-401, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289060]
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: G. Strang, Linear Algebra and its Applications. Harcourt Brace Jovanovich, Publishers, San Diego, CA, 1988.
• 13: Vijay Sundararajan , Keshab K. Parhi, Low Power Gate Resizing of Combinational Circuits by Buffer-Redistribution, Proceedings of the 20th Anniversary Conference on Advanced Research in VLSI, p.170, March 21-24, 1999
• 14: V. Chvatal, Linear Programming. W. H. Freeman and Company, New York, NY, 1983.
• 15: A. E. Dunlop, J. E Fishburn, D. D. Hill, and D. D. Shugard, "Experiments Using Automatic Physical Design Techniques for Optimizing Circuit Performance," in Proceedings of the 32nd Midwest Symposium on Circuits and Systems, (Urbana, IL), pp. 216-220, August 1989.
• 16: J. Cong, "Challenges and Opportunities for Design Innovations in Nanometer Technologies," Technical Report, Semiconductor Research Corporation, 1997.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
  B.8 Performance and Reliability

General Terms:
Algorithms, Design, Measurement, Performance, Theory