進階搜尋


下載電子全文  
系統識別號 U0026-2108201315512100
論文名稱(中文) 針對遮罩層數最小化之工程變更命令繞線方法論
論文名稱(英文) A Novel ECO Routing Methodology for Layer Mask Minimization
校院名稱 成功大學
系所名稱(中) 資訊工程學系碩博士班
系所名稱(英) Institute of Computer Science and Information Engineering
學年度 101
學期 2
出版年 102
研究生(中文) 白尚亞
研究生(英文) Shang-Ya Bai
學號 P76004253
學位類別 碩士
語文別 英文
論文頁數 32頁
口試委員 指導教授-何宗易
口試委員-林英超
口試委員-莊坤達
中文關鍵字 工程變更命令  總體繞線  整數線性規劃  細部繞線  最小 成本最大流量演算法  繞線器 
英文關鍵字 Engineering Change Order  Global Routing  Integer Linear Programming  Detailed Routing  Minimum Cost Maximum Flow  Router 
學科別分類
中文摘要 由於有繞線資源的限制以及逐漸增加的設計規則,工程變更命令
的繞線工作是一個複雜且困難的工作,並且往往在較晚的設計階段
有被應用在最佳化電路的雜音與延遲的需求。在工程變更命令的繞
線過程之後,電路的佈局往往會因為金屬層被重繞的工程變更命令
線路使用到而改變,進而導致遮罩的重新製造並造成極高的成本花
費。然而,目前卻沒有任何工程變更命令的繞線器將繞線的重點著重
在繞線時使用到的層數。因此,我們提出了一個三階段的工程變更命
令繞線流程,並且能夠在考量將使用的層數最小化的情況下將所有
的工程變更命令線路同時繞線。 首先,針對每個工程變更命令線路
有效率的產生許多估計的繞線路徑,並且使用了一個整數線性規劃
的模組去對這些估計的繞線路徑以最小化改變的遮罩層數量為目的
去做選擇。此外,為了能夠更加減少改變的遮罩層數量,我們應用了
一個最小成本最大流量演算法來更加改善整數線性規劃的繞線結果。
實驗結果顯示我們提出的工程變更命令繞線流程能夠有效的減少繞
現實改變的遮罩層數量,並且以可接受的線長以及孔數的增加數量
完成所有工程變更命令線路的繞線。
英文摘要 Engineering Change Order (ECO) routing, which is a complicated and difficult
task due to limited routing resource and increasing design rules, is requested in
later design stage for the purpose of delay and noise optimization. After ECO routing
procedure, layout may be changed since layers are used by the re-routed ECO
nets and cause the mask re-spin which leads to an extremely high cost. However,
there is no existing ECO router focuses on minimizing the number of used layers.
Therefore, this thesis presents a three-stage ECO routing flow which can simultaneously
route all ECO nets while considering routing layer minimization. Initially,
several routing paths for each ECO net are efficiently estimated and an Integer
Linear Programming (ILP) model is developed to simultaneously determine the
routing path of each ECO net to minimize the number of changed masks. Moreover,
a Minimum-Cost-Maximum-Flow (MCMF) algorithm is applied to further
reduce the number of changed masks. Experimental results demonstrate that our
proposed ECO routing flow can effectively reduce the number of changed masks
with acceptable increasing wirelength and via count.
論文目次 摘要iii
致謝v
Table of Contents vi
List of Tables viii
List of Figures ix
1 Introduction 1
1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Algorithm 8
2.1 Tile-based Routing Graph Construction . . . . . . . . . . . . . . . 8
2.2 ECO Routing with Mask Cost Minimization . . . . . . . . . . . . . 11
2.2.1 Routing Topology Generation . . . . . . . . . . . . . . . . . 11
2.2.2 Integer Linear Programming Based Routing Topology Selection
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Detailed Routing . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Network Flow-based ECO Routing Refinement . . . . . . . . . . . . 20
3 Experimental Results 26
4 Conclusion 29
Bibliography 30
參考文獻 [1] L. Behjat and A. Chiang. Fast integer linear programming based models
for VLSI global routing. In IEEE International Symposium on Circuits and
Systems, pages 6238–6243, 2005.
[2] L. Behjat, A. Chiang, L. Rakai, and J. Li. An effective congestion-based integer
programming model for VLSI global routing. In Electrical and Computer
Engineering, 2008. CCECE 2008. Canadian Conference on, pages 931–936,
2008.
[3] J. Cong, J. Fang, and K.-Y. Khoo. An implicit connection graph maze routing
algorithm for ECO routing. In IEEE/ACM International Conference on
Computer-Aided Design, pages 163–167, 1999.
[4] J. Cong, J. Fang, and K.-Y. Khoo. DUNE: A multi-layer gridless routing
system with wire planning. In IEEE/ACM International Conference on
Computer-Aided Design, page 12, 2000.
[5] S.-Y. Fang, T.-F. Chien, and Y.-W. Chang. Redundant-wires-aware ECO
timing and mask cost optimization. In IEEE/ACM International Conference
on Computer-Aided Design, pages 381–386, 2010.
[6] http://www-01.ibm.com/software/integration/optimization/.
[7] C. Inc. SoC Encounter. [Online]. Available: http://www.cadence.com/products/
di/soc_encounter.
[8] Y.-L. Li, C. H.-Y., and L. C.-T. NEMO: A new implicit-connection-craphbased
gridless router with multilayer planes and pseudo tile propagation.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and
Systems, 26(4):705–718, 2007.
[9] Y.-L. Li, J.-Y. Li, and W.-B. Chen. An Efficient Tile-Based ECO Router
Using Routing Graph Reduction and Enhanced Global Routing Flow. IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems,
26(2):345–358, 2007.
[10] Y.-H. Lin, Y.-J. Lo, J.-S. Tong, W.-H. Liu, and Y.-L. Li. Topology-aware
buffer insertion and GPU-based massively parallel rerouting for ECO timing
optimization. In ACM/IEEE Asia and South Pacific Design Automation
Conference, pages 437–442, 2012.
[11] C.-H. Liu, I.-C. Chen, and D. T. Lee. An efficient algorithm for multi-layer
obstacle-avoiding rectilinear Steiner tree construction. In ACM/IEEE Design
Automation Conference, pages 613–622, 2012.
[12] J. K. Ousterhout. Corner Stitching: A Data-Structuring Technique for VLSI
Layout Tools. IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, 3(1):87–100, 1984.
[13] Reports of the International Technology Roadmap for Semiconductors,. 2012,
http://www.itrs.net/.
[14] H. Shojaei, A. Davoodi, and P. Ramanathan. Confidentiality Preserving Integer
Programming for global routing. In Design Automation Conference
(DAC), 2012 49th ACM/EDAC/IEEE, pages 709–716, 2012.
[15] S. Q. Zheng, J. S. Lim, and S. S. Iyengar. Finding obstacle-avoiding shortest
paths using implicit connection graphs. IEEE Transactions on Computer-
Aided Design of Integrated Circuits and Systems, 15(1):103–110, 1996.
32
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2018-08-27起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2018-08-27起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw