Flip-chip routing with unified area-I/O pad assignments for package-board co-design

Jia-Wei Fang; Martin D. F. Wong; Yao-Wen Chang

doi:10.1145/1629911.1630002

Flip-chip routing with unified area-I/O pad assignments for package-board co-design

Jia-Wei Fang, Martin D. F. Wong, Yao-Wen Chang

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

41 Citations (Scopus)

Abstract

In this paper, we present a novel flip-chip routing algorithm for package-board co-design. Unlike the previous works that can consider only either free- or pre-assignment routing, our router is the first work in the literature that can handle both the free-and pre-assignment routing. Based on the computational geometry techniques (e.g., the Delaunay triangulation and the Voronoi diagram), the router applies a unified network-flow formulation to perform congestion estimation for the pre-assignment routing. According to the congestion map, the network-flow formulation can also consider the free-assignment nets during the routing for the pre-assignment ones. Then, the router modifies the network-flow formulation to optimally assign and route the free-assignment nets, considering the routed pre-assignment nets. With the package and board co-design flow, we can achieve 100% routing completion. Experimental results based on industry designs demonstrate the high-quality of our algorithm.

Original language	English
Title of host publication	46th ACM/IEEE Design Automation Conference - Proceedings 2009
Publisher	Association for Computing Machinery (ACM)
Pages	336-339
Number of pages	4
ISBN (Print)	9781605584973
DOIs	https://doi.org/10.1145/1629911.1630002
Publication status	Published - 29 Jul 2009
Event	46th ACM/IEEE Design Automation Conference, DAC 2009 - San Francisco, United States Duration: 26 Jul 2009 → 31 Jul 2009 https://www.dac.com/About/Conference-Archive/46th-DAC-2009 (Conference website) https://www.dac.com/portals/0/documents/archive/2009/46DAC_Final_Prgm.pdf (Conference programme ) https://dl.acm.org/doi/proceedings/10.1145/1629911 (Conference proceedings) https://ieeexplore.ieee.org/xpl/conhome/5209519/proceeding

Publication series

Name	ACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)	0738-100X

Conference

Conference	46th ACM/IEEE Design Automation Conference, DAC 2009
Country/Territory	United States
City	San Francisco
Period	26/07/09 → 31/07/09
Internet address	https://www.dac.com/About/Conference-Archive/46th-DAC-2009 (Conference website) https://www.dac.com/portals/0/documents/archive/2009/46DAC_Final_Prgm.pdf (Conference programme ) https://dl.acm.org/doi/proceedings/10.1145/1629911 (Conference proceedings) https://ieeexplore.ieee.org/xpl/conhome/5209519/proceeding

Scopus Subject Areas

Computer Science Applications
Control and Systems Engineering
Electrical and Electronic Engineering
Modelling and Simulation

User-Defined Keywords

Detailed routing
Global routing
Physical design

Access to Document

10.1145/1629911.1630002

Cite this

@inproceedings{18e15480f19440b18222e32849b44a43,

title = "Flip-chip routing with unified area-I/O pad assignments for package-board co-design",

abstract = "In this paper, we present a novel flip-chip routing algorithm for package-board co-design. Unlike the previous works that can consider only either free- or pre-assignment routing, our router is the first work in the literature that can handle both the free-and pre-assignment routing. Based on the computational geometry techniques (e.g., the Delaunay triangulation and the Voronoi diagram), the router applies a unified network-flow formulation to perform congestion estimation for the pre-assignment routing. According to the congestion map, the network-flow formulation can also consider the free-assignment nets during the routing for the pre-assignment ones. Then, the router modifies the network-flow formulation to optimally assign and route the free-assignment nets, considering the routed pre-assignment nets. With the package and board co-design flow, we can achieve 100% routing completion. Experimental results based on industry designs demonstrate the high-quality of our algorithm.",

keywords = "Detailed routing, Global routing, Physical design",

author = "Jia-Wei Fang and Wong, {Martin D. F.} and Yao-Wen Chang",

note = "This work was partially supported by ITRT, SpringSoft, Synopsys, TSMC, National Science Foundation of the US under Grant No{\textquoteright}s. CCF-0701821, and National Science Council of Taiwan under Grant No{\textquoteright}s. NSC 97-2221-E-002-237-MY3, NSC 96-2628-E-002-248-MY3, NSC 96-2628-E-002-249-MY3, and NSC 096-2917-I-002-120.; 46th ACM/IEEE Design Automation Conference, DAC 2009 ; Conference date: 26-07-2009 Through 31-07-2009",

year = "2009",

month = jul,

day = "29",

doi = "10.1145/1629911.1630002",

language = "English",

isbn = "9781605584973",

series = "ACM/IEEE Design Automation Conference - Proceedings",

publisher = "Association for Computing Machinery (ACM)",

pages = "336--339",

booktitle = "46th ACM/IEEE Design Automation Conference - Proceedings 2009",

address = "United States",

url = "https://www.dac.com/About/Conference-Archive/46th-DAC-2009, https://www.dac.com/portals/0/documents/archive/2009/46DAC_Final_Prgm.pdf, https://dl.acm.org/doi/proceedings/10.1145/1629911, https://ieeexplore.ieee.org/xpl/conhome/5209519/proceeding",

}

