Article

A global routing method for 2-layer ball grid array packages

Authors:

Yukiko Kubo,

Atsushi TakahashiAuthors Info & Claims

ISPD '05: Proceedings of the 2005 international symposium on Physical design

Pages 36 - 43

https://doi.org/10.1145/1055137.1055146

Published: 03 April 2005 Publication History

Get Access

Abstract

In current VLSI circuits, there can be hundreds of required I/O pins. BGA(Ball Grid Array) packaging is commonly used to realize the huge number of connections between VLSI and PCB. In this paper, we propose a global routing method for two-layer BGA packages. In our routing model, the global routing for each net is uniquely determined by a via assignment. Our global routing method begins with an initial feasible via assignment and incrementally improves the via assignment to minimize the total wire length and wire congestion. In each iteration, a via assignment is improved by exchanging adjacent two vias, rotating three vias, or by moving vias to their adjacent grids one by one. Our method is a greedy-based heuristic. The algorithm efficiently generates better global routes than initial routes with respect to wire congestion and total wire length.

References

[1]

M.-F. Yu and W. W.-M. Dai, "Single-layer fanout routing and routability analysis for ball grid arrays," In Proceedings of International Conference on Computer-Aided Design, pp.581--586, 1996.

Digital Library

Google Scholar

[2]

S, Shibata, K. Ukai, N. Togawa, M. Sato, and T. Ohtsuki, "A BGA Package Routing Algorithm on Sketch Layout System," The journal of Japan Institute for Interconnecting and Packaging Electronic Circuits, Vol. 12, No. 4, pp.241--246, 1997.

Crossref

Google Scholar

[3]

C.-C. Tsai, C.-M. Wang, and S.-J Chen, "NEWS: A Net-Even-Wiring System for the Routing on a Multilayer PGA Package," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.17, No. 2, pp.182--189, 1998.

Digital Library

Google Scholar

[4]

S.-S. Chen, J.-J. Chen, C.-C. Tsai, and S.-J. Chen, "An Even Wiring Approach to the Ball Grid Array Package Routing," In Proceedings of International Conference on Computer Design, pp.303--306, 1999.

Digital Library

Google Scholar

[5]

W. W.-M. Dai, R. Kong, J. Jue, and M. Sato, "Rubber band routing and dynamic data representation," In Proceedings of International Conference on Computer-Aided Design, pp.52--55, 1990.

Google Scholar

[6]

Yukiko Kubo and Atsushi Takahashi, "Global Routing and Via Assignment Method for 2-layer Ball Grid Array Packages," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2005 (to appear).

Digital Library

Google Scholar

[7]

Yukiko Kubo and Atsushi Takahashi, "Global Routing Method for 2-layer Ball Grid Array Packages," The 17th Workshop on Circuits and Systems in Karuizawa, pp.535--540, 2004 (in Japanese).

Google Scholar

Cited By

View all

Chen ZJi WPeng YChen DLiu MYao HChen YZhirnov VSasan ASavidis I(2021)Machine Learning Based Acceleration Method for Ordered Escape RoutingProceedings of the 2021 Great Lakes Symposium on VLSI10.1145/3453688.3461483(365-370)Online publication date: 22-Jun-2021
https://dl.acm.org/doi/10.1145/3453688.3461483
Yan J(2019)Single-Layer GNR Routing for Minimization of Bending DelayIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.287816438:11(2099-2112)Online publication date: Nov-2019
https://doi.org/10.1109/TCAD.2018.2878164
(2015)Single-layer obstacle-aware routing for substrate interconnectionsIntegration, the VLSI Journal10.1016/j.vlsi.2015.04.00151:C(1-9)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.vlsi.2015.04.001
Show More Cited By

Index Terms

A global routing method for 2-layer ball grid array packages
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Recommendations

Global routing by iterative improvements for two-layer ball grid array packages

In current very large scale integration (VLSI) circuits, there can be hundreds of required I/O pins. Ball grid array (BGA) packaging is commonly used to realize the huge number of connections between VLSI chips and printed circuit boards (PCBs). In this ...
Congestion-Constrained Layer Assignment for Via Minimization in Global Routing

In this paper, we study the problem of layer assignment for via minimization, which arises during multilayer global routing. In addressing this problem, we take the total overflow and the maximum overflow as the congestion constraints from a given one-...
A Via Assignment and Global Routing Method for 2-Layer Ball Grid Array Packages

In this paper, we propose a global routing method for 2-layer BGA packages. In our routing model, the global routing for each net is uniquely determined by a via assignment of each net. Our global routing method starts from an initial monotonic via ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISPD '05: Proceedings of the 2005 international symposium on Physical design

April 2005

258 pages

ISBN:1595930213

DOI:10.1145/1055137

General Chair:
Patrick Groeneveld
Eindhoven University
,
Program Chair:
Lou Scheffer
Cadence

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: 03 April 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISPD05

Sponsor:

ISPD05: International Symposium on Physical Design 2005

April 3 - 6, 2005

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 62 of 172 submissions, 36%

Upcoming Conference

ISPD '25

Sponsor:
sigda

International Symposium on Physical Design

March 16 - 19, 2025

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
514
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)2

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chen ZJi WPeng YChen DLiu MYao HChen YZhirnov VSasan ASavidis I(2021)Machine Learning Based Acceleration Method for Ordered Escape RoutingProceedings of the 2021 Great Lakes Symposium on VLSI10.1145/3453688.3461483(365-370)Online publication date: 22-Jun-2021
https://dl.acm.org/doi/10.1145/3453688.3461483
Yan J(2019)Single-Layer GNR Routing for Minimization of Bending DelayIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.287816438:11(2099-2112)Online publication date: Nov-2019
https://doi.org/10.1109/TCAD.2018.2878164
(2015)Single-layer obstacle-aware routing for substrate interconnectionsIntegration, the VLSI Journal10.1016/j.vlsi.2015.04.00151:C(1-9)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.vlsi.2015.04.001
Yan JTseng YYen C(2014)Feasible region assignment of routing nets in single-layer routing2014 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2014.6865148(393-396)Online publication date: Jun-2014
https://doi.org/10.1109/ISCAS.2014.6865148
Lee RChen H(2013)A study of row-based area-array I/O design planning in concurrent chip-package design flowACM Transactions on Design Automation of Electronic Systems10.1145/2442087.244210118:2(1-19)Online publication date: 11-Apr-2013
https://dl.acm.org/doi/10.1145/2442087.2442101
Lee RHsu HChen H(2013)Board- and Chip-Aware Package Wire PlanningIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2012.221228821:8(1377-1387)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1109/TVLSI.2012.2212288
Yan TWong M(2012)Correctly Model the Diagonal Capacity in Escape RoutingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2011.216925831:2(285-293)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1109/TCAD.2011.2169258
Tai-Hung Li Wan-Chun Chen Xian-Ting Cai Tai-Chen Chen (2012)Escape routing of differential pairs considering length matching17th Asia and South Pacific Design Automation Conference10.1109/ASPDAC.2012.6164934(139-144)Online publication date: Jan-2012
https://doi.org/10.1109/ASPDAC.2012.6164934
Yan TWu PMa QWong MScheffer LPhillips JHu A(2010)On the escape routing of differential pairsProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133559(614-620)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133559
Yan TWong MScheffer LPhillips JHu A(2010)Recent research development in PCB layoutProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133514(398-403)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133514
Show More Cited By

View Options

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

Global routing by iterative improvements for two-layer ball grid array packages

Congestion-Constrained Layer Assignment for Via Minimization in Global Routing

A Via Assignment and Global Routing Method for 2-Layer Ball Grid Array Packages