隨著超大型積體電路製程的日益進步，晶片設計早就已經無法單純的靠人力完成，電路的複雜度是一個很重要的主因，為了處理高複雜度的設計，所以有了電子設計自動化的產生，大幅降低從擬定規格到設計定案的時間，也節省了許多人力上的付出。

在現在的奈米世代中，一個超大型積體電路晶片可能包含了幾百萬個電晶體，導致在佈局階段將有幾千萬條線必須完成繞線，繞線的問題變的越來越複雜，必須在有限的繞線區域內完成所有的繞線，否則必須退回到之前的步驟重新擺置所有元件，調整出更適合的繞線區域，這樣會使得整個電路設計在擺置與繞線的階段花費太多的時間。所以一個好的繞線器對整個電路設計來講是非常重要。

在此篇論文當中，我們使用了格子化模型來解決繞線的問題，使用格子化模型來繞線，不用太複雜的資料結構來處理，可以使得繞線的複雜度降低，並且我們使用了三層的金屬層來做為繞線的主要元件，也運用到了正負四十五度角的繞線路徑，這樣可以大幅減少繞線的路徑與長度。在我們所提出的演算法中，由於我們擬定了較小的繞線格子模型，為了避免違反設計規則檢查，所以第三金屬層在繞線時有一定的限制。雖然我們的演算法使用了三層金屬層來繞線，但是這樣的繞線方法除了可以減少訊號的長度，也可以比以往的多金屬層繞線方法降低訊號間的天線效應。我們不需要增加其他空間或是移動任何的腳位即可完成百分之百的繞線，這樣對所謂的固定模組在繞線這個步驟上會比較容易完成，不用因為無法完成百分之百的繞線，而必須再重新擺置固定模組的位置，並且整個繞線的通道高度也可以減少許多。

在測試實例中，我們使用了幾個通道繞線的測試基準，分別為YK3a、YK3b、YK3c與Deutsch’s Difficult Example (DDE)與ISCAS 85，在模擬結果，雖然在YK3c這個測試實例中，我們的繞線通道數目比較多，但是因為我們所使用的繞線格子單位較小，經過換算之後，我們的總繞線通道高度仍舊較小，整個繞線通道的高度平均減少約30個百分比的空間。

The Very Large Scale Integration (VLSI) manufacturing technology progresses is increasingly in recent year, Integrated Circuit (IC) design cannot be accomplished successfully by the pure manpower. The complexity of the IC is the major cause. In order to deal with that, Electronic Design Automation (EDA) has greatly decreased the time form establishing the system specifications to tape-out and reduced the manpower.

In nanometer-scale processing, a VLSI chip may contain several million transistors. As a result, it is highly probable that tens of millions of connecting nets have to be routed completely and successfully in the layout step. The problem of the routing becomes more and more complicated. We must finish the all routing nets in the finite routing region, or going back to replace the whole components in prior step. It is in order to adjust to more suitable routing region, then expending too much time in placement and routing. In a word, a nice router is very important for IC design.

In this paper, we use the grid-model to deal with the routing problem. The advantage of using grid-model needs not too complex data structure to solve it, and making the complexity of routing lower. Besides, we use the three metal-layers to be the major components of routing. We also use the positive and negative 45 degrees routing path, and therefore reduce the routing path and length. In our proposed algorithm, we draw up the smaller grid-model, and in order to avoid violating the Design Rule Check (DRC), so the algorithm has a restriction for the third metal-layer in routing step. Although we use three metal-layers in our algorithm, this way can not only reduce the signal length but also decrease the antenna effect between signals than the other multilayer routing algorithm. We needn’t increasing the other spaces and moving any pins to finish the routing completely. The foregoing is good for hard blocks to finish the routing easily, and it does not replace the location of hard blocks because of routing incompletely. Therefore, the height of the entire routing channel can reduce a lot.

