||Star-Routing Algorithm For Three-Layers Channel Routing Using Manhattan-Diagonal Model
||Department of Electrical Engineering
在測試實例中，我們使用了幾個通道繞線的測試基準，分別為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
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
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
 Naveed A. Sherwani, Algorithms for LSI Physical Design Automation, 1999
 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.
 J. Soukup, "Global Router," in Proc.16-th Design Automation Conf., pp. 481-484, Jun. 1979.
 E.S. Kuh and T. Ohtsuki, "Recent Advances in VLSI Layout," in Proc. IEEE, vol. 78, no. 2, pp. 237-263, Feb. 1990.
 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.
 Y. Cai and D.F. Wong, "Optimal Via-Shifting in Channel Compaction," in Proc. European Design Automation Conference, pp. 186-190, Mar. 1990.
 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.
 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.
 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.
 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.
 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.
 R.L. Rivest and C.M. Fiduccia, "A Greedy Channel Router," in Proc. 19th Design Automation Conf., pp. 418-424, Jun. 1982.
 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.
 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.
 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.
 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.
 S. Das and B. Bhattacharya, "Channel routing in Manhattan-diagonal model," in Proc.9-th Int. Conf. VLSI Design, pp. 43-48, Jan. 1996.
 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.
 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.
 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.
 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.
 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.
 E. Lodi, F. Luccio, and L. Pagli, "A preliminary study of a diagonal channel-routing model," Algorithmica, pp. 585–597, 1989.
 X. Tan and X. Song, "Improvement on the diagonal routing model," in IEE Proc. Circuits, Devices and Systems, pp. 535–536, 1994.
 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.
 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.