考慮製造限制之繞線研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：22

、訪客IP：18.189.182.160

姓名

洪牧新(Mu-Hsin Hung) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

考慮製造限制之繞線研究
(Robust and Effective Routing with Manufacturing Constraints)

相關論文

★ 三維積體電路的微凸塊分配與晶粒間繞線之研究	★ 使用次序關係配置三維積體電路微凸塊
★ 考慮線長匹配的平行匯流排之逃脫繞線	★ 用於三維積體電路之溫度導向平面規劃的散熱型矽晶穿孔面積融合方法
★ 雙圖案微影技術下考慮原生衝突之電路軌道繞線	★ 考量障礙物間通道寬度限制及避免電子遷移效應的繞線樹建構之研究
★ 三維積體電路中同步降低熱點溫度與電源雜訊之研究	★ 使用延遲決策技術於類比電路之可繞度導向擺置方法
★ 提升聚焦離子束對訊號探測能力之細部繞線方法	★ 考慮障礙物閃避及電荷分享之鑽孔數量最小化跳線插入演算法
★ 模組化層級三維積體電路之矽晶穿孔規劃與線長最佳化	★ 降低不匹配效應之力導向電容擺置方法
★ 考慮繞線資源需求之標準元件擺置合法化	★ Simultaneous escape routing for mixed-pattern signals on staggered pin arrays
★ 面積與最大線長最佳化之類比積體電路佈局產生器	★ 含多重檢查機制之實體驗證自動化工具

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

繞線(routing)是實體設計(physical design)的最後一個步驟，關係著整個晶片的成功與否，因此是超大型積體電路(VLSI)設計領域中很重要的一環。繞線是針對一個已通過電路分群(circuit partitioning)、佈局規劃(floorplanning)與擺置(placement)等步驟的電路，進行所有連線(net)上信號節點(pin)的連接動作。
繞線完成度(routability)一直以來都是繞線問題中的重要議題。除此之外，隨著製程的進步，愈來愈多且複雜的製造限制需要在繞線時被考量，如障礙物(obstacle)、偏好方向(preferred direction)及變換方向區域(switch region)。因此，如何產生一個高繞線完成度的繞線結果且符合製造上的限制是實體設計的一大挑戰。
本研究提出了一個以連接圖形(connection graph)為基礎、強健且有效的繞線演算法。此演算法可處理偏好方向、變換方向區域與不同層擁有不同網格大小等製造限制。實驗結果顯示，本研究提出的演算法可以針對每一連線建立高品質(high-quality)的繞線樹(routing tree)，並且得到一個高繞線完成度(high-routability)的繞線結果。

摘要(英)

Routing is very important for VLSI designs since it is the last stage of the physical design and is related to the success of a chip. Routing is aimed to connect all pins of each net for a circuit, which has passed circuit partitioning, floorplanning, and placement.
Routability is always an important issue for routing. Besides, as technology advances, more and more complicated manufacturing constraints are needed to be considered in routing, such as obstacles, preferred directions, and switch regions. Therefore, it is a tremendous challenge to generate high-routability routing results with meeting modern manufacturing constraints.
In this thesis, we propose a robust and effective routing algorithm based on a connection graph method. The algorithm can handle preferred directions, switch regions, and different pitch values for different layers. Experimental results show that our algorithm can construct a high-quality routing tree for each net, and obtain a high-routability routing result.

關鍵字(中)

★ 實體設計
★ 繞線

關鍵字(英)

★ physical design
★ routing

論文目次

第 1 章簡介 1
1.1 實體設計 1
1.2 繞線問題 2
1.3 考慮實際製造上限制的繞線 4
1.4 問題描述 5
1.4.1 名詞解釋 6
1.4.2 合理的繞線 7
1.5 本研究的目的 8
第 2 章相關研究 9
2.1 繞線樹 10
2.2 以網格為基礎的繞線系統 15
第 3 章演算法 17
3.1 演算法流程圖 19
3.2 決定連線順序 20
3.3 連接圖形的產生 22
3.3.1 決定繞線範圍 24
3.3.2 產生中繼點 24
3.3.3 連接與訂定權重 25
3.3.4 以二維陣列建構多層架構 26
3.3.5 層與層之間投影點的方式 26
3.4 單組連線的方法 27
第 4 章實驗結果與分析 30
4.1 工作平台與測試檔說明 30
4.2 實驗結果與比較 30
4.3 實驗結果分析 34
4.4 繞線圖形化介面 34
第 5 章結論與未來方向 37
參考文獻 38

參考文獻

