Algorithms for simultaneous satisfaction of multiple constraints and objective optimization in a placement flow with application to congestion control

ABSTRACT

This paper addresses the problem of tackling multiple constraints simultaneously during a partitioning driven placement (PDP) process, where a larger solution space is available for constraint-satisfying optimization compared to post placement methods. A general methodology of multi-constraint satisfaction that balances violation correction and primary optimization is presented. A number of techniques are introduced to ensure its convergence and enhance its solution search capability with intermediate relaxation. Application of our approach to congestion control modeled as pin density and external net distribution balance constraints shows it effectively reduces overall congestion by 14.3% and improves chip area by 8.9%, with reasonable running time and only 1.6% increase in wire length. As far as we know, this is the first time an approach to congestion reduction during placement optimization produced good congestion improvement with very small wire length increase.

REFERENCES

• 1: A. E. Dunlop and B. W. Kernighan. A procedure for placement of standard-cell VLSI circuits. IEEE Trans. CAD, pp. 92--98, Jan. 1985
• 2: S. Dutt and W. Deng, "Probability-based Approaches to VLSI Circuit Partitioning," IEEE Trans. CAD, pp. 534--549, Mar. 2000
• 3: Shantanu Dutt , Halim Theny, Partitioning around roadblocks: tackling constraints with intermediate relaxations, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.350-355, November 09-13, 1997, San Jose, California, United States
• 4: Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277119]
• 5: H. Esbensen and E. Kuh, "Exploring the design space for building block placements considering area, aspect ratio, path delay and routing congestion", Proc. Physical Design Workshop, 1996, pp. 126--133
• 6: Dennis J.-H. Huang , Andrew B. Kahng, Partitioning-based standard-cell global placement with an exact objective, Proceedings of the 1997 international symposium on Physical design, p.18-25, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267674]
• 7: Roman Kužnar , Franc Brglez , Krzysztof Kozminski, Cost minimization of partitions into multiple devices, Proceedings of the 30th international conference on Design automation, p.315-320, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164910]
• 8: S. Mayrhofer and U. Lauther, "Congestion-driven placement using a new multi partitioning heuristic", Proc. ICCAD, pp. 332--335, 1990
• 9: Phiroze N. Parakh , Richard B. Brown , Karem A. Sakallah, Congestion driven quadratic placement, Proceedings of the 35th annual conference on Design automation, p.275-278, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277121]
• 10: W-J. Sun and C. Sechen, "Efficient and Effective Placement for Very Large Circuits", IEEE Trans. CAD, pp. 349--359, Mar. 1995
• 11: Maogang Wang , Xiaojian Yang , Majid Sarrafzadeh, Dragon2000: standard-cell placement tool for large industry circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 12: M. Wang, X. Yang and M. Sarrafzadeh, "Congestion Minimization During Placement", IEEE Trans. CAD, pp. 1140--1148, Oct. 2000
• 13: Wayne Wolf, Modern VLSI design (2nd ed.): systems on silicon, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 14: Xiaojian Yang , Ryan Kastner , Majid Sarrafzadeh, Congestion reduction during placement based on integer programming, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 15: Ke Zhong , Shantanu Dutt, Effective partition-driven placement with simultaneous level processing and global net views, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 16: Hai Zhou , D. F. Wong, Global routing with crosstalk constraints, Proceedings of the 35th annual conference on Design automation, p.374-377, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277147]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Experimentation

Keywords:
congestion reduction, connector generation, intermediate relaxation, minimization of objective deterioration, multi-constraint satisfaction, partitioning-driven placement