Dogleg channel routing with parallel mixed integer linear programming solvers

Tseng, I-Lun, Kao, Yung-Wei, Chang, Cheng-Yuan and Postula, Adam (2011). Dogleg channel routing with parallel mixed integer linear programming solvers. In: Hamid R. Arabnia, Proceedings of International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA). The WORLDCOMP'11 - International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), Las Vegas, Nevada, USA, (533-539). July 18-21 2011.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
Author Tseng, I-Lun
Kao, Yung-Wei
Chang, Cheng-Yuan
Postula, Adam
Title of paper Dogleg channel routing with parallel mixed integer linear programming solvers
Conference name The WORLDCOMP'11 - International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA)
Conference location Las Vegas, Nevada, USA
Conference dates July 18-21 2011
Proceedings title Proceedings of International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA)
Place of Publication USA
Publisher Worldcomp
Publication Year 2011
Sub-type Fully published paper
Editor Hamid R. Arabnia
Volume Vol. 1-2
Start page 533
End page 539
Total pages 7
Collection year 2012
Language eng
Abstract/Summary Channel routing is a type of problems arising in the detailed routing phase of VLSI physical design automation as well as in the design of printed circuit boards (PCBs). It has been known that channel routing problems can be formulated as constraint programming (CP) problems and thus CP solvers can be used to find solutions. In this article, we present a mixed integer linear programming (MILP) formulation to gridded dogleg channel routing problems. As a result, parallel MILP solvers, which have the ability to exploit the computational power of multi-core processors, can be used to find solutions. Experimental results show that high degrees of scalability can be achieved. Owing to the properties of MILP problems, it is possible to further shorten the execution time if a computer containing more processor cores is available.
Keyword Channel routing
VLSI physical design automation
Mixed integer linear programming
Parallel computing
Q-Index Code E1
Q-Index Status Confirmed Code
Institutional Status UQ

 
Versions
Version Filter Type
Citation counts: Google Scholar Search Google Scholar
Created: Thu, 20 Oct 2011, 22:52:46 EST by Dr Adam Postula on behalf of School of Information Technol and Elec Engineering