DOI: 10.5176/978-981-08-7656-2 A-46
Authors: Che-I Lee, Huan-Wen Chen, and I-Lun Tseng
Abstract: Switchbox routing is a type of problems arising in the
detailed routing phase of VLSI physical design automation. A
switchbox is a rectangular area and its boundary contains
terminals; each terminal belongs to a specific net. A switchbox
router can connect all the terminals belonging to the same net
and the router must complete the connection of each net. It has
been proven that a switchbox routing problem containing
multiple terminals and multiple nets belongs to the class of NPcomplete.
In this article, we present a constraint programming
(CP) formulation and a mixed integer linear programming
(MILP) formulation to switchbox routing problems. Therefore,
CP solvers and MILP solvers can be used to find solutions.
Experimental results show that more than 23X speed-up can be
achieved by using a parallel MILP solver with 16 threads. The
execution time can be further reduced when a computer
containing more processor cores is available.
Keywords: Obstacle-avoiding switchbox router; VLSI physical
design automation; constraint programming; parallel mixed integer
linear programming
Updating...