In the test cases, we use several test benchmarks of channel routing, including YK3a, YK3b, YK3c, Deutsch’s Difficult Example (DDE) and ISCAS 85 benchmarks. In the simulation results, the result of YK3c has more numbers of the routing track than others, even so, our routing channel height after conversion still less than others, because our unit of grid-model is smaller than others. The height of routing channel decrease 30% in average and it can guarantee to achieve 100% routing.

TABLE OF CONTENTS
Chinese Abstract····················································································· I
English Abstract······················································································ III
Table of Contents····················································································· V
List of Figures··························································································· VIII
List of Tables····························································································· XI
CHAPTER 1 INTRODUCTION······························································· 1
1.1 Preliminaries·························································································· 6
1.1.1 VLSI design problem············································································· 6
1.1.2 Motivation···························································································· 7
1.2 Physical Design ····················································································· 8
1.2.1 Physical design cycle············································································· 8
1.2.2 Partitioning·························································································· 9
1.2.3 Floorplanning······················································································· 10
1.2.4 Placement····························································································· 11
1.2.5 Routing································································································ 13
1.2.6 Compaction·························································································· 14
1.3 Design Styles··························································································· 15
1.3.1 Full-Custom style·················································································· 15
1.3.2 Standard cell style················································································· 16
1.3.3 Gate array style···················································································· 18
1.3.4 FPGA (Field Programmable Gate Array) style········································· 19
1.3.5 Comparison of different design style······················································· 21
CHAPTER 2 DETAILED ROUTING··················································· 22
2.1 Channel Routing···················································································· 22
2.1.1 Channel routing problem··················································································· 22
2.1.2 Channel routing model······················································································· 23
2-2 Routing Models····················································································· 24
2.2.1 Grid model··························································································· 24
2.2.2 Manhattan-Diagonal model···································································· 25
2.2.3 Grid size······························································································· 26
2.2.4 The special rule of restricting Metal-3····················································· 28
2-3 Star Routing··························································································· 29
CHAPTER 3 THE STAR-ROUTING ROUTER······························ 30
3-1 Initialization··························································································· 31
3.1.1 Channel routing model·········································································· 31
3-2 Compute the Correlation of Nodes······················································ 33
3.2.1 Record the location of nodes··································································· 33
3-3 Preliminary Metal-2 Initialization······················································· 35
3.3.1 Algorithm of orientating the initial Metal-2············································· 35
3.3.2 Rules of orientating the initial Metal-2···················································· 38
3.3.3 Rules of orientating the initial Metal-3···················································· 54
3.3.4 Result of orientating the initial Metal-2··················································· 55
3-4 Route the Other Terminals··································································· 56
3.4.1 Routing method for the most terminals··················································· 56
3-5 The Routing Method of Preliminary Un-routed Set·························· 60
3.5.1 Definition table of the symbols for searching shortest and multilayer
routing path························································································· 60
3.5.2 Recording the center············································································· 61
3.5.3 Searching sequence of Metal-1 or Metal-2 for grid node GA······················ 62
3.5.4 Searching sequence of Metal-3 for grid node GA······································ 64
3.5.5 Searching basis of Metal-1 for grid node GA············································ 66
3.5.6 Searching basis of Metal-2 for grid node GA············································ 68
3.5.7 Searching basis of Metal-3 for grid node GA············································ 70
3.5.8 Reducing the redundant Metal and via···················································· 72
3.5.9 Routing result of searching shortest and multilayer routing path··············· 76
3.6 The Routing Method for the Few Terminals of Routing Failed········ 77
3.6.1 The terminal set of routing failed after searching shortest and multilayer
routing path························································································· 77
3.6.2 Reorder the sequence of Metal-2···························································· 79
CHPATER 4 EXPERIMENTAL RESULTS······································· 80
4-1 The test benchmarks············································································· 80
4-2 Comparison results of the first test set················································ 82
4-3 Comparison results of the second test set············································ 83
CHAPTER 5 CONCLUSIONS····································································· 84
References·································································································· 86

