BU-Router: Researching on Techniques of Global Router

Abstract:

Variety of routing approaches are employed by global routers in the VLSI circuit designs. Rip-up and reroute, as a conveniently implemented method, is widely used in most of modern global routers. Maze algorithm is always performed iteratively as the final technique to eliminate overflow. Maze algorithm and its ramifications can obtain an optimum solution. However, it will cost much CPU time if being used impertinently. In this work, we present a global router called Bottom-Up Router (BU-Router), with an optimized maze algorithm, which is based on multi-source multi-sink maze. BU-Router processes not the nets but the segments of nets in a sequence ordered by the length. In the progress, segments will be fixed on the global route graph edge, when the edge is saturated, which is as the basis, also known as bottom. Then the edge will be set as a blockage, which wont accept path goes through it any more. This means the edge will push the possible congestion in the future. Besides this, BU-Router optimized cost function in two ways: make the function adaptive and congestion center avoidable. Additionally, a specific optimized maze algorithm is proposed for routing a long distance segment so as to reduce the run-time.

• Periodical: Applied Mechanics and Materials (Volumes 513-517)
• Pages: 539-544
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.513-517.539
• Online since: February 2014
• Authors: Chun Yang Zhang*, Jun Fu Li, Qian Xu
• Keywords: EDA, Global Route, Maze

References

[1] Tai-Hsuan Wu , Azadeh Davoodi , Jeffrey T. Linderoth, GRIP: scalable 3D global routing using integer programming, Proceedings of the 46th Annual Design Automation Conference, July 26-31, 2009, San Francisco, California.

DOI: 10.1145/1629911.1629999

[2] J. A. Roy and I. L. Markov, High-performance routing at the nanometer scale, Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp.496-502, Nov (2007).

DOI: 10.1109/iccad.2007.4397313

[3] Chris Chu. FLUTE: Fast Lookup Table Based Wirelength Estimation Technique, Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pages 696–701, (2004).

DOI: 10.1109/iccad.2004.1382665

[4] M. D. Moffitt, MaizeRouter: Engineering an effective global router, Proceedings of the 2008 Asia and South Pacific Design Automation Conference, Jan (2008).

DOI: 10.1109/aspdac.2008.4483946

[5] Minsik Cho and David Z. Pan, BoxRouter: a new global router based on box expansion and progressive ILP, Proceedings of the 43rd annual Design Automation Conference, (2006).

DOI: 10.1109/dac.2006.229299

[6] Minsik Cho, Katrina Lu, Kun Yuan, and David Z. Pan, BoxRouter 2. 0: architecture and implementation of a hybrid and robust global router, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, (2007).

DOI: 10.1109/iccad.2007.4397314

[7] M. Pan, and C. Chu, FastRoute: A step to integrate global routing into placement, Proceedings of the International Conference on Computer-Aided Design, pp.464-471, Nov (2006).

DOI: 10.1109/iccad.2006.320159