TY - JOUR
T1 - BSG-route
T2 - A length-constrained routing scheme for general planar topology
AU - Yan, Tan
AU - Wong, Martin D. F.
N1 - Funding Information:
Manuscript received January 17, 2009; revised June 4, 2009. Current version published October 21, 2009. This work was supported in part by the National Science Foundation under Grant CCF-0701821 and in part by a Grant from the Fujitsu Laboratories. An earlier version of this paper appeared in the Proceedings of the International Conference on Computer-Aided Design 2008 [1]. This paper was recommended by Associate Editor C. J. Alpert.
PY - 2009/11
Y1 - 2009/11
N2 - Length-constrained routing is a very important issue for printed circuit board (PCB) routing. Previous length-constrained routers all have assumptions on the routing topology, whereas practical designs may be free of any topological constraint. In this paper, we propose a routing scheme that deals with general topology. Unlike previous works, our approach does not impose any restriction on the routing topology. Moreover, our routing scheme is gridless. Its performance does not depend on the routing grid size of the input while the routers in the papers of Ozdal and Wong and Kubo do. This is a big advantage because modern PCB routing configurations usually imply huge routing grids. The novelty of this work is that we view the length-constrained routing problem as an area assignment problem and use a placement structure, which is the bounded-sliceline grid, to help transform the area assignment problem into a mathematical programming problem. We then use an iterative approach to solve this mathematical programming problem. Experimental results show that our routing scheme can handle practical designs that previous routers cannot handle. For designs that they could handle, our router runs much faster. For example, in one of our data, we obtain the result in 88 s while the Lagrangian relaxation based router by Ozdal and Wong takes more than one day.
AB - Length-constrained routing is a very important issue for printed circuit board (PCB) routing. Previous length-constrained routers all have assumptions on the routing topology, whereas practical designs may be free of any topological constraint. In this paper, we propose a routing scheme that deals with general topology. Unlike previous works, our approach does not impose any restriction on the routing topology. Moreover, our routing scheme is gridless. Its performance does not depend on the routing grid size of the input while the routers in the papers of Ozdal and Wong and Kubo do. This is a big advantage because modern PCB routing configurations usually imply huge routing grids. The novelty of this work is that we view the length-constrained routing problem as an area assignment problem and use a placement structure, which is the bounded-sliceline grid, to help transform the area assignment problem into a mathematical programming problem. We then use an iterative approach to solve this mathematical programming problem. Experimental results show that our routing scheme can handle practical designs that previous routers cannot handle. For designs that they could handle, our router runs much faster. For example, in one of our data, we obtain the result in 88 s while the Lagrangian relaxation based router by Ozdal and Wong takes more than one day.
KW - Algorithms
KW - Linear programming (LP)
KW - Printed circuit layout
KW - Routing
UR - http://www.scopus.com/inward/record.url?scp=70350583052&partnerID=8YFLogxK
U2 - 10.1109/TCAD.2009.2030352
DO - 10.1109/TCAD.2009.2030352
M3 - Journal article
AN - SCOPUS:70350583052
SN - 0278-0070
VL - 28
SP - 1679
EP - 1690
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 11
ER -