Algorithms for library-specific sizing of combinational logic

ABSTRACT

We examine the problem of choosing the proper sizes from a cell library for the logic elements of a Boolean network to meet timing constraints on the propagation delay along every path from the primary input to the primary output. If the Boolean network has a tree topology, we show that there exists a pseudo-polynomial time algorithm for finding the optimal solution to this problem. A backtracking-based algorithm for finding feasible solutions for networks that are not trees is also suggested and evaluated.

REFERENCES

• 1: K. Bartlett, W. Cohen, A. Geus, and G. Hachtel. Synthesis and Optimization of Multilevel Logic under Timing Constraints. IEEE Trans. on CAD, CAD-5(4):582-595, Oct. 1986.
• 2: P. K. Chan. Power and Timing Optimization with Long and Short-Path Constraints. Technical Report UCSC-CRL-89-06, Computer Engineering, UCSC, Santa Cruz, CA 95064, Mar. 1989.
• 3: M. A. Cirit, Transistor sizing in CMOS circuits, Proceedings of the 24th ACM/IEEE conference on Design automation, p.121-124, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37906]
• 4: J. Fishburn and A. Dunlop. TILOS: a posynomial programming approach to transistor sizing. ICCAD, pg. 326-328, Nov. 1985.
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 6: Lance A. Glasser , Lennox P.J. Hoyte, Delay and power optimization in VLSI circuits, Proceedings of the 21st conference on Design automation, p.529-535, June 25-27, 1984, Albuquerque, New Mexico, United States
• 7: K. S. Hedlund, Aesop: a tool for automated transistor sizing, Proceedings of the 24th ACM/IEEE conference on Design automation, p.114-120, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37905]
• 8: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 9: F. Lai, S. Kang, 2". Trick, and V. Rao. iJADE" a rule-based hierarchical cMOS. VLSI circuit optimizer. ICCD, pg. 38-41, Oct. 1987.
• 10: It. Lisanke. Logic Synthesis and Optimization Benchmarks, User Guide, Version 2.0. Microelectronics Center of North Carolina, 1988.
• 11: D. Marple and A. Gamal. Optimal selection of transistor sizes in digital VLSI circuits. Advanced Research in VLSI, 1987 Stanford Conference, pg. 151-172, 1987.
• 12: M. Matson and L. Glasser. ,Macromodeling and Optimization of Digital MOS VLSI Circuits. IEEE Trans. on CAD, CAD-5(4):659-678, Oct. 1986.
• 13: A. E. Ruehli , P. K. Wolff , G. Goertzel, Analytical power/timing optimization technique for digital system, Proceedings of the 14th conference on Design automation, p.142-146, January 1977
• 14: Texas Instruments SystemCell Series. 2-ttm CMOS S~andard Cell Data Book. Texas Instruments, 1986.
• 15: K. Singh, A. Wang, It. Brayton, and A. Sangiovanni-Vincentelli. Timing Optimization of Combinational Logic. ICCAD, pg. 282- 285, Nov. 1988.
• 16: S. Unger. Assigning Delay values to Meet Long and Short Path Constraints. IBM Technical Report RC 10166, Yorktown Heights, 1983.
• 17: S H Unger , Chung-Jen Tan, Clocking schemes for high-speed digital systems, IEEE Transactions on Computers, v.35 n.10, p.880-895, Oct. 1986 [doi>10.1109/TC.1986.1676679]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

General Terms:
Algorithms, Design