隨著半導體製程的日益進步，數位電路所面臨的繞線問題變得越來越複雜，伴隨而來的問題就有電路是否能完成100%繞線以及所需要用到的總繞線面積大小…等。如果一個電路有不能完成繞線的部份，繞線器將會花費相當多的時間在做重新繞線的工作上，所以要在元件放置之後就要開始分析繞線所需的繞線資源以及其他繞線時所需要的相關資訊。

在使用標準電路單元設計電路時，我們首先會先將設計完的電路，找出其對應的標準電路元件，然後先做初步的電路元件放置之後，再進行繞線的動作。在此篇論文中，我們使用格子化模型來作繞線的依據，使用格子化模型的好處是它會使繞線的複雜度降低，只要依照格子化模型去繞線，就不會有設計規則校正 (DRC) 違反的問題，這也會使得設計電路的時間與繞線難度大大的降低。

接下來，我們將以此格子化模型為基礎，來處理繞線時可能發生的不可繞的狀況。我們將提出一個新的方法，來解決電路不可繞的情形。我們將在放置電路元件之後，取得一些繞線所需要的相關資訊，在從這些資訊中去找出在繞線時，可能會出現的不可繞的狀況，然後搭配我們所提出的演算法，進一步地去預先解決不可繞的電路，使用我們的方法，可以達成100%的繞線結果，並且能在線性時間內完成繞線。在完成所有的繞線之後，我們可以選擇性的去增加一些空間，減少通道數目的使用，來將通道數目做一個最佳化的動作，這能針對一些需要較少通道的電路，有較大的幫助。

最後，我們使用ISCAS’85 benchmarks 來模擬我們的結果，ISCAS’85 benchmarks 是一套組合邏輯電路，我們可以知道電路內含的元件數目以及各個元件中的輸入、輸出腳數目。模擬結果，我們平均需要增加6.34%的面積，就可以完全解決電路中不可繞線的部份，並且能保證電路能100%的完成繞線。

In recent year the advance of semiconductor manufacturing technology has led to a great development, the routing problems of digital circuit design become more and more complex. The following problems that are the circuit whether it can achieve 100% routing or not and the need of total routing area…etc. If the circuit has the segments that can be route, the router will spend much more time on re-route. Therefore, after placed the components we begin analyzing the routing data and other related data that are need for routing.

Using standard cell style to design digital circuits, the first we will map the designed circuit in standard cell library and we will place the components preliminary then route the nets. In this paper, we use the grid based routing model to deal with the routing problems. The advantage of using grid based routing model is the model can reduce the complexity of routing. If the router routing the circuit base on this routing model, it will not violate the design rules check (DRC) and it will reduce more the design time and design difficulty.

 Following, we will base on the grid routing model to deal with the unrouted problems that maybe occur during routing the nets. We propose a novel approach to solve the unrouted problems. After we placed the components of circuit, we will get some related data that are need for routing and we will find the unrouted conditions from these data beforehand. After that using our propose algorithm to solve the unrouted circuits in advance and using our approach can achieve 100% routing results and it can finish in linear time. Complete all of the nets routing, we can add some space selectively to reduce the numbers of channel tracks. Optimize the numbers of channel tracks that is helpful to reduce the channel height.

Finally, we use the ISCAS’85 benchmarks to simulate the results. The ISCAS’85 benchmarks are a group of combinatorial logic circuits that we know how many components、inputs and outputs of circuits. In the simulation results, the area overhead only increase 6.34% in average to solve all of the unrouted segments and it can guarantee to achieve 100% routing.

TABLE OF CONTENTS

中文摘要………………………………………………………………..	I
英文摘要...……………………………………………………………. .	III
Table of Contents ……………………………………………...	V

List of Figures ………………………………………………...	VII

List of Tables ………………………………………………….	IX

	
Chapter 1 INTRODUCTION ………………………………	1
	
1-1 Preliminaries………………………………………………………………..	3
      1.1.1 VLSI Design Problem………………………………………………. .	3
      1.1.2 Motivation…………………………………………………………….	4
1-2 Physical Design………………………………………………….. . 	4
      1.2.1 Physical Design Cycle………………………………………………. .	4
      1.2.2 Partitioning……………………………………………………………	6
      1.2.3 Floorplanning…………………………………………………………	7
      1.2.4 Placement……………………………………………………………. .	8
      1.2.5 Routing………………………………………………………………. .	9
      1.2.6 Compaction……………………………………………………………	12
