Path-delay constrained floorplanning: a mathematical programming approach for initial placement

ABSTRACT

A procedure for path-delay constrained initial placement during chip floorplanning is presented which directly incorporates timing and geometrical constraints into the process. The problem is modeled and mathematically formulated as a constrained non-linear programming problem which is systematically divided and solved in three steps: timing minimization with module overlap, module separation and timing minimization without module overlap. To save computation time, two techniques for eliminating non-logical and noncritical paths are used to reduce the number of paths considered during the optimization. Experimental results show that the placement results satisfy all given timing and geometrical constraints, and have good total normalized wire delays.

REFERENCES

• AlAs88: Alon, A. and Ascher, U., "Model and Solution Strategy for Placement of Rectangular Blocks in the Euclidean Plane," IEEE Trans. on Computer-Aided Design, Vol.7 No.3 (1988), pp. 378-380.
• BeKi86: Berkcan, E~ and Kinnen, E., "Dim-REL: Performance Biased Placement Program for Custom IC Layout," Proc. Custom Integrated Circuit Conf. (lgs ), pp 2 3-2 8.
• BuYo85: Michael Burstein , Mary N. Youssef, Timing influenced layout design, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.124-130, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317845]
• DADJ84: A. E. Dunlop , V. D. Agrawal , D. N. Deutsch , M. F. Jukl , P. Kozak , M. Wiesel, Chip layout optimization using critical path weighting, Proceedings of the 21st conference on Design automation, p.133-136, June 25-27, 1984, Albuquerque, New Mexico, United States
• DCDJ87: Dai, W., Chen, H., Dutta, R., Jackson, M. and et.al., "Bear: A New Building-Block Layout System," Proc. International Conf. on Computer- Aided Design (1987), pp. 34-37.
• FiMc68: Fiacco, A. and McCormick, G., Nonlinear Programming." Sequential Unconstrained Minimization Techniques, New York: Wiley, 1968.
• HaNY87: Hauge, P., N~ir, R. and Yoffa, E., "Circuit Placement for Predictable Performance," Proc. International Conj. on Computer-Aided Design (i sV, pp. ss-oi.
• HsKu87: Hsh, Y-C. and Kubitz, W., "A Procedure for Chip Floorplanning," Proc. International Syrup. on Circuits and Systems (1987}, pp. 568-571.
• JaKM87: JackSon, M., Kuh, E.S. and Marek-Sadowska, M., "Timing Driven Routing for Building Block Layout, pq Proc. International Syrup. on Circuits and Systems (i987), pp. 518-519.
• OIST86: Yasushi Ogawa , Tatsuki Ishii , Yoichi Shiraishi , Hidekazu Terai , Tokinori Kozawa , Kyoji Yuyama , Kyoji Chiba, Efficient placement algorithms optimizing delay for high-speed ECL masterslice LSIs, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.404-410, July 1986, Las Vegas, Nevada, United States
• PeSU88: A. L. Peressini , Francis E. Sullivan , J. J. Uhl, Jr., The mathematics of nonlinear programming, Springer-Verlag New York, Inc., New York, NY, 1988
• RWKN88: Rose, M., Wiesel, M., Kirkpatrick, D. and Nettleton, N., "Dense, Performance Directed, Auto Place and Route." Proc. Custom Integrated Circuit Conf. (I988), pp 11.1.1 - 11.1.4.
• ShYB88: Shragowitz, E., Youssef, H. and Benning, L., "Predictive Tools in VLSI System Design : Timing Aspects," COMPEURO (1988), pp. 48-55.
• WeEs85: Neil H. E. Weste , Kamran Eshraghian, Principles of CMOS VLSI design: a systems perspective, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Experimentation