Network flow modeling for escape routing on staggered pin arrays

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

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publication2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013
Pages193-198
Number of pages6
DOIs
StatePublished - May 20 2013
Event2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013 - Yokohama, Japan
Duration: Jan 22 2013Jan 25 2013

Publication series

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

Other

Other2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013
CountryJapan
CityYokohama
Period1/22/131/25/13

Fingerprint

Product design

ASJC Scopus subject areas

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

Cite this

Pei-Ci Wu, W., & Wong, M. D. F. (2013). Network flow modeling for escape routing on staggered pin arrays. In 2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013 (pp. 193-198). [6509595] (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1109/ASPDAC.2013.6509595

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 proceedingConference 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
Pei-Ci Wu W, Wong MDF. Network flow modeling for escape routing on staggered pin arrays. In 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). https://doi.org/10.1109/ASPDAC.2013.6509595
Pei-Ci Wu, Wu ; Wong, Martin D.F. / Network flow modeling for escape routing on staggered pin arrays. 2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013. 2013. pp. 193-198 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).
@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",
month = "5",
day = "20",
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",

}

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/5/20

Y1 - 2013/5/20

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

ER -