臺灣博碩士論文加值系統

由於製程與電路設計技術顯著的進展，設計複雜度達到數百萬閘級，而系統單晶片的設計需求更使得晶片複雜度提高與不同設計種類如混合訊號與高頻電路佈局的整合複雜度提高。這些對佈局最佳化都帶來了新而嚴酷的挑戰。延遲與雜訊的最佳化往往決定一個設計的成功與否，而增加導線尺寸與加大導線間間距普遍的被應用來解決這兩個最佳化的問題。在設計流程的後端裡，經常須要執行後端設計變更(ECO)繞線來作延遲和雜訊的最佳化。而先前設計裡已存在龐大數目的障礙物與為因應不同雜訊與延遲問題而衍生各式各樣的設計規則使得 ECO繞線變得非常困難。與網格式繞線器相較，非網格式繞線器更能夠克服前述問題的瓶頸。為了能夠快速執行數百萬閘級設計與系統單晶片的ECO繞線，論文中我們建置了一個有效率的方塊式點對點繞線器。

雖然方塊式繞線器在非點格式繞線器中擁有較簡單的繞線圖形，但是隨著晶片複雜度的增加，其繞線圖形複雜度也增加至百萬以上的節點數目，因此有效簡化在繞線時所處理的繞線圖形節點複雜度可大幅提高執行效率。在本論文中，我們提出兩種方法來加快方塊式繞線器的執行效率。第一種是繞線圖形節點的簡化。我們提出兩種方法不但可以減少方塊碎裂的情形，進而提高了繞線的執行效率而且不會因簡化繞線圖形而犧牲繞線品質。第二種是ECO全域繞線。我們提出不同的繞線資源評估方式以適用ECO繞線問題的特質，此外也提出由擴展繞線與全域細胞內部導線路徑重組與全域細胞重新規劃的繞線流程，除了保證一定可以找到存在的繞縣路徑外，也由於限制了繞線搜尋的範圍，更可大大減少所需的繞線時間，不過會付出降低一些繞線品質的代價。實驗結果顯示，簡化繞線圖形可減少繞線時間約40%;而進一步應用ECO全域繞線更可大幅減少繞線時間至85%左右。

Remarkable advances in the process and circuit designs bring crucial challenges for optimizing the layout of a multi-million gate design. Moreover, introducing System On a Chip (SOC) design methodology greatly increases the design complexity and the layout integration complexity of various Intelligent Properties (IPs). Delay and noise optimization are dominant factors to succeed in the design, where wire sizing and spacing are widely used for solving the problems respectively. Engineering Change Order (ECO) routing is frequently requested in the later design stage for the purpose of delay and noise optimization. ECO routing is very difficult as a result of huge existing obstacles and the requests for various design rules. Gridless routers are more applicable to overcome the problem barrier than grid routers. Therefore, we develop an efficient tile-based point-to-point router for the ECO routing of multi-million gate designs in this thesis.

Although tile-based routers have less number of nodes of routing graph than grid routers and connection-based routers, as the design complexity increases, the number of nodes of tile-based routing graphs have grown over thousand millions for SOC designs. We can reduce the complexity of tile-based routing graph to promote routing performance. In this thesis, we propose two methods to promote routing speed of the tile-based router. The first is Routing Graph Reduction. We propose two methods, i.e., redundant tiles removal and neighbor tiles alignment, to reduce the complexity of tile-based routing graph. It diminishes tile fragmentation as well as reduces the routing time without sacrificing routing quality. The second is ECO Global Routing. We propose different resource estimation scheme from that used by general global routing to reflect the characteristics of ECO routing problem. Also, we propose an ECO routing flow, including extended routing and GCell restructuring and rescheduling, to guarantee to find a feasible solution if there exists such a solution. By limiting the searching scope of ECO routing, ECO global routing improves a lot the routing speed at little expense of routing quality. Experimental results show that routing graph reduction can decrease the routing time by 40% and ECO global routing with routing graph reduction can further decrease the routing time up to 85% or so.

Abstract (in Chinese).................................................. I
Abstract (in English)..................................................II
Acknowledgements.......................................................IV
List of Figures .......................................................VI
List of Tables........................................................VII