LIST OF FIGURES
Figure 1.1 The first integrated circuits (ICs) invented by Mr. Kilby·························· 1
Figure 1.2 Moore’s Law··················································································· 2
Figure 1.3 A simple VLSI design flowchart·························································· 3
Figure 1.4 Physical design cycle········································································ 8
Figure 1.5 The illustration of partitioning stage···················································· 9
Figure 1.6 Structure of slicing············································································ 10
Figure 1.7 The slicing tree············································································· 10
Figure 1.8 Example of Standard Cell Placement···················································· 12
Figure 1.9 Two phases of routing······································································· 12
Figure 1.10 Two phases of routing flowchart························································· 13
Figure 1.11 Example of 2-D compaction······························································· 14
Figure 1.12 Full-Custom structure········································································ 17
Figure 1.13 Standard Cell structure······································································ 17
Figure 1.14 Gate array structure··········································································· 17
Figure 1.15 FPGA structure················································································ 20
Figure 2.1 Channel routing model······································································ 23
Figure 2.2 Grid based routing model··································································· 24
Figure 2.3 Grid-less based routing model····························································· 24
Figure 2.4 Manhattan and Manhattan-Diagonal model··········································· 25
Figure 2.5 The grid size of Metal-2 for Manhattan model······································· 26
Figure 2.6 The grid size of Metal-2 or Metal-3 for MD model································· 27
Figure 2.7 The grid size of Metal-3 for our MD model··········································· 27
Figure 2.8 The star shape of our routing algorithm················································ 29
Figure 3.1 The star-routing algorithm flowchart···················································· 30
Figure 3.2 An example of the channel routing································································ 32
Figure 3.3 The special example of the channel routing·········································· 32
Figure 3.4 Algorithm of orientating the Metal-2···················································· 37
Figure 3.5 Illustration of the Figure 3.4 L-03························································ 38
Figure 3.6 Illustration of the Figure 3.4 L-05························································ 38
Figure 3.7 Illustration of the Figure 3.4 L-08························································ 39
Figure 3.8 Illustration of the Figure 3.4 L-11························································ 40
Figure 3.9 Illustration case 1 of the Figure 3.4 L-13·············································· 40
Figure 3.10 Illustration case 2 of the Figure 3.4 L-13·············································· 42
Figure 3.11 Illustration of the Figure 3.4 L-14························································ 42
Figure 3.12 Illustration case 1 of the Figure 3.4 L-17·············································· 43
Figure 3.13 Illustration case 2 of the Figure 3.4 L-17·············································· 43
Figure 3.14 Illustration of the Figure 3.4 L-18························································ 44
Figure 3.15 Illustration of the Figure 3.4 L-21························································ 45
Figure 3.16 Illustration of the Figure 3.4 L-23························································ 46
Figure 3.17 Illustration of the Figure 3.4 L-24························································ 47
Figure 3.18 Illustration of the Figure 3.4 L-25························································ 48
Figure 3.19 Illustration of the Figure 3.4 L-29························································ 49
Figure 3.20 Illustration of the Figure 3.4 L-31························································ 49
Figure 3.21 Illustration of the Figure 3.4 L-32························································ 51
Figure 3.22 Illustration of the Figure 3.4 L-36························································ 51
Figure 3.23 Illustration of the Figure 3.4 L-38························································ 52
Figure 3.24 Illustration of the Figure 3.4 L-39························································ 53
Figure 3.25 The rules of the Metal-3 to route the diagonal line·································· 54
Figure 3.26 The result of the Figure 3.1 that routed with our proposed algorithm········· 55
Figure 3.27 Routing result is violating the special Metal-3 rule and routing error········· 57
Figure 3.28 Success and failure of using Metal-1 to route vertical line························ 57
Figure 3.29 The routing result of the most terminals for Figure 3.2···························· 58
Figure 3.30 The illustration of assigning numbers to the sequence····························· 59
Figure 3.31 The illustration of searching sequence for Metal-1 or Metal-2·················· 63
Figure 3.32 The illustration of searching sequence for Metal-3································· 65
Figure 3.33 Searching basis of Metal-1 for gird node GA········································· 67
Figure 3.34 Searching basis of Metal-2 for gird node GA········································· 69
Figure 3.35 Searching basis of Metal-3 for gird node GA········································· 71
Figure 3.36 The situation of some redundant Metal and via······································ 72
Figure 3.37 The single linked list for recording the shortest and multilayer routing path 73
Figure 3.38 The rules of searching the node for redundant Metal and via···················· 73
Figure 3.39 Grid node GA is situated at the set 1 of Figure 3.38································ 73
Figure 3.40 Grid node GA is situated at the set 2 of Figure 3.38································ 75
Figure 3.41 Grid node GA is situated at the set 3 of Figure 3.38································ 75
Figure 3.42 Routing result of searching shortest and multilayer routing path of Figure
3.28······························································································· 76
Figure 3.43 The extending sample of Metal··························································· 78

