Fast and Effective Congestion Refinement Technique

Abstract:

Due to the promotion of modern design feature, the placement solution is becoming more and more difficult to route. Previous routability-driven based technology is usually coupled with the original placer, which is difficult to be widely used in various placement tools. In this paper, we proposed a tool called CRT (Congestion Refinement Technique), which is independent of any placer and any router, and can be applied to various placemen to improve the routability. CRT is a congestion-driven based module shifting technique. Basically, CRT is one kind of technology that better allocating routing resources by shifting the modules. The boundary of tile is shifted in the horizontal and vertical directions without affecting the original placement. Here a longest path solution is presented to solve the problem fast and effectively. The experimental results show that the CRT can effectively alleviate the congestion of unroutable placement solutions. We apply it to placement solutions generated by placers on ISPD2011 [ placement benchmarks. From the result we can see that CRT greatly improves the routbility and saves execution time for the routing stage after refinement.

• Periodical: Applied Mechanics and Materials (Volumes 530-531)
• Pages: 936-942
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.530-531.936
• Online since: February 2014
• Authors: Yan Zhao*, Yin Yao Zhao, Xu Qian
• Keywords: CRT, Effective, FAST, Longest Path, Module Shifting

References

[1] ISPD2011 contest benchmark. http: /www. ispd. cc/contests/11/ispd2011_contest. html.

[2] P. Spindler and F.M. Johannes, Fast and accurate routing demand estimation for efficient routability-driven placement. In Proc. Conf. on Design, Automation and Test in Europe, p.1226 (2007).

DOI: 10.1109/date.2007.364463

[3] U. Brenner and A. Rohe. An effective congestion-driven placement framework. In Proc. CM/SIGDA Intl. Symp. on Physical Design, p.6( 2002).

[4] M. Pan and C. Chu. IPR: An integrated placement and routing algorithm. In Proc. ACM/IEEE Design Automation Conf., p.59 (2007).

[5] M. Pan and C. Chu. FastRoute 2. 0: A high-quality and efficient global router. In Proc. Asia and South Pacific Design Automation Conf., pages 250(2007).

DOI: 10.1109/aspdac.2007.357994

[6] N. Viswanathan and C. Chu. FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model. In Proc. ACM/SIGDA Intl. Symp. on Physical Design , p.26( 2004).

DOI: 10.1145/981066.981072

[7] J. Roy and I.L. Markov. Seeing the forest and the trees: Steiner wirelength optimization in placement. IEEE Trans. on Computer-Aided Design and Integrated Circuits and Systems, 26(4) (2007).

DOI: 10.1109/tcad.2006.888260

[8] Yangheng Zhang and Chris Chu. CROP: Fast and Effective Congestion Refinement of placement. In Proc. of ICCAD, p.344 (2009).

[9] W. -H. Liu et al, Multi-Threaded Collision-Aware Global Routing with Bounded-Length Maze Routing, in Proc. DAC (2010).

DOI: 10.1145/1837274.1837324

[10] Yang, Xiaojian, Ryan Kastner, and Majid Sarrafzadeh. Congestion estimation during top-down placement., Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 21. 1 (2002): 72-80.

DOI: 10.1109/43.974139

[11] Parakh, Phiroze N., Richard B. Brown, and Karem A. Sakallah. Congestion driven quadratic placement., Proceedings of the 35th annual Design Automation Conference. ACM, (1998).

DOI: 10.1145/277044.277121

[12] M. Wang X. Yang, M. Sarrafzadeh, "Congestion Minimization during Placementeee19 (10), pp.1140-1148, (2000).

[13] M. Pan, N. Viswanathan, and C. Chu, An Efficient and Effective Detailed Placement Algorithm', ICCAD, pp.48-55, (2005).

[14] Dai K R, Lu C H, Li Y L. GRPlacer: Improving routability and wire-length of global routing with circuit replacement[C]/Proceedings of the 2009 International Conference on Computer-Aided Design. ACM, 2009: 351-356.

DOI: 10.1145/1687399.1687466