Ordered Escape Routing Combining Improved A* Algorithm with Rip-up and Reroute

Xinguo DENG; Sijin YE; Jiarui CHEN; Chuandong CHEN

doi:10.11999/JEIT201033

Volume 43 Issue 6

Jun. 2021

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2021 > 43(6): 1609-1616

Xinguo DENG, Sijin YE, Jiarui CHEN, Chuandong CHEN. Ordered Escape Routing Combining Improved A* Algorithm with Rip-up and Reroute[J]. Journal of Electronics & Information Technology, 2021, 43(6): 1609-1616. doi: 10.11999/JEIT201033

Citation:

Xinguo DENG, Sijin YE, Jiarui CHEN, Chuandong CHEN. Ordered Escape Routing Combining Improved A* Algorithm with Rip-up and Reroute[J]. Journal of Electronics & Information Technology, 2021, 43(6): 1609-1616. doi: 10.11999/JEIT201033

Citation:

PDF( 3658 KB)

Ordered Escape Routing Combining Improved A* Algorithm with Rip-up and Reroute

doi: 10.11999/JEIT201033

1.
College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
2.
College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108, China

Funds: The National Natural Science Foundation of China (61977017), The Key Research and Development Project of the Ministry of Science and Technology (2018YFB2202704), The Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China (Mindu Innovation Laboratory) (2021ZR142)

Received Date: 2020-12-09
Rev Recd Date: 2021-04-16

Available Online: 2021-04-27

Publish Date: 2021-06-18

Abstract

Abstract

Escape routing is an important part of the integrated circuit physical design. In order to solve the problem of slow parallel escape routing with unsatisfactory outcomes, an algorithm of ordered escape routing, combining the improved A* algorithm with the rip-up and reroute method is proposed. Firstly, the routing sequence of pins is determined by the cost estimation function and the improved A* algorithm is used to initialize the ordered escape routing. Secondly, the routing paths of the same length are optimized and the routing paths of the crowded areas are adjusted. Finally, A* algorithm and breadth-first search are employed to rip-up and reroute. The experimental results shows that this method achieved 100% escape routing for all given test cases, and that the feasible solution of the ordered escape paths is, to a great extent, close to the optimal solution. Compared to the Boolean Satisfiability Problem (SAT) algorithm and MMCF algorithm, this algorithm reduces CPU time by 95.6% and 97.8%, respectively, and makes the overall line length shorter. It is evident that the proposed method reduces the time required to find the feasible solution and optimize wire routing.
- A* algorithm,
- Rip-up and reroute,
- Ordered escape routing,
- Shortest path

FullText(HTML)

References(19)

References

