請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46034
標題: | 應用於覆晶設計之繞線演算法 Routing Algorithms for Flip-Chip Designs |
作者: | Po-Wei Lee 李柏緯 |
指導教授: | 張耀文(Yao-Wen Chang) |
關鍵字: | 實體設計,覆晶繞線,自由配對,非自由配對,避開障礙物的繞線, physical design,flip-chip routing,free-assignment,pre-assignment,obstacle-avoiding routing, |
出版年 : | 2010 |
學位: | 碩士 |
摘要: | 覆晶(flip-chip)封裝技術被廣泛應用於積體電路以解決高密度整合和大量輸入/輸出訊號的需求。隨著該封裝技術的引進,覆晶繞線(flip-chip routing)問題日益重要。覆晶繞線問題可被歸分為兩類:(1)自由配對(free-assignment)繞線問題、(2)非自由配對(pre-assignment)繞線問題。兩種繞線問題都存在於實際應用當中,因此越來越受到重視與關注。本論文將以兩個主題來分別探討上述兩種繞線。另一方面,現今的覆晶設計可能有許多障礙物,它們源於前置擺放的模組或線路, 我們將在論文中一併討論。
在第一個主題中,我們探討在障礙物限制下的自由配對繞線。自由配對繞線問題透過網路流通規劃(network-flow formulation)的方法可以有效地被解決。然而,據我們所知文獻上的研究未考量障礙物的效應,因此不適用於現今具有障礙物的設計。為了彌補此方面的不足,本論文首度來處理有障礙物的覆晶繞線問題。首先,我們提出一個適用於障礙物的網路流通模型來彌補先前的模型在處理障礙物上的不足。根據我們所建構的模型,我們進一步設計一套可匹配的繞線演算法。我們的繞線演算法分為兩個階段,全域繞線以及細部繞線。首先,全域繞線將問題轉化成最小成本網路流通問題(minimum-cost flow problem)以得到一個概略的繞線路徑。細部繞線再根據此概略決定詳細的實體繞線路徑。我們將提出的演算法實做成繞線器,並和文獻上具有最佳效能的繞線器做比較。由於比較的繞線器所使用的演算法並未考量障礙物,我們合理地將它改良以考慮障礙物。實驗結果顯示我們的演算法能快速且有效地完成所有測試電路的繞線;然而比較的對象無法達成。 在第二個主題中,我們先探討非自由配對繞線問題,提出一個快速且有效的繞線演算法,再進而將所提出的演算法延伸至考量障礙物。我們會以漸進的方式來研究非自由配對繞線問題是基於該問題在本質上的難度頗高——而導致了文獻上的研究十分有限,且研究成果尚未能滿足實際應用。我們設計的繞線演算法主要根據順序一致性的概念而成,並套用兩個動態程式規劃(dynamic programming)的演算法:(1)權重式最長共通序列(weighted longest common subsequence)、(2)平面上最多不相交弦之集合(maximum planar subset of chords)。另一方面,我們觀察到先前的研究在可繞度的分析上過於悲觀,以至於一些合法的繞線路徑沒有被納入考量。為了解決此問題,我們提出了較為精確的分析方式,並設計一套能在常數項時間複雜度內完成分析的程序。我們實做提出的演算法,並和文獻中最佳的繞線器做比較。比較的繞線器使用整數線性規劃(integer linear programming)的方法。結果顯示雖然兩者皆可完成所有電路的繞線,但是我們在效能上有122倍的提升;除此之外,我們甚至能得到稍短的線長。 The flip-chip package is introduced for modern IC designs with higher integration density and larger I/O counts. As the advance of technology, the flip-chip routing problems become more and more important. The problems can be classified into two categories: (1) the free-assignment routing problem and (2) the pre-assignment routing problem. Both routing problems occur in real applications and thus have received dramatically increasing attention recently. This thesis studies both routing problems with two research topics. On the other hand, modern flip-chip designs might incur a significant number of obstacles in the routing regions due to pre-placed modules and/or pre-routed nets, which is also concerned in this thesis. In the first topic, we consider the obstacle-avoiding free-assignment flip-chip routing problem. The free-assignment problem has been shown to be solved well by using network-flow formulation. To our best knowledge, however, existing published works do not consider obstacles, which might not apply to designs with obstacles well. To remedy the insufficiency, this thesis presents the first work to solve the free-assignment flip-chip routing problem considering obstacles. We first propose a new effective network-flow model to remedy the insufficiency of the previous models in obstacle handling. Based on the new model, a two-stage technique of global routing followed by detailed routing is introduced for flip-chip routing. The global routing converts the routing problem into the minimum-cost flow problem to compute a routing topology. The detailed routing then determines the final layout based on the routing topology. Compared with a state-of-the-art work with reasonable extensions to handle obstacles, the experimental results show that our algorithm is effective (100% routability for all circuits) and efficient. In the second topic, we consider the pre-assignment flip-chip routing problem first, and then extend the proposed algorithm to consider obstacles. That we advance gradually is due to the difficulty of the pre-assignment routing problem, which limits the quality of previous work. Based on the concept of routing sequence exchange, we propose a very efficient global routing algorithm by computing the weighted longest common subsequence (WLCS) and the maximum planar subset of chords (MPSC) for pre-assignment flip-chips. We observe that the existing work over constrains the capacity of a routing tile, which might miss some critical solution space with a better routing solution (e.g., smaller wirelength), and provide a remedy for this insufficiency to identify a better solution in a more complete solution space. We also develop a constant-time routability analyzer to check if a given set of wires can pass through a tile. Experimental results show that our router can achieve a 122X speedup with even better solution quality (same routability with slightly smaller wirelength), compared with a state-of-the-art flip-chip router based on integer linear programming (ILP). |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46034 |
全文授權: | 有償授權 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 1.8 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。