本論文從基本IC設計開始，從規格制定、邏輯合成、最後到電路佈局與繞線，這個部分就是我們研究的方向，要如何使用或修改成更佳的演算方法使得使用的線長和運算速度更快是我們的最終目的。
    在重分佈層(RDL, Redistribution layer)目前多廣泛使用在覆晶技術(Flip-Chip)上，而覆晶技術是一種將IC與基板(substrate)相互連接，基於小尺寸晶片、高I/O密度的封裝(Packaging)方法。在封裝過程中，先將晶片的墊片(pad)長出凸塊(bump)，然後將其翻覆過來，椅面朝下的方式將晶片上的墊片透過金屬導體與基板的接合點相互連接的封裝技術。
    然而，在最初的時期並不具有面陣列(area array)的設計，所以在早期的應用上並不如預期般的推廣，直到後來才出現重分佈層(Redistribution layer)的技術來改善這項方案，重分佈層被設計裝置在晶片的表層、並對I/O接口進行重新佈局，重分佈層是在晶圓表面沉積金屬層和介質層、並形成相應的金屬佈線，將分散在四周的I/O接口重新分佈成平面二維陣列的分佈方式。
    繞線演算法的目的是利用晶片四個邊緣的I/O接腳(I/O pad)重新分布到平面的凸塊墊片(bump pad)上。大致上的步驟為 : 全域繞線跟細部繞線兩種；而全域繞線又分成四個步驟 : 1.區塊分割 2.區塊合併 3.建立路網圖 4.分配線路。其中所說到的 ”區塊模組” 所要探討的是 : 當一個矩形區塊的四周圍有數條線路需經過此區塊時，該如何正確的分配路線的空間與走位。
    經過了區塊合併之後，我們應用了無線分散式演算法(Wireless Ad-hoc Neatwork)，作細部規劃中尋徑演算法之應用，其演算法本身是用於點對點的一個封包傳送式演算法，但我們將參考論文最初演算法的思維後加以修改，在應用到細部規劃裡面的尋徑規劃，並達成優化的效果。
    分散式演算法有分成三個部分 :  CT模式、AR模式及BACK模式；利用點與點之間相對角度的判斷，在佈線時演算法內容會經由三種模式的選取，進而使用每個模式所提供的走位方法，可以較快速的進行佈線而達到更佳的模擬結果。

Redistribution layer(RDL), which abundantly applied on Flip-chip technology in recent years. Flip-chip is similar to conventional IC fabrication with a few additional steps, the chip is inverted to bring the solder down so that the solder balls are facing the connections on the external circuit. Then the solder re-melt to produce an electrical connection, and use insulator to fix the substrate.
    However, the I/O ports of Flip-chip technology does not have plane array design, so it faced a huge challenge that the design of redistribution layer appeared. Redistribution layer is a re-routing process between deposited metal layer and medium layer. This technology re-assign I/O port into plane array for more spacious area.
     When distribution progress begin, the obstacles could appear on the surface and affect routing process. Our thesis mainly focus on this problem that also find other better Ad-hoc algorithm to alleviate wire length and routing time. The previous work is divided into two parts : Global Routing and Detail Routing.
     Global Routing means a rough blueprint of region range, including tiles and bump pads. We expend the edges of these tiles, bump pads for the purpose of cutting the whole segment in to lots of rectangle section. When those tiles are approximately set up, we could estimate how many paths which pass between the tiles. Then combined every tiles in “flow network”, according to the graph that we can link any two point when needed. Detail Routing represents a real geometric construction which is conscious of it’s “metal wires” and “channels. Although the process of the Detail Routing is easier than Global Routing, but we still consider some design rules, just like “wire length” and “routing angle”. At last, we apply the “Minimum-Cost Flow Problem” in order to construct the routing network. Finally, we transform the network-flow into routing topology, than based on the topology that determines the specific wire location and complete the whole routing procedure.
     We apply and rewrite the Ad-hoc network system that extends a new algorithm to improve former network. A major limitation with these nodes is that they have high mobility, causing links to be frequently broken and reestablished. Our algorithm divided into three model : CT mode、AR mode and BACK mode, through the transform of packet mode could represent different convention state. According the accurate angle between source and destination that we can receive a better simulation result in our thesis. Finally, the design of a mobile ad hoc network is highly challenging, but this technology has high prospects to be able to manage communication protocols of the future.

中文摘要…………………………………………………..……I
英文摘要……………………………………………………....II
目錄……………………………………………………....……V
圖目錄……………………………………………………....VIII
表目錄……………………………………………………....…X
Chapter 1 緒論………………………………………………..1
	1.1	 IC製作流程與概要…………………………………………...1
	1.2	 覆晶技術與研究動機…………………………………………2
	1.3  論文綱要………………………………………………………5
Chapter 2 基本概念與理論…………………………………..6
	2.1  全域規劃與細部規劃…………………………………………6
		2.1.1  全域規劃……………………………………………..…7
		2.1.2  細部規劃......................7
	2.2  設計規則與限制………………………………………………8
	2.3  A* 搜尋演算法……………………………………………….8
	2.4  最小成本流問題…………………………………...…….…..10
Chapter 3 前者方法論
	3.1  完整繞線流程………………………………………………..11
		3.1.1  區塊劃分……………………………………………….11
		3.1.2  區塊合併……………………………………………....12
		3.1.3  路網流通結構…………………………………………13
		3.1.4  最小成本流問題………………………………………13
		3.1.5  細部規劃………………………………………………14
	3.2  障礙感知流通網路模型……………………………………..15
	3.3  現有預分配繞線方法………………………………………..19
Chapter 4 新模型與演算法應用…………………………....21
	4.1  問題描述……………………………………………………..21
	4.2  模型簡化與改進……………………………………………..22
	4.3  提出的新模型……………………………………………..…24
Chapter 5 無線分散式網路傳輸與應用……………………26
	5.1  Wireless Ad-hoc Network(WANET)簡介……………………26
	5.2  Ad-hoc傳送演算法之應用………………………………….27
	5.3  程式碼流程圖規劃…………………………………………..32
		5.3.1  區塊劃分……………………………………………....32
		5.3.2  建立網路系統結構……………………………………33
                5.3.3  細部規劃………………………………………………34
Chapter 6 模擬結果…………………………………………35
總結………………………………………………………………...37
參考文獻………………………………………………………………..38

圖目錄
圖	1.1  IC基本製作流程…………………………………………..….1
圖	1.2  覆晶技術架構圖……………………………………………....3
圖	1.3  覆晶技術封裝流程…………………………………………....4
圖	2.1  全域規劃與細部規劃……………………………………...….6
圖	1.2  最小成本流問題示意圖……………………………………..10
圖	3.1  區塊劃分……………………………………………………..11
圖	3.2  最佳化缺失………………………………………………..…12
圖	3.3  區塊中心點與中間點………………………………………..14
圖	3.4  交叉點與軌道………………………………………………..14
圖	3.5  含有六個變數的 r-vector……………………………………15
圖	3.6  OA-model與九個容量變數…………………………………17
圖	3.7  現有預分配繞線流程…………………………………….….20
圖	4.1  優化後的區塊劃分…………………………………………..22
圖	4.2  五種區塊類型………………………………………………..23
圖	4.3  全邊通行的三種佈線狀況…………………………………..24
圖	4.4  簡化後的新模組……………………………………………..25
圖	5.1  封包傳送流程圖…………………………………………..…28
圖	5.2  區塊劃分流程圖…………………………………………..…32
圖	5.3  流通網路結構之建立流程圖………………………………..33
圖	5.4  細部規劃流程圖……………………………………………..34
圖	6.1  佈線結果圖…………………………………………………..36

表目錄
表	6.1  結果比較表格………………………………………………..35

參考文獻
[1] J. W. Fang, I. J. Lin, Y. W. Chang, and J. H. WANG, “A Network-Flow-Based RDL Routing Algorithm for Flip-Chip Design,” IEEE Trans, Comput. Aided Design Integrated. Circuit Syst., vol. 26, no 8, pp. 1417-1429, Aug. 2007.

[2] Y. K. Ho, H. C. Lee, P. W. Lee, Y. W. Chang, C. F. Chang, I J. Lin, C. F. Shen, “Obstacle-Avoiding Free-assignment Routing for Flip-Chip Designs,” Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol.33, no.2, pp.224,236, Feb. 2014.

[3] J. T. Yan, Z. W. Chen, “Pre-Assignment RDL Routing via Extraction of Maximal Net Sequence” Computer Design (ICCD), 2011 IEEE 29th International Conference on, vol., no., pp.65, 70, 9-12 Oct. 2011.

[4] J. T. Yan, Z. W. Chen, “IO connection assignment and RDL routing for flip-chip designs,” Asia and South Pacific Design Automation Conference, pp.588-593, 2009.

[5] J. T. Yan and Z. W. Chen, “RDL pre-assignment routing for flip-chip design,” ACM Great Lakes Symposium on VLSI, pp.401-404, 2009.

[6] J. W. Fang, I J. Lin, P. H. Yuh, Y. W. Chang, J. H. Wang, “A routing algorithm for flip-chip design,” Computer-Aided Design, ICCAD-2005. IEEE/ACM International Conference on, vol., no., pp.753, 758, 6-10 Nov. 2005.

[7] X. D. Liu, Y. F. Zhang, G. K. Yeap, C. L. Chu, J. Sun, X. Zeng, “Global routing and track assignment for flip-chip designs,” Design Automation Conference(DAC), 2010 47th ACM/IEEE, vol., no., pp.90,93, 13-18 June 2010.

[8] T. Yan; Wong, M.D.F., “A correct network flow model for escape routing,” Design Automation Conference(DAC), 2009 46th ACM/IEEE, vol., no., pp.332,335, 26-31 July 2009.

[9] A. Levitin, Introduction to The Design and Analysis of Algorithms, 2nd. Pearson, 2009.

[10]L. T, Wang, Y. W. Cheng, K. T. Cheng, Electronic Design Automation: Synthesis, Verification, and Test (Systems on Silicon), 1st ed. Morgan Kaufmann, 2009, ch.9~11.

[11] 鄭 榮 淇 . 1999, June 10. IC 載板產業展望 [Online]. Available:http://money.hinet.net/z/zd/zdc/zdcz/zdcz_C87A5222-EA76-4F94-9ADE-F500B3297AA9.djhtm.

[12] Shao. Tao, A. L. Ananda, M. C. Chan, “Spherical Coordinate Routing for 3D Wireless Ad-hoc Sensor Network” IEEE International Conference on vol 54.

[13] C. E. Perkins and E. M. Royer. Ad-hoc on-demand distance vector routing. In Proceedings of the WMCSA, pages 90-100, 1999.