[1]	徐宁, 洪先龙. 超大规模集成电路物理设计理论与算法[M]. 北京: 清华大学出版社, 2009: 147–172. XU Ning and HONG Xianlong. Very Large Scale Integration Physical Design Theory and Method[M]. Beijing: Tsinghua University Press, 2009: 147–172.
[2]	YAN Tan and WONG M D F. Recent research development in PCB layout[C]. 2010 IEEE/ACM International Conference on Computer-Aided Design (ICCAD'10), San Jose, USA, 2010: 398–403. doi: 10.1109/ICCAD.2010.5654190.
[3]	WANG Kan, WANG Huaxi, and DONG Sheqin. Escape routing of mixed-pattern signals based on staggered-pin-array PCBs[C]. 2013 ACM International Symposium on Physical Design, Stateline, United States, 2013: 93–100. doi: 10.1145/2451916.2451941.
[4]	FANG Jiawei, LIN I J, CHANG Y W, et al. A network-flow-based RDL routing algorithmz for flip-chip design[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007, 26(8): 1417–1429. doi: 10.1109/TCAD.2007.891364
[5]	MA Qiang, YOUNG E F Y, and WONG M D F. An optimal algorithm for layer assignment of bus escape routing on PCBs[C]. The 48th Design Automation Conference, San Diego, United States, 2011: 176–181. doi: 10.1145/2024724.2024764.
[6]	CHO B G, KAM D G, and KOO H I. Mixed-signal escape routing algorithm for multilayer PCBs[J]. IEEE Transactions on Components, Packaging and Manufacturing Technology, 2019, 9(8): 1576–1586. doi: 10.1109/TCPMT.2019.2900463
[7]	YAN Jintai. Direction-constrained rectangle escape routing[J]. ACM Transactions on Design Automation of Electronic Systems, 2018, 23(3): 34. doi: 10.1145/3178047
[8]	ALPERT C J, MEHJTA D P, and SAPATNEKAR S S. Handbook of Algorithms for Physical Design Automation[M]. Boca Raton: CRC Press, 2008: 469–475.
[9]	TOMIOKA Y and TAKAHASHI A. Routing of monotonic parallel and orthogonal netlists for single-layer ball grid array packages[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2006, E89-A(12): 3551–3559. doi: 10.1093/ietfec/e89-a.12.3551
[10]	FANG Jiawei, HSU C H, and CHANG Yaowen. An integer-linear-programming-based routing algorithm for flip-chip designs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2009, 28(1): 98–110. doi: 10.1109/TCAD.2008.2009151
[11]	LIAO Zhaopo and DONG Sheqin. A constraint-driven compact model with partition strategy for ordered escape routing[C]. 2020 on Great Lakes Symposium on VLSI, Virtual Event, New York, USA, 2020: 393–398. doi: 10.1145/3386263.3406942.
[12]	TOMIOKA Y and TAKAHASHI A. Monotonic parallel and orthogonal routing for single-layer ball grid array packages[C]. Proceedings of 2006 Asia and South Pacific Conference on Design Automation, Yokohama, Japan, 2006: 6–12. doi: 10.1109/ASPDAC.2006.1594758.
[13]	LUO Lijuan and WONG M D F. Ordered escape routing based on Boolean satisfiability[C]. 2008 Asia and South Pacific Design Automation Conference, Seoul, Korea (South), 2008: 244–249. doi: 10.1109/ASPDAC.2008.4483950.
[14]	LUO Lijuan and WONG M D F. On using SAT to ordered escape problems[C]. 2009 Asia and South Pacific Design Automation Conference, Yokohama, Japan, 2009: 594–599. doi: 10.1109/ASPDAC.2009.4796545.
[15]	JIAO Fengxian and DONG Sheqin. Ordered escape routing with consideration of differential pair and blockage[J]. ACM Transactions on Design Automation of Electronic Systems, 2018, 23(4): 46. doi: 10.1145/3185783
[16]	朱自然, 陈建利, 朱文兴. 基于多阶段拆线重布的总体布线算法[J]. 计算机辅助设计与图形学学报, 2016, 28(11): 2000–2008. doi: 10.3969/j.issn.1003-9775.2016.11.023 ZHU Ziran, CHEN Jianli, and ZHU Wenxing. A global routing algorithm based on multistage rip-up and reroute[J]. Journal of Computer-Aided Design &Computer Graphics, 2016, 28(11): 2000–2008. doi: 10.3969/j.issn.1003-9775.2016.11.023
[17]	SHI Rui and CHENQ C K. Efficient escape routing for hexagonal array of high density I/Os[C]. The 43rd Design Automation Conference, San Francisco, USA, 2006: 1003–1008. doi: 10.1109/DAC.2006.229424.
[18]	赵奇, 赵阿群. 一种基于A算法的多径寻由算法[J]. 电子与信息学报, 2013, 35(4): 952–957. doi: 10.3724/SP.J.1146.2012.00983 ZHAO Qi and ZHAO Aqun. A multi-path routing algorithm base on A algorithm[J]. Journal of Electronics &Information Technology, 2013, 35(4): 952–957. doi: 10.3724/SP.J.1146.2012.00983
[19]	高庆吉, 于咏生, 胡丹丹. 基于改进A算法的可行性路径搜索及优化[J]. 中国民航学院学报, 2005, 23(4): 42–45. doi: 10.3969/j.issn.1001-5590.2005.04.010 GAO Qingji, YU Yongsheng, and HU Dandan. Advanced A algorithm for path-finding and optimization[J]. Journal of Civil Aviation University of China, 2005, 23(4): 42–45. doi: 10.3969/j.issn.1001-5590.2005.04.010