LIST OF TABLES
Table 1.1 The evolution of ICs··········································································· 2
Table 1.2 Comparisons of design styles······························································· 20
Table 3.1 The recording table of the Figure 3.2····················································· 34
Table 3.2 The definition table of the symbols in our algorithm································ 36
Table 3.3 The preliminary un-routed terminal set·················································· 59
Table 3.4 The definition table of symbols for searching shortest and multilayer
routing path······················································································ 60
Table 4.1 The characteristics of the benchmarks for first test set······························ 81
Table 4.2 The characteristics of the benchmarks for second test set·························· 81
Table 4.3 The comparison results of the first test set·············································· 82
Table 4.4 The comparison results of the second test set·········································· 83

[1]	http://www.ti.com/
[2]	http://www.seed.slb.com/
[3]	http://en.wikipedia.org/
[4]	http://www.intel.com/
[5]	Naveed A. Sherwani, Algorithms for LSI Physical Design Automation, 1999
[6]	U. Lauther, "A Min-Cut Placement Algorithm for General Cell Assemblies Based on a 	Graph Representation," in Proc.16-th Design Automation Conf., pp. 1-10, Jun. 1979.
[7]	J. Soukup, "Global Router," in Proc.16-th Design Automation Conf., pp. 481-484, Jun. 	1979.
[8]	E.S. Kuh and T. Ohtsuki, "Recent Advances in VLSI Layout," in Proc. IEEE, vol. 78,  	no. 2, pp. 237-263, Feb. 1990.
[9]	H. Fischer and W. Pschunder, "Low-Cost Solar Cells Based on Large-Area 	Unconventional Silicon," IEEE Trans. Electron Devices, vol.24, no. 4, pp. 438-442, Apr. 	1977.
[10]	Y. Cai and D.F. Wong, "Optimal Via-Shifting in Channel Compaction," in Proc. 	European Design Automation Conference, pp. 186-190, Mar. 1990.
[11]	U. Choudhury and A. Sangiovanni-Vincentelli, "Constraint-Based Channel Routing for 	Analog and Mixed Analog/Digital Circuits," in Proc. Int. Conf. Computer-Aided Design, 	pp. 198-201, Nov. 1990.
[12]	H.W. Leong and C.L. Liu, "Discretionary Channel Routing," IEE Proc. Circuits, Devices, 	and Systems, vol. 135, no. 2, pp. 45-57, Apr. 1988.

