An ILP-based automatic bus planner for dense PCBs

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Modern PCBs have to be routed manually since no EDA tools can successfully route these complex boards. An auto-router for PCBs would improve design productivity tremendously since each board takes about 2 months to route manually. This paper focuses on a major step in PCB routing called bus planning. In the bus planning problem, we need to simultaneously solve the bus decomposition, escape routing, layer assignment and global bus routing. This problem was partially addressed by Kong et al. in [3] where they only focused on the layer assignment and global bus routing, assuming bus decomposition and escape routing are given. In this paper, we present an ILP-based solution to the entire bus planning problem. We apply our bus planner to an industrial PCB (with over 7000 nets and 12 signal layers) which was previously successfully routed manually, and compare with a state-of-the-art industrial internal tool where the layer assignment and global bus routing are based on the algorithm in [3]. Our bus planner successfully routed 97.4% of all the nets. This is a huge improvement over the industrial tool which could only achieve 84.7% routing completion for this board.

Original languageEnglish (US)
Title of host publication2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013
Pages181-186
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

Inductive logic programming (ILP)
Polychlorinated biphenyls
Planning
Decomposition
Routers
Productivity

ASJC Scopus subject areas

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

Cite this

Pei-Ci Wu, W., Ma, Q., & Wong, M. D. F. (2013). An ILP-based automatic bus planner for dense PCBs. In 2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013 (pp. 181-186). [6509593] (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1109/ASPDAC.2013.6509593

An ILP-based automatic bus planner for dense PCBs. / Pei-Ci Wu, Wu; Ma, Qiang; Wong, Martin D.F.

2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013. 2013. p. 181-186 6509593 (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, Ma, Q & Wong, MDF 2013, An ILP-based automatic bus planner for dense PCBs. in 2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013., 6509593, Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, pp. 181-186, 2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013, Yokohama, Japan, 1/22/13. https://doi.org/10.1109/ASPDAC.2013.6509593
Pei-Ci Wu W, Ma Q, Wong MDF. An ILP-based automatic bus planner for dense PCBs. In 2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013. 2013. p. 181-186. 6509593. (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1109/ASPDAC.2013.6509593
Pei-Ci Wu, Wu ; Ma, Qiang ; Wong, Martin D.F. / An ILP-based automatic bus planner for dense PCBs. 2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013. 2013. pp. 181-186 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).
@inproceedings{a06cd4b67ad44cb4afa4a525bf065ec4,
title = "An ILP-based automatic bus planner for dense PCBs",
abstract = "Modern PCBs have to be routed manually since no EDA tools can successfully route these complex boards. An auto-router for PCBs would improve design productivity tremendously since each board takes about 2 months to route manually. This paper focuses on a major step in PCB routing called bus planning. In the bus planning problem, we need to simultaneously solve the bus decomposition, escape routing, layer assignment and global bus routing. This problem was partially addressed by Kong et al. in [3] where they only focused on the layer assignment and global bus routing, assuming bus decomposition and escape routing are given. In this paper, we present an ILP-based solution to the entire bus planning problem. We apply our bus planner to an industrial PCB (with over 7000 nets and 12 signal layers) which was previously successfully routed manually, and compare with a state-of-the-art industrial internal tool where the layer assignment and global bus routing are based on the algorithm in [3]. Our bus planner successfully routed 97.4{\%} of all the nets. This is a huge improvement over the industrial tool which could only achieve 84.7{\%} routing completion for this board.",
author = "{Pei-Ci Wu}, Wu and Qiang Ma and Wong, {Martin D.F.}",
year = "2013",
month = "5",
day = "20",
doi = "10.1109/ASPDAC.2013.6509593",
language = "English (US)",
isbn = "9781467330299",
series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",
pages = "181--186",
booktitle = "2013 18th Asia and South Pacific Design Automation Conference, ASP-DAC 2013",

}

TY - GEN

T1 - An ILP-based automatic bus planner for dense PCBs

AU - Pei-Ci Wu, Wu

AU - Ma, Qiang

AU - Wong, Martin D.F.

PY - 2013/5/20

Y1 - 2013/5/20

N2 - Modern PCBs have to be routed manually since no EDA tools can successfully route these complex boards. An auto-router for PCBs would improve design productivity tremendously since each board takes about 2 months to route manually. This paper focuses on a major step in PCB routing called bus planning. In the bus planning problem, we need to simultaneously solve the bus decomposition, escape routing, layer assignment and global bus routing. This problem was partially addressed by Kong et al. in [3] where they only focused on the layer assignment and global bus routing, assuming bus decomposition and escape routing are given. In this paper, we present an ILP-based solution to the entire bus planning problem. We apply our bus planner to an industrial PCB (with over 7000 nets and 12 signal layers) which was previously successfully routed manually, and compare with a state-of-the-art industrial internal tool where the layer assignment and global bus routing are based on the algorithm in [3]. Our bus planner successfully routed 97.4% of all the nets. This is a huge improvement over the industrial tool which could only achieve 84.7% routing completion for this board.

AB - Modern PCBs have to be routed manually since no EDA tools can successfully route these complex boards. An auto-router for PCBs would improve design productivity tremendously since each board takes about 2 months to route manually. This paper focuses on a major step in PCB routing called bus planning. In the bus planning problem, we need to simultaneously solve the bus decomposition, escape routing, layer assignment and global bus routing. This problem was partially addressed by Kong et al. in [3] where they only focused on the layer assignment and global bus routing, assuming bus decomposition and escape routing are given. In this paper, we present an ILP-based solution to the entire bus planning problem. We apply our bus planner to an industrial PCB (with over 7000 nets and 12 signal layers) which was previously successfully routed manually, and compare with a state-of-the-art industrial internal tool where the layer assignment and global bus routing are based on the algorithm in [3]. Our bus planner successfully routed 97.4% of all the nets. This is a huge improvement over the industrial tool which could only achieve 84.7% routing completion for this board.

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

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

U2 - 10.1109/ASPDAC.2013.6509593

DO - 10.1109/ASPDAC.2013.6509593

M3 - Conference contribution

AN - SCOPUS:84877748022

SN - 9781467330299

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

SP - 181

EP - 186

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

ER -