1-3 Design Styles………………………………………………….. …..	13
      1.3.1 Full-Custom Style……………………………………………. ………	13
      1.3.2 Standard Cell Style …………………………………………………...	14
      1.3.3 Gate Array Style…………………………………………………... ... 	16
      1.3.4 FPGA (Field Programmable Gate Array) Style…………………... .	17
      1.3.5 Comparison of Different Design Style…………………... ... ……….	19
	
Chapter 2 DETAILED ROUTING ………………………. .	21
	
2-1 Routing Models………………………………………………….. .	21
2-2 Channel Routing…………………………………………………..	22
     2.2.1 Channel Routing Model …………………………………………….. . 	22
     2.2.2 Channel Routing Problem……………………………………………..	23
2-3 Switchbox Routing…………………………………………………	24
     2.3.1 Switchbox Routing Model …………………………………………….	24
     2.3.2 Switchbox Routing Problem…………………………………………. 	25
	
Chapter 3 THE EXTENSIBLE ROUTER ………………. .	26
	
3-1 Initilization………………………………... ………………... ……	26
     3.1.1 Initial the terminals……………………………………………………	26
3-2 Constraint Graph……………………………………. ………. …	27
     3.2.1 Horizontal Constraint Graph…………………………………………	27
     3.2.2 Vertical Constraint Graph…………………………………………. . .	28
3-3 The Left-edge Algorithm…………………………………….. …. .	32
     3.3.1 Basic Left-edge Algorithm…………………………………………….	32
3-4 Insert Space for avoid Vertical Constraint………………………	34
     3.4.1 Find the vertical constraint……………………………………………	34
     3.4.2 Insert the space…………………………………………………………	35
     3.4.3 Update the data structure …………………………………………….	37
3-5 Insert Space for reduce channel tracks……………………….. 	37
     3.5.1 Cases of optimization…………………………………………………. 	37
     3.5.2 Horizontal segment optimization……………………………………. .	39
	
Chapter 4 EXPERIMENTAL RESULTS…….. ….. …. …. .	45
	
4-1 The ISCAS’85 benchmarks………………………………………………	45
4-2 The ChAOS Router vs. The Extensible Router……………………	46
4-3 Comparison Results………………………………………………………	47
	
Chapter 5 CONCLUSIONS……………………. ………. …	50
	
References …………………………………………………….	51
	


LIST OF FIGURES

Figure 1.1     Use Manual or Automation to realize Chip…...…………………. 	1
Figure 1.2     VLSI Design Cycle ………………………………………………	2
Figure 1.3     Physical Design Cycle ………………………………………. …. 	5
Figure 1.4     Partitioning Stage ………………………………………. ……….	6
Figure 1.5     Slicing Structure ………………………………………. ………. . 	7
Figure 1.6     Slicing Tree ………………………………………. …………….   	7
Figure 1.7     Objectives of Placement ………………………………………….	9
Figure 1.8     Example of Standard Cell Placement …………………………….	9
Figure 1.9     Two phases of Routing …………………………………………. . 	10
Figure 1.10    Two phases of Routing Flowchart………………………………. .	11
Figure 1.11    Example of 2-D Compaction……………………………………. .	12
Figure 1.12    Full-Custom Structure…………………………………………….	15
Figure 1.13    Standard Cell Structure…………………………………………. . 	15
Figure 1.14    Gate Array Structure………………………………………………	17
Figure 1.15    FPGA Structure…………………………………………………. .	18
	
Figure 2.1     Grid Based Routing Model …………………………………. …. 	22
Figure 2.2     Grid-less Based Routing Model ………………………………….	22
Figure 2.3    Channel Routing Model……………………... …………………. .	23
Figure 2.4     Switchbox Routing Model ……………………………. ………. . 	24
	