[13]	N. Funabiki and Y. Takefuji, "A Parallel Algorithm for Channel Routing Problems 	[VLSI]," IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems,    	vol. 11, no. 4, pp. 464-474, Apr. 1992.
[14]	H.H. Chen and E.S. Kuh, "Glitter: A Gridless Variable-Width Channel Router," IEEE 	Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 5, no. 4,      	pp. 459-465, Oct. 1986.
[15] T. Yoshimura and E.S. Kuh, "Efficient Algorithms for Channel Routing," IEEE 	Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 1, no. 1,      	pp. 25-35, Jan. 1982.
[16]	R.L. Rivest and C.M. Fiduccia, "A Greedy Channel Router," in Proc. 19th Design 	Automation Conf., pp. 418-424, Jun. 1982.
[17]	J. Cong, D.F. Wong and C.L. Liu, "A New Approach to Three- or Four-Layer Channel 	Routing," IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems,   	vol. 7, no. 10, pp. 1094-1104, Oct. 1988.
[18]	C. J. Liu, Y. C. Lin and J. C. Rau, "The Grid-Based Two-Layer Routing Algorithm 	Suitable for Cell/IP-Based Circuit Design," to appear in Proc. IEEE Int. Conf. 	Electronics, Circuits and Systems, 2008.
[19]	K. Chaudhary and P. Robinson, "Channel Routing by Sorting," IEEE Trans.	Computer-Aided Design of Integrated Circuits and Systems, vol. 10, no. 6, pp. 754-760, 	Jun. 1991.
[20]	D. Lou, Y. Li, X. Zhang and J. Yu, "A Routing Algorithm for Irregular Channel Based on 	MD Model," in Proc. Int. Conf. Communications, Circuits and Systems, vol. 2, pp. 	1263-1266, May 2005.
[21]	S. Das and B. Bhattacharya, "Channel routing in Manhattan-diagonal model," in 	Proc.9-th Int. Conf. VLSI Design, pp. 43-48, Jan. 1996.
[22]	T. Y. Ho, C. F. Chang, Y. W. Chang and S. J. Chen, "Multilevel Full-Chip Routing for the 	X-Based Architecture," in Proc. 42nd Design Automation Conf., pp. 597-602, Jun. 2005.
[23]	S. S. Chen, C.H. Yang and S. J. Chen, "Bubble-Sort Approach to Channel Routing," IEE 	Proc. Computers and Digital Techniques, vol. 147, no. 6, pp. 415-422, Nov. 2000.
[24]	Y. Yu, B. Yang, X. Zhang and J. Yu, "Crosstalk Minimization in Four-Layer 	Non-Manhattan Channel Routing," in Proc. Int. Conf. Communications, Circuits and 	Systems, vol. 2, pp. 1281-1285, Jun. 2004.
[25]	C.Y. Chen, C.Y. Hou and U. Singh, "Optimal Algorithms for Bubble Sort Based 	Non-Manhattan Channel Routing," IEEE Trans. Computer-Aided Design of Integrated 	Circuits and Systems, vol. 13, no. 5, pp. 603-609, May 1994.
[26]	Z. Cao, T. Jing, Y. Hu, Y. Shi, X. Hong, X. Hu and G. Yan, "DraXRouter: Global Routing 	in X-Architecture With Dynamic Resource Assignment," In Proc. Asia and South Pacific 	Conf. Design Automation, pp. 618-623, Jan. 2006.
[27]	E. Lodi, F. Luccio, and L. Pagli, "A preliminary study of a diagonal channel-routing 	model," Algorithmica, pp. 585–597, 1989.
[28]	X. Tan and X. Song, "Improvement on the diagonal routing model," in IEE Proc. 	Circuits, Devices and Systems, pp. 535–536, 1994.
[29]	C. K. Koh and P. H. Madden, "Manhattan or nonmanhattan ? : A study of alternative 	VLSI routing architectures, " in Proc. 10th Great Lakes Symposium on VLSI, pp. 47–52, 	2000.
[30]	M.R. Stan, F. Hamzaoglu and D. Garrett, "Non-Manhattan Maze Routing," in Proc. 17th 	Symposium on Integrated Circuits and Systems Design, pp. 260-265, Sep. 2004.