[1] S. M. Sait and H. Youssef, VLSI Physical Design Automation: Theory and Practice, McGraw-Hill, 1995.
[2] C.-W. Lin, S.-Y. Chen, C.-F. Li, Y.-W. Chang, and C.-L. Yang, “Obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 4, pp. 643—653, April 2008.
[3] I. H.-R. Jiang, S.-W. Lin and Y.-T. Yu, “Unification of obstacle-avoiding rectilinear Steiner tree construction,” in Proceedings of IEEE International SOC Conference, pp. 127—130, September 2008.
[4] J. Jaja and S. A. Wu, “On routing two-terminal nets in the presence of obstacles,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 8, no. 5, pp. 563—570, May 1989.
[5] J. Long, H. Zhou, and S. O. Memik, “An O(nlogn) edge-based algorithm for obstacle-avoiding rectilinear Steiner tree construction,” in Proceedings ACM International Symposium on Physical Design, pp. 126—133, April 2008.
[6] Y. Shi, P. Mesa, H. Yu, and L, He “Circuit simulation based obstacle-aware Steiner routing,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 385—388, July 2006.
[7] C. Chiang, M. Sarrafzadeh, and C. K. Wong, “An algorithm for exact rectilinear Steiner trees for switchbox with obstacles,” IEEE Transactions on circuits and systems. I: Fundamental theory and applications, vol. 39, no. 6, pp. 446—455, June 1992.
[8] Y. Hu, T. Jing, X. Hong, Z. Feng, X. Hu, and G. Yan, “An-OARSMan: Obstacle-avoiding routing tree construction with good length performance,” in Proceedings of ACM/IEEE Asia and South Pacific Design Automation Conference, pp. 7—12, January 2005.
[9] Z. Feng, Y. Hu, T. Jing, X. Hong, X. Hu, and G. Yan, “An O(n log n) algorithm for obstacle-avoiding routing tree construction in the λ-geometry plane,” in Proceedings of ACM International Symposium on Physical Design, pp. 48—55, April 2006.
[10] P.-C. Wu, J.-R. Gao, and T.-C. Wang, “A fast and stable algorithm for obstacle-avoiding rectilinear Steiner minimal tree construction,” in Proceedings of ACM/IEEE Asia and South Pacific Design Automation Conference, pp. 262—267, January 2007.
[11] M. C. Yildiz and P.H. Madden, “Preferred direction Steiner trees,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 21, no. 11, pp. 1368—1372, November 2002.
[12] Z. C. Shen, C. C. N. Chu, and Y.-M. Li, “Efficient rectilinear Steiner tree construction with rectilinear blockages,” in Proceedings of IEEE International Conference on Computer Design, pp. 38—44, November 2005.
[13] I. H.-R. Jiang and Y.-T. Yu, “Configurable Rectilinear Steiner Tree Construction for SoC and Nano Technologies,” in Proceeding of IEEE International Conference on Computer Design, October 2008.
[14] C.-W. Lin, S.-L. Huang, K.-C. Hsu, M.-X. Li, and Y.-W. Chang, “Multi-layer obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 11, pp. 2007—2016, November 2008.
[15] C.-H. Liu, Y.-H. Chou, S.-Y. Yuan, and S.-Y. Kuo, “Efficient multilayer routing based on obstacle-avoiding preferred direction Steiner tree,” in Proceedings of ACM International Symposium on Physical design, pp. 118—125, April 2008.
[16] Y.-W. Chang and S.-P. Lin, “MR: a new framework for multilevel full-chip routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 23, no. 5, pp. 793—800, May 2004.
[17] T.-Y. Ho, Y.-W. Chang, and S.-J. Chen, “Multilevel routing with antenna avoidance,” in Proceedings of ACM International Symposium on Physical Design, pp. 34—40, April 2004.
[18] T.-Y. Ho, Y.-W. Chang, S.-J. Chen, and D.-T. Lee, “Crosstalk- and performance-driven multilevel full-chip routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 24, no. 6, pp. 869—878, June 2005.
[19] H. Zhou, “Efficient Steiner tree construction based on spanning graphs,” in Proceedings of ACM International Symposium on Physical Design, pp. 152—157, April 2003.
[20] J. L. Ganley and J. P. Cohoon, “Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles,” in Proceedings of IEEE International Symposium On Circuits and Systems, vol. 1, pp. 113—116, May 1994.
[21] E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, 1: 269—271, 1959.
[22] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd Edition, MIT Press, 2001.
[23] C. Y. Lee, “An algorithm for path connections and its applications,” IRE Transactions on Electronic Computers, EC-10(3): 346—365, September 1961.
[24] Z. Xing and R. Kaog, “Shortest path search using tiles and piecewise linear cost propagation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 21, no. 2, pp. 145—158, February 2002.
[25] 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, vol. 15, no. 1, pp. 103—110, January 1996.
[26] Y. F. Wu, P. Widmayer, M. D. F. Schlag, and C. K. Wong, “Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacle,” IEEE Transactions on Computers, vol. C-36, no. 3, pp. 321—331, March 1987.
[27] http://www.gnuplot.info/

指導教授

陳泰蓁(Tai-Chen Chen)

審核日期

2009-7-21

推文