Figure 3.1     Placement of the Terminals ………………………………………	26
Figure 3.2     Compute Every Horizontal Line Segment ………………………. 	27
Figure 3.3     The Horizontal Constraint Graph ………………………………. .	28
Figure 3.4     The Contents of V(G) and E(G) ………………………………….	29
Figure 3.5     Data structure of undirected graph ………. …. …. …. …. ……. .	30
Figure 3.6     Find the Vertical Constraints …………………………….. .. .. .. ..	30
Figure 3.7     The Vertical Constraint Graph ……………………………….. .. ..	31
Figure 3.8     Data structure of directed graph ………………………………….	32
Figure 3.9     The Left-edge Algorithm ………………………... ………………	33
Figure 3.10    Example of after Left-edge Algorithm……………………………	34
Figure 3.11    Example of preliminary routing with the vertical constraints…….	35
Figure 3.12    Solution of Vertical Constraint violations………………………. . 	36
Figure 3.13    The Insert Space Algorithm………………………………………	36
Figure 3.14    Example for using the insert space algorithm necessarily………. 	37
Figure 3.15    Two cases of optimization………………………………………. .	38
Figure 3.16    After optimizing the horizontal line segments……………………	38
Figure 3.17    The Horizontal Segment Optimization Algorithm………………. 	40
Figure 3.18    The original condition that we will optimize……………………. 	40
Figure 3.19    The extended condition(overlap one contact) ……………………	41
Figure 3.20    The extended condition(overlap two contacts) …………………. 	41
Figure 3.21    Find the Cases of optimization……………………………………	42
Figure 3.22    After insert the zero terminals……………………………………. 	42
Figure 3.23    Shift the horizontal line segments………………………………. .	43
Figure 3.24    The case that we do not shift it……………………………………	44
Figure 3.25    The final routing solution…………………………………………	44
	


LIST OF TABLES

Table 1.1     Comparisons of Design Styles …………………………………….	20
	
Table 4.1     The information about ISCAS’85 benchmarks ……………………	45
Table 4.2     The ChAOS Router………………………………………………. .	46
Table 4.3     The Extensible Router……………………………………………. 	47
Table 4.4     Comparison of ChAOS Router and Extensible Router……………	48
Table 4.5     The data of horizontal segment optimization………………………	49
Table 4.6     The data of horizontal segment optimization………………………	49

[1] Bass, M.J.; Christensen, C.M., “The future of the microprocessor business”, IEEE Spectrum, Vol.39, April 2002, pp. 34-39.
[2] Daniel, M.E.; Gwyn, C.W., “CAD Systems for IC Design”, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, Vol.1, January 1982, pp. 2-12.
[3] Lauther, U., “A Min-Cut Placement Algorithm for General Cell Assemblies Based on a Graph Representation”, Design Automation, 1979. 16th Conference on, June 1979, pp.1-10
[4] Soukup, J., “Global Router”, Design Automation, 16th Conference on, 25-27 June 1979, pp.481-484.
[5] Kuh, E.S.; Ohtsuki, T., “Recent advances in VLSI layout”, Proceedings of the IEEE, Vol.78, February 1990, pp. 237-263.
[6] Fischer, H.; Pschunder, W., “Low-cost solar cells based on large-area unconventional silicon”, Electron Devices, IEEE Transactions on, Vol.24, April 1977, pp. 438-442.
[7] Chen, H.H.; Kuh, E.S., “Glitter: A Gridless Variable-Width Channel Router”, International Journal of Science and Technology, Vol.5, October 1986, pp. 59-465. 
[8] Leong, H.W.; Liu, C.L., “Discretionary channel routing”,  IEE Proceedings-Circuits, Devices, and Systems, Vol.135, April 1988, pp. 45-57.
[9] Funabiki, N.; Takefuji, Y., “A parallel algorithm for channel routing problems [VLSI]”, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, Vol. 11,  April 1992 pp.:464-474
[10] Yang Cai; Wong, D.F., “Optimal via-shifting in channel compaction”, Design Automation Conference, EDAC. Proceedings of the European, March 1990, pp. 186-190.
[11] Choudhury, U.; Sangiovanni-Vincentelli, A., “Constraint-based channel routing for analog and mixed analog/digital circuits”,  ICCAD-90. Digest of Technical Papers., IEEE International Conference on, November 1990, pp. 198-201.
[12] Deutsch, D.N., “Solutions to a Switchbox Routing Problem”, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, Vol.4, April 1985, pp.163-163
[13] Chi-Ping Hsu, “General River Routing Algorithm”, Design Automation, 20th Conference on, June 1983, pp. 578-583.
[14] Yoshimura, T., “An Efficient Channel Router”, Design Automation, 21st Conference on, June 1984, pp. 38-44.
[15] Wada, M.M., “A Dogleg Optimal Channel Router with Completion Enhancements”, Design Automation, 18th Conference on, June 1981, pp. 762-768
[16] Rivest, R.L.; Fiduccia, C.M., “A Greedy Channel Router”, Design Automation, 19th Conference on, June 1982 6, pp. 418-424. 
[17] http://www.fm.vslib.cz/~kes/asic/iscas/
[18] dos Santos, G.B.V.; de Oliveira Johann, M.; da Luz Reis, R.A., “Channel based routing in channel-less circuits”, Circuits and Systems, IEEE International Symposium on, May 2006, pp. 4.