臺灣博碩士論文加值系統

傳統超大型積體電路實體設計流程包含了規劃、置放、廣域佈線以及細部佈線。一個快速的廣域佈線器可以幫助置放器更加準確的預估線長以及可繞度。高品質的廣域佈線器也可以幫助細部佈線的可繞度。在這篇論文中，我們發展了一個高效率擁擠導向的全域佈線器，叫做 Dory。可以很快的產生比整數線性規劃基底的廣域佈線器更好的的結果。Dory 是根據 FastRoute 2.0 為基底，加上我們所發展出的歷史基底繞線、改良的繞線流程以及簡化的多重源頭多重目標迷宮繞線。實驗結果也展現出 Dory 可以在很快的時間之內減少許多的擁擠度。

在 IBM98 的測試檔方面，和現有的學術廣域佈線器 FastRoute 2.0 和 BoxRouter 相比，我們可以完成所有的電路而沒有任何的溢出，並且繞線的長度也較短。在 ISPD2007 的測試檔方面，Dory 在線長和擁擠度比 FastRoute 更好，不過花費更多的時間。Dory 比 FGR, MaizeRouter, BoxRouter 快，但是在線長和擁擠度方面比較差

Traditional VLSI physical design flow is composed of floorplanning, placement, global routing and detailed routing. A fast global router can help placer in accurately estimating wire length and routability. A high-quality global router increases routability for detailed routers. In this paper, we develop a high-performance congestion-driven global router, called Dory, to fast produce better routing results as compared to a ILP-based global router. Based on the routing flow of FastRoute 2.0, we develop a history-based routing, an enhanced routing flow and simplified multi-source multi-sink maze routings. Experimental results reveal that Dory decreases many overflows at little cost of runtime.

On IBM98 benchmarks, compared to state-of-art academic global router FastRoute 2.0, and BoxRouter, we can complete all circuits without any overflow with less wirelength. On ISPD2007 benchmarks, Dory is superior to FastRoute in overflow and wire length at the cost of worse runtime, and also superior to FGR, MaizeRouter and BoxRouter in runtime at the cost of worse overflow and wire length.

Chapter 1 Introduction 1
Chapter 2 Preliminaries 4
2.1 Grid Graph model 4
2.2 Global route metrics 4
Chapter 3 FastRoute Overview 6
3.1 Congestion Map Generation 6
3.2 Congestion-driven steiner tree construction 7
3.2.1 Congestion-driven Topology Generation 7
3.2.2 Edge Shifting 9
3.3 Monotonic Routing 10
3.4 Multi-source Multi-sink Maze Routing 12
Chapter 4 Our Global Router 16
4.1 History-based routing 16
4.2 Enhanced Routing Flow 18
4.3 Simplified Multi-Source Multi-Sink Maze Routing 21
4.3.1 Multi-source-pin Multi-destination-pin scheme 21
4.3.2 A* maze routing 23
Chapter 5 Experimental results 25
Chapter 6 Conclusion and future work 29
Chapter 7 Reference 30

[1] H. Eisenmann and F. M. Johannes. Generic global placement and f loorplanning. In Proc. ACM/IEEE Design Automation Conf., pages 269-274, 1998.
[2] X. Yang, B.-K. Choi, and M. Sarrafzadeh. Timing-driven placement using design hierarchy guided constraint generation. In Proc. IEEE/ACM Intl. Conf. Computer-Aided Design, pages 177-184, 2002.
[3] G. Stem, B. M. Riess, B. Roh_eisch and F. M. Johannes. Timing driven placement in interaction with netlist transformations. Proc. Intl. Symp. on Physical Design, pages 36-41, 1997.
[4] J. Lou, S. Krishnamoorthy, and H. Sheng. Estimating routing congestion using probabilistic analysis. In Proc. Intl. Symp. on Physical Design, pages 112-117, 2001.
[5] J. Westra, C. Bartels, and P. Groeneveld. Probabilistic congestion prediction. In Proc. Intl. Symp. on Physical Design, pages 204-209, 2004.
[6] A. B. Kahng and X. Xu. Accurate pseudo-constructive wirelength and congestion estimation. In Proc. Intl. Workshop on System-Level Interconnect Prediction(SLIP), pages. 61-68, 2003.
[7] M. Pan and C. Chu. FastRoute: A step to integrate global routing into placement. In Proc. IEEE/ACM Intl. Conf. Computer-Aided Design, pages 464-471, 2006
[8] R. Kastner, E. Bozorgzadeh and M. Sarrafzadeh. Pattern routing: Use and theory for increasing predictability and avoiding coupling. IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, pages 777-790, 2002
[9] R.T. Hadsell and P. H. Madden. Improve global routing through congestion estimation. In Proc. Design Automation Conf. pages 28-31, 2003
[10] Minsik Cho and David Pan. BoxRouter: A new global router based on box expansion and progressive ILP. In Proc. Design Automation Conf., pages 373-378, 2006
[11] Min Pan and Chris Chu. FastRoute 2.0: A high-quality and efficient global router. In Proc. Asia and South Pacific Design Automation Conf. pages 250-255, 2007
[12] http://www.ece.ucsb.edu/~kastner/labyrinth/benchmarks/
[13] http://www.ispd.cc/ispd07_contest.html
[14] http://www.ispd.cc/slides07/gr-contest.pdf
[15] C. Chu, Y. Wong. Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design. In Proc. Intl. Symp. On Physical Desgin, pages 28-35, 2005
[16] M. Hanan, On Steiner’s problem with rectilinear distance. SIAM Journal of Applied Mathematics, 14, pages 255-265, 1966
[17] E. Dijkstra. A note on two problems in connexion with graphs. In Numerische Mathmatik, vol. 1, pages 269-271, 1959
[18] L. McMurchie and C. Ebeling. Pathfinder: A negotiation-based performance-driven router for FPGAs. In Proc. Of ACM Int’l Symp on Field-Programmable Gate Arrays, pages 111-117, 1995
[19] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pages 498–524.
[20] P.E. Hart, N.J. Nilsson, and B.Raphael. A formal basis for the heuristic determination of minimum cost paths. In IEEE Transactions on System Science and Cybernetics, pages 100-107, July 1968