![]() |
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數:13 、訪客IP:18.119.108.202
姓名 管大宇(Ta-Yu Kuan) 查詢紙本館藏 畢業系所 電機工程學系 論文名稱 使用次序關係配置三維積體電路微凸塊
(Micro-Bump Assignment Algorithm for 3D ICs Using Order Relation)相關論文 檔案 [Endnote RIS 格式]
[Bibtex 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
[下載]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。
摘要(中) 現今積體電路的發展使得電路設計日益複雜,製程技術上的進步,在提供晶片面積縮小的同時也讓製程成本往上提高。三維積體電路(3D IC)在空間上提供晶片往縱向維度發展的可能性,提升了晶片的單位密度,以至於我們可以用成本較低或是成熟度較高的製程來完成相同的設計。三維積體電路的晶片堆疊(die-stacking)技術也使得不同的設計可存在於同一塊晶片上,對於異質整合(heterogeneous integration)的應用提供了一個很好的平台。
對於三維積體電路來說,微凸塊(micro-bump)的位置決定了重新分配層(redistributed layer, RDL)繞線結果的好壞,我們的研究針對微凸塊提出了一個最佳的配置方法。對於任意兩組訊號的微凸塊必定存在一個最佳的相對位置使上重新分配層(upper RDL)與下重新分配層(lower RDL)都不會有繞線交越(wire crossing)的問題,我們提出使用次序關係(order relation)的配置演算法可以把這種微凸塊的次序關係找出來,並且組合所有訊號的微凸塊的次序關係,得到一個擁有全部微凸塊相對位置的最佳解。以此相對位置對微凸塊做配置的結果可以使訊號彼此的最短路徑交疊的情形降到最低,減少了上與下重新分配層繞線的迂迴線路(detour wire)的數量,最後可以產生一個在全域繞線(global routing)上能擁有最小整體線長(total wirelength)的微凸塊配置結果。
摘要(英) In modern very large scale integration (VLSI) circuit, the circuit design has become extremely complication. The advances on manufacturing definitely reduce the chip size but simultaneously arises the cost on fabrication. The three dimensional integrated circuit (3D IC) has the potentiality on extending the chip to vertical dimension. The 3D IC certainly arises the chip density per unit, thus we can use the lower cost or well matured fabrication to the same design. The die-stacking technology of 3D IC also makes it possible that different designs can exist on the same chip concurrently and supplies an ideal platform for the application of heterogeneous integration.
Regarding to 3D IC, the micro-bump location seriously affects the routing results on redistributed layer (RDL). In our research, we propose a best assignment method for micro-bump considering the RDL-routing results. Any two micro bumps certainly exists a set of relative location that avoids wire crossing problem in both upper and lower RDLs. Our assignment algorithm uses order relation to find out this kind of micro-bump orders, and it composes the micro-bump relative orders of all signals to generate a best solution which includes whole micro-bump relative locations. By using order relation, the crossing problem of straight paths will be minimized so that the detour wires in upper and lower RDLs will be decreased. Finally, our algorithm can obtain an assignment result which minimizes total wirelength in global routing.
關鍵字(中) ★ 實體設計
★ 三維積體電路
★ 電子設計自動化
★ 微凸塊
★ 重新分配層
★ 次序關係
★ 全域繞線關鍵字(英) ★ three dimensional integrated circuit (3D IC)
★ order relation
★ electronic design automation (EDA)
★ physical design
★ global routing
★ micro bump
★ redistributed layer (RDL)論文目次 摘要........................................................................................................................... I
Abstract.....................................................................................................................II
致謝........................................................................................................................ III
Table of Contents .................................................................................................... IV
List of Figures ......................................................................................................... VI
List of Tables........................................................................................................... IX
Chapter 1 Introduction ....................................................................................... - 1 -
1.1 3D IC Technology.......................................................................................... - 1 -
1.1.1Die Stacking........................................................................................................ - 2 -
1.1.2 Inter-Die Connection ........................................................................................... - 2 -
1.1.3 Interface Connection............................................................................................ - 3 -
1.2 Problem Formulation..................................................................................... - 4 -
1.3 Our Contribution ........................................................................................... - 6 -
Chapter 2 Related Work ..................................................................................... - 8 -
2.1 Redistributed Layer ....................................................................................... - 8 -
2.2 ILP-Based Micro-Bump Assignment ............................................................. - 9 -
2.3 Topological Sort .......................................................................................... - 11 -
2.4 Transitive-Closure Algorithm....................................................................... - 13 -
2.5 Comparison Among Our and Related Works................................................ - 15 -
Chapter 3 Algorithm ........................................................................................ - 17 -
3.1 Observations and Ideas ................................................................................ - 17 -
3.1.1Micro-Bump Location ........................................................................................- 17 -
3.1.2Routing Angle in Redistributed Layers ...............................................................- 18 -
3.1.3 45-degree Coordinate Mapping...........................................................................- 20 -
3.1.4Order Duplication...............................................................................................- 21 -
3.2 Algorithm Overview.................................................................................... - 22 -
3.3 Order Determination.................................................................................... - 23 -
3.3.1 3-Net Picking .....................................................................................................- 24 -
3.3.2Order Duplication...............................................................................................- 27 -
3.3.3 3-Net Relation Table Construction......................................................................- 29 -
3.3.4 Subgraph Merging ..............................................................................................- 31 -
3.4 Micro-Bump Shifting................................................................................... - 35 -
3.5 ILP Routing ................................................................................................. - 38 -
Chapter 4 Experimental Results ....................................................................... - 39 -
Chapter 5 Conclusions and Future Works ......................................................... - 44 -
Reference ............................................................................................................ - 45 -
參考文獻 [1] J.-W. Fang and Y.-W. Chang, “Area-I/O Flip-Chip Routing for Chip-Package co-design,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 518–522, 2008.
[2] J.-W. Fang, K.-H. Ho, and Y.-W. Chang, “Routing for Chip-Package-Board Co-Design Considering Differential Pairs,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 512–517, 2008.
[3] J.-W. Fang, M. D. F. Wong, and Y.-W. Chang, “Flip-Chip Routing with Unified Area-I/O Pad Assignments for Package-Board Co-Design,” in Proceedings of IEEE/ACM Design Automation Conference, pp. 336–339, 2009.
[4] P.-W. Lee, C.-W. Lin, Y.-W. Chang, C.-F. Shen, and W.-C. Tseng, “An Efficient Pre-Assignment Routing Algorithm for Flip-Chip Designs,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 239–244, 2009.
[5] Y. Kubo and A. Takahashi, “Global Routing by Iterative Improvements for Two-Layer Ball Grid Array Packages,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 4, pp. 725–733, April 2006.
[6] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithm, 3rd edition, The MIT Press, Cambridge, Massachusetts, 2009.
[7] R. Weerasekera, D. Pamunuwa, L.-R. Zheng, and H. Tenhunen, “Two-Dimensional and Three-Dimensional Integrationof Heterogeneous Electronic Systems Under Cost, Performance, and Technological Constraints,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 8, pp. 1237–1250, August 2009.
[8] M. Koyanagi, T. Fukushima, and T. Tanaka, “Three-Dimensional Integration Technology and Integrated Systems,” in Proceedings of IEEE/ACM Asia and South Pacific Design Automation Conference, pp. 409–415, 2009.
[9] N. Miyakawa, “A 3D Prototyping Chip Based on a Wafer-Level Stacking Technology,” in Proceedings of IEEE/ACM Asia and South Pacific Design Automation Conference, pp. 416–420, 2009.
[10] D. Kung and R. Puri, “CAD Challenges for 3D ICs,” in Proceedings of IEEE/ACM Asia and South Pacific Design Automation Conference, pp. 421–422, 2009.
[11] C. Chiang and S. Sinha, “The Road to 3D EDA Tool Readiness,” in Proceedings of IEEE/ACM Asia and South Pacific Design Automation Conference, pp. 429–436, 2009.
[12] 張佳仁, “三微積體電路的微凸塊分配與晶粒間繞線之研究,” 國立中央大學電機工程研究所碩士論文, June 2009.
指導教授 陳泰蓁(Tai-Chen Chen) 審核日期 2010-7-24 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
myshare