1 Introduction ....................................................... 1
1.1 ECO Routing.................................................... 1
1.2 Gridless router................................................ 2
1.3 Our approach................................................... 6

2 Tile-Based Router................................................... 8

3 Routing Graph Reduction (RGR).......................................12
3.1 Redundant Tiles Removal........................................12
3.2 Neighbor Tiles Alignment.......................................18

4 ECO Global Routing..................................................29
4.1 Global Routing Graph.0.........................................30
4.2 Extended Routing and GCell Restructuring and Rescheduling......36
4.2.1 Extended Routing...........................................38
4.2.2 GCell Restructuring and Rescheduling.......................41

5 Experimental Results................................................45

6 Conclusions.........................................................48


Bibliography...........................................................49

[1] J. Cong, L. He, C.-K. Koh, and P. Madden, “Performance optimization of VLSI interconnect layout,” Intergr. VLSI J., vol. 21, no. 1–2, pp. 1–94, Nov. 1996.

[2] T. Ohtsuki, “Gridless routers—New wire routing algorithms based on computational geometry, in Proc. Int. Conf. Circuits and Systems, pp. 802809, May 1985.

[3] K. L. Clarkson, S. Kapoor, and P. M. Vaidya, “Rectilinear shortest paths through polygonal obstacles in O(n(log n) ) time,” in Proc. 3rd Annual Symp. Computational Geometry, 1987, pp. 251–257.

[4] Y. Wu, P. Widmayer, M. Schlag, and C. Wong, “Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles,”IEEE Trans. Computers, vol. C-36, no. 1, pp. 321-331, 1987.

[5] S.Zheng, J.S. Lim, and S. Iyengar, “Finding obstacle-avoiding shortest paths using implicit connection graphs,”IEEE Trans. Computer-Aided Design, vol. 15, no. 1, pp. 103-110, Jan. 1996.

[6] J. Cong, J. Fang, and K. Khoo, “An implicit connection graph maze routing algorithm for ECO routing,” in Proc. Int. Conf. Computer-Aided Design, pp. 163167, Nov. 1999.

[7] J. Cong, J. Fang, and K. Khoo,“DUNE: A multilayer gridless routing system with wire plan-ning,”in Proc. Int. Symp. Physical Design, Apr. 2000, pp. 1218.

[8] J. Cong, J. Fang, and K. Khoo,“DUNE - A multilayer gridless routing system,”IEEE Trans. Computer-Aided Design, vol. 20, no. 5, pp. 633-647, May. 2001.

[9] M. Sato, J. Sakanaka, and T. Ohtsuki, “A fast line-search method based on a tile plane,” in IEEE Int. Symp. Circuits and Systems, pp. 588591, May 1987.

[10] A. Margarino, A. Romano, A. De Gloria, F. Curatelli, and P. Antognetti, “A tile-expansion router,”IEEE Trans. Computer-Aided Design, vol. CAD-6, pp. 507517, July 1987.

[11] R. Eric Lunow, “A Channelless, Multilayer Router,”in 25th ACM/IEEE Design Automation Conference, pp. 667 - 671, 1988.

[12] L.-C. Liu, H.-P. Tseng, and C. Sechen, “Chip-level area routing,” in Proc. Int. Symp. Physical Design, pp. 197204, Apr. 1998.

[13] C. Tsai, S. Chen, and W. Feng, “An H-V Alternating Router,” IEEE Trans. Computer-Aided Design, vol. 11, pp. 976–991, Aug. 1992.

[14] J. Dion and L. M. Monier,“Contour: A tile-based gridless router,”Western Research Laboratory, Palo Alto, CA, Research Report 95/3.

[15] Zhaoyun Xing and Russell Kaog, “Shortest Path Search Using Tiles and Piecewise Linear Cost Propagation,”IEEE Trans. Computer-Aided Design, vol. 21, no. 2, pp. 145158, Feb. 2002.
[16] J. K. Ousterhout, “Corner Stitching: Adata-structuring technique for VLSI layout tools,” IEEE Trans. Computer-Aided Design, vol. CAD-3, pp.87–100, Jan. 1984.

[17] Preparata Franco P. & Shamos Michael Ian, “ Computational geometry : an introduction”, Springer-Verlag, New York ,1985