Network flow modeling for escape routing on staggered pin arrays

Wu Pei-Ci Wu; Martin D.F. Wong

doi:10.1109/ASPDAC.2013.6509595

Network flow modeling for escape routing on staggered pin arrays

Wu Pei-Ci Wu, Martin D.F. Wong

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Recently staggered pin arrays are introduced for modern designs with high pin density. Although some studies have been done on escape routing for hexagonal arrays, the hexagonal array is only a special kind of staggered pin array. There exist other kinds of staggered pin arrays in current industrial designs, and the existing works cannot be extended to solve them. In this paper, we study the escape routing problem on staggered pin arrays. Network flow models are proposed to correctly model the capacity constraints of staggered pin arrays. Our models are guaranteed to find an escape routing satisfying the capacity constraints if there exists one. The correctness of these models lead to an optimal algorithm.

Original language	English (US)
Title of host publication	2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013
Pages	193-198
Number of pages	6
DOIs	https://doi.org/10.1109/ASPDAC.2013.6509595
State	Published - 2013
Event	2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013 - Yokohama, Japan Duration: Jan 22 2013 → Jan 25 2013

Publication series

Name	Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Other

Other	2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013
Country/Territory	Japan
City	Yokohama
Period	1/22/13 → 1/25/13

ASJC Scopus subject areas

Computer Science Applications
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering

Online availability

10.1109/ASPDAC.2013.6509595

Library availability

Discover UIUC Full Text

Cite this

Network flow modeling for escape routing on staggered pin arrays. / Pei-Ci Wu, Wu; Wong, Martin D.F.
2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013. 2013. p. 193-198 6509595 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Pei-Ci Wu, W & Wong, MDF 2013, Network flow modeling for escape routing on staggered pin arrays. in 2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013., 6509595, Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, pp. 193-198, 2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013, Yokohama, Japan, 1/22/13. https://doi.org/10.1109/ASPDAC.2013.6509595

@inproceedings{5f237292f0314f7fa72c794013682352,

title = "Network flow modeling for escape routing on staggered pin arrays",

abstract = "Recently staggered pin arrays are introduced for modern designs with high pin density. Although some studies have been done on escape routing for hexagonal arrays, the hexagonal array is only a special kind of staggered pin array. There exist other kinds of staggered pin arrays in current industrial designs, and the existing works cannot be extended to solve them. In this paper, we study the escape routing problem on staggered pin arrays. Network flow models are proposed to correctly model the capacity constraints of staggered pin arrays. Our models are guaranteed to find an escape routing satisfying the capacity constraints if there exists one. The correctness of these models lead to an optimal algorithm.",

author = "{Pei-Ci Wu}, Wu and Wong, {Martin D.F.}",

year = "2013",

doi = "10.1109/ASPDAC.2013.6509595",

language = "English (US)",

isbn = "9781467330299",

series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",

pages = "193--198",

booktitle = "2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013",

note = "2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013 ; Conference date: 22-01-2013 Through 25-01-2013",

}

TY - GEN

T1 - Network flow modeling for escape routing on staggered pin arrays

AU - Pei-Ci Wu, Wu

AU - Wong, Martin D.F.

PY - 2013

Y1 - 2013

N2 - Recently staggered pin arrays are introduced for modern designs with high pin density. Although some studies have been done on escape routing for hexagonal arrays, the hexagonal array is only a special kind of staggered pin array. There exist other kinds of staggered pin arrays in current industrial designs, and the existing works cannot be extended to solve them. In this paper, we study the escape routing problem on staggered pin arrays. Network flow models are proposed to correctly model the capacity constraints of staggered pin arrays. Our models are guaranteed to find an escape routing satisfying the capacity constraints if there exists one. The correctness of these models lead to an optimal algorithm.

AB - Recently staggered pin arrays are introduced for modern designs with high pin density. Although some studies have been done on escape routing for hexagonal arrays, the hexagonal array is only a special kind of staggered pin array. There exist other kinds of staggered pin arrays in current industrial designs, and the existing works cannot be extended to solve them. In this paper, we study the escape routing problem on staggered pin arrays. Network flow models are proposed to correctly model the capacity constraints of staggered pin arrays. Our models are guaranteed to find an escape routing satisfying the capacity constraints if there exists one. The correctness of these models lead to an optimal algorithm.

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

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

U2 - 10.1109/ASPDAC.2013.6509595

DO - 10.1109/ASPDAC.2013.6509595

M3 - Conference contribution

AN - SCOPUS:84877788692

SN - 9781467330299

T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

SP - 193

EP - 198

BT - 2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013

T2 - 2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013

Y2 - 22 January 2013 through 25 January 2013

ER -

Network flow modeling for escape routing on staggered pin arrays

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this