Congestion driven incremental placement algorithm for standard cell layout

ABSTRACT

Congestion minimization is the least understood in placement objectives, however, it models routability most accurately. In this paper, a new incremental placement algorithm C-ECOP for standard cell layout is presented to reduce routing congestion. Congestion estimation is based on a new routing model and a more accurate cost function. An integer linear programming (ILP) problem is formulated to determine cell flow direction and avoid the conflictions between adjacent congestion areas. Experimental results show that the algorithm can considerably reduce routing congestion and preserve the performance of the initial placement with high speed.

REFERENCES

• 1: A. E. Dunlop and B. W. Kernighan, "A procedure for placement of standard cell VLSI circuits," IEEE Trans. Computer Aided Design, vol. 4, pp. 92--98, Jan. 1985.
• 2: 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]
• 3: Saab et. al, "A fast clustering-based Min-cut placement algorithm with simulated-annealing performance," VLSI Design: Int. J. Custom-Chip Design, Simulation, Testing, vol. 5, no. 1, pp. 37--48, 1996.
• 4: G. Meixner and U. Lauther, "Congestion-driven placement using a new multi-partitioning heuristic," in Proc. Int. Conf. Computer-Aided Design, Nov. 1990, pp. 332--335.
• 5: Zhuoyuan Li, Weimin Wu, Xianlong Hong, Jun Gu, "Incremental placement algorithm for standard-cell layout", Circuits and Systems, 2002 IEEE International Symposium on, Volume: 2, 2002, Page(s): 883--886.
• 6: Wenting Hou , Hong Yu , Xianlong Hong , Yici Cai , Weimin Wu , Jun Gu , William H. Kao, A new congestion-driven placement algorithm based on cell inflation, Proceedings of the 2001 conference on Asia South Pacific design automation, p.605-608, January 2001, Yokohama, Japan [doi>10.1145/370155.370560]
• 7: 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
• 8: Maogang Wang; Xiaojian Yang; Sarrafzadeh, M., "Congestion minimization during placement", Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, Volume: 19 Issue: 10, Oct. 2000, Page(s): 1140--1148
• 9: Maogang Wang , Majid Sarrafzadeh, Modeling and minimization of routing congestion, Proceedings of the 2000 conference on Asia South Pacific design automation, p.185-190, January 2000, Yokohama, Japan [doi>10.1145/368434.368601]
• 10: Maogang Wang , Majid Sarrafzadeh, On the behavior of congestion minimization during placement, Proceedings of the 1999 international symposium on Physical design, p.145-150, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300044]
• 11: Olivier Coudert , Jason Cong , Sharad Malik , Majid Sarrafzadeh, Incremental CAD, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 12: Jason Cong , Majid Sarrafzadeh, Incremental physical design, Proceedings of the 2000 international symposium on Physical design, p.84-92, May 2000, San Diego, California, United States [doi>10.1145/332357.332379]
• 13: http://er.cs.ucla.edu/benchmarks/ibm-place/
• 14: http://er.cs.ucla.edu/Dragon/

INDEX TERMS

Keywords:
congestion, incremental placement, standard cell