Title page for 975201020


[Back to Results | New Search]

Student Number 975201020
Author Ta-Yu Kuan(管大宇)
Author's Email Address 975201020@cc.ncu.edu.tw
Statistics This thesis had been viewed 581 times. Download 362 times.
Department Electrical Engineering
Year 2009
Semester 2
Degree Master
Type of Document Master's Thesis
Language English
Title Micro-Bump Assignment Algorithm for 3D ICs Using Order Relation
Date of Defense 2010-07-09
Page Count 60
Keyword
  • electronic design automation (EDA)
  • global routing
  • micro bump
  • order relation
  • physical design
  • redistributed layer (RDL)
  • three dimensional integrated circuit (3D IC)
  • Abstract 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.
    Table of Content 摘要........................................................................................................................... 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 -
    Reference [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.
    Advisor
  • Tai-Chen Chen(陳泰蓁)
  • Files
  • 975201020.pdf
  • approve in 2 years
    Date of Submission 2010-07-24

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have dissertation-related questions, please contact with the NCU library extension service section.
    Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.