research-article

Global routing and track assignment for flip-chip designs

Authors:

Xuan ZengAuthors Info & Claims

DAC '10: Proceedings of the 47th Design Automation Conference

Pages 90 - 93

https://doi.org/10.1145/1837274.1837298

Published: 13 June 2010 Publication History

Get Access

Abstract

This paper describes a solution for global routing and track assignment of flip-chip I/O nets. Voronoi Diagram (VD) is used to partition the open routing space and the geometrical properties of VD graph are exploited to create global routing channels with capacity and congestion considerations. A network flow algorithm is used to achieve optimal global routing. The regularity of the flip-chip bump placement is observed and allows us to reduce the size of global routing channel graph by over 50% to speed up computation. A track assignment algorithm avoids crossing wires before completing the final route with a detailed router. Experiment results using actual silicon chip data demonstrate that our solution achieves good quality of results compared to an implementation used in a commercial tool.

References

[1]

J. W. Fang, I. J. Lin, Y. W. Chang, and J. H. Wang. A network-flow-based rdl routing algorithmz for flip-chip design. IEEE Trans. on CAD of Integrated Circuits and Systems, 26(8):1417--1429, 2007.

Digital Library

Google Scholar

[2]

J. W. Fang, C. H. Hsu, and Y. W. Chang. An integer-linear-programming-based routing algorithm for flip-chip designs. IEEE Trans. on CAD of Integrated Circuits and Systems, 28(1):98--110, 2009.

Digital Library

Google Scholar

[3]

J. W. Fang, 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 ACM/IEEE Design Automation Conference, pages 336--339, 2009.

Digital Library

Google Scholar

[4]

S. J. Fortune. A sweepline algorithm for voronoi diagrams. Algorithmica, 2:153--174, 1987.

Digital Library

Google Scholar

[5]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms and Applications. Prentice-Hall, 1993.

Digital Library

Google Scholar

[6]

Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry. Springer-Verlag, 2nd edition, 2000.

Google Scholar

Cited By

View all

Ji WYao HYin X(2023)A Fast Escape Router for Large-Scale Staggered-Pin-Array PCBs2023 International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA59274.2023.10218614(317-322)Online publication date: 8-May-2023
https://doi.org/10.1109/ISEDA59274.2023.10218614
Chiang CChuang FChang YCheng KYang H(2020)Unified Redistribution Layer Routing for 2.5D IC PackagesProceedings of the 25th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC47756.2020.9045359(331-337)Online publication date: 17-Jan-2020
https://dl.acm.org/doi/10.1109/ASP-DAC47756.2020.9045359
Lin TChi CChang YParameswaran S(2017)Redistribution layer routing for wafer-level integrated fan-out package-on-packagesProceedings of the 36th International Conference on Computer-Aided Design10.5555/3199700.3199775(561-568)Online publication date: 13-Nov-2017
https://dl.acm.org/doi/10.5555/3199700.3199775
Show More Cited By

Index Terms

Global routing and track assignment for flip-chip designs
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

IO connection assignment and RDL routing for flip-chip designs

Given a set of IO buffers and a set of bump balls with the capacity constraints between two adjacent bump balls, based on the construction of the Delaunary triangulation and a Manhattan Voronoi diagram, an O(n²) assignment algorithm is proposed to ...
An integer linear programming based routing algorithm for flip-chip design
DAC '07: Proceedings of the 44th annual Design Automation Conference

The flip-chip package provides a high chip-density solution to the demand for more I/O pads of VLSI designs. In this paper, we present the first routing algorithm in the literature for the pre-assignment flip-chip routing problem with a pre-defined ...
RDL pre-assignment routing for flip-chip designs
GLSVLSI '09: Proceedings of the 19th ACM Great Lakes symposium on VLSI

Based on the concept of net renumbering and recovery to simplify the complexity of the global and detailed routing, an efficient RDL pre-assignment routing algorithm is proposed to maximize the number of routed nets with the minimization of total ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '10: Proceedings of the 47th Design Automation Conference

June 2010

1036 pages

ISBN:9781450300025

DOI:10.1145/1837274

General Chair:
Sachin Sapatnekar
Univ. of Minnesota, Minneapolis, MN

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

DAC '10

Sponsor:

EDAC
SIGDA

DAC '10: The 47th Annual Design Automation Conference 2010

June 13 - 18, 2010

California, Anaheim

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
230
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ji WYao HYin X(2023)A Fast Escape Router for Large-Scale Staggered-Pin-Array PCBs2023 International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA59274.2023.10218614(317-322)Online publication date: 8-May-2023
https://doi.org/10.1109/ISEDA59274.2023.10218614
Chiang CChuang FChang YCheng KYang H(2020)Unified Redistribution Layer Routing for 2.5D IC PackagesProceedings of the 25th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC47756.2020.9045359(331-337)Online publication date: 17-Jan-2020
https://dl.acm.org/doi/10.1109/ASP-DAC47756.2020.9045359
Lin TChi CChang YParameswaran S(2017)Redistribution layer routing for wafer-level integrated fan-out package-on-packagesProceedings of the 36th International Conference on Computer-Aided Design10.5555/3199700.3199775(561-568)Online publication date: 13-Nov-2017
https://dl.acm.org/doi/10.5555/3199700.3199775
Lin TChi CChang Y(2017)Redistribution layer routing for wafer-level integrated fan-out package-on-packages2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1109/ICCAD.2017.8203827(561-568)Online publication date: Nov-2017
https://doi.org/10.1109/ICCAD.2017.8203827
Wu PMak WWang TZhuo CUnda KShi Y(2017)A routing framework for technology migration with bump encroachmentIntegration10.1016/j.vlsi.2017.01.00358(1-8)Online publication date: Jun-2017
https://doi.org/10.1016/j.vlsi.2017.01.003
Lei SMak W(2016)Optimizing Pin Assignment and Escape Routing for Blind-via-Based PCBsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.246045835:2(246-259)Online publication date: Feb-2016
https://doi.org/10.1109/TCAD.2015.2460458
Ho YLee HLee WChang YChang CLin IShen C(2014)Obstacle-Avoiding Free-Assignment Routing for Flip-Chip DesignsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2013.228527533:2(224-236)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1109/TCAD.2013.2285275
Ho YLee HChang Y(2013)Escape Routing for Staggered-Pin-Array PCBsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2013.225953932:9(1347-1356)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1109/TCAD.2013.2259539
Yuan-Kai Ho Xin-Wei Shih Yao-Wen Chang Chung-Kuan Cheng (2013)Layer minimization in escape routing for staggered-pin-array PCBs2013 18th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2013.6509594(187-192)Online publication date: Jan-2013
https://doi.org/10.1109/ASPDAC.2013.6509594
Lee PLee HHo YChang YChang CLin IShen CGroeneveld PSciuto DHassoun S(2012)Obstacle-avoiding free-assignment routing for flip-chip designsProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228558(1088-1093)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228558
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

IO connection assignment and RDL routing for flip-chip designs

An integer linear programming based routing algorithm for flip-chip design

RDL pre-assignment routing for flip-chip designs