Fang, J-W, Wong, MDF & Chang, Y-W 2009, Flip-chip routing with unified area-I/O pad assignments for package-board co-design. in 46th ACM/IEEE Design Automation Conference - Proceedings 2009. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 336-339, 46th ACM/IEEE Design Automation Conference, DAC 2009, San Francisco, California, United States, 26/07/09. https://doi.org/10.1145/1629911.1630002

Flip-chip routing with unified area-I/O pad assignments for package-board co-design. / Fang, Jia-Wei; Wong, Martin D. F.; Chang, Yao-Wen.
46th ACM/IEEE Design Automation Conference - Proceedings 2009. Association for Computing Machinery (ACM), 2009. p. 336-339 (ACM/IEEE Design Automation Conference - Proceedings).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Flip-chip routing with unified area-I/O pad assignments for package-board co-design

AU - Fang, Jia-Wei

AU - Wong, Martin D. F.

AU - Chang, Yao-Wen

N1 - This work was partially supported by ITRT, SpringSoft, Synopsys, TSMC, National Science Foundation of the US under Grant No’s. CCF-0701821, and National Science Council of Taiwan under Grant No’s. NSC 97-2221-E-002-237-MY3, NSC 96-2628-E-002-248-MY3, NSC 96-2628-E-002-249-MY3, and NSC 096-2917-I-002-120.

PY - 2009/7/29

Y1 - 2009/7/29

N2 - In this paper, we present a novel flip-chip routing algorithm for package-board co-design. Unlike the previous works that can consider only either free- or pre-assignment routing, our router is the first work in the literature that can handle both the free-and pre-assignment routing. Based on the computational geometry techniques (e.g., the Delaunay triangulation and the Voronoi diagram), the router applies a unified network-flow formulation to perform congestion estimation for the pre-assignment routing. According to the congestion map, the network-flow formulation can also consider the free-assignment nets during the routing for the pre-assignment ones. Then, the router modifies the network-flow formulation to optimally assign and route the free-assignment nets, considering the routed pre-assignment nets. With the package and board co-design flow, we can achieve 100% routing completion. Experimental results based on industry designs demonstrate the high-quality of our algorithm.

AB - In this paper, we present a novel flip-chip routing algorithm for package-board co-design. Unlike the previous works that can consider only either free- or pre-assignment routing, our router is the first work in the literature that can handle both the free-and pre-assignment routing. Based on the computational geometry techniques (e.g., the Delaunay triangulation and the Voronoi diagram), the router applies a unified network-flow formulation to perform congestion estimation for the pre-assignment routing. According to the congestion map, the network-flow formulation can also consider the free-assignment nets during the routing for the pre-assignment ones. Then, the router modifies the network-flow formulation to optimally assign and route the free-assignment nets, considering the routed pre-assignment nets. With the package and board co-design flow, we can achieve 100% routing completion. Experimental results based on industry designs demonstrate the high-quality of our algorithm.

KW - Detailed routing

KW - Global routing

KW - Physical design

UR - https://dl.acm.org/doi/10.1145/1629911.1630002

UR - https://ieeexplore.ieee.org/document/5227130

UR - http://www.scopus.com/inward/record.url?scp=70350733796&partnerID=8YFLogxK

U2 - 10.1145/1629911.1630002

DO - 10.1145/1629911.1630002

M3 - Conference proceeding

AN - SCOPUS:70350733796

SN - 9781605584973

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 336

EP - 339

BT - 46th ACM/IEEE Design Automation Conference - Proceedings 2009

PB - Association for Computing Machinery (ACM)

T2 - 46th ACM/IEEE Design Automation Conference, DAC 2009

Y2 - 26 July 2009 through 31 July 2009

ER -

Flip-chip routing with unified area-I/O pad assignments for package-board co-design

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this