BoxRouter 2.0

Welcome to BoxRouter2.0, a new global router for ultimate routability.

This is 64 bit version.

BoxRouter2.0 Website

Tutorial

1. What do you have in this folder and What do you need?

You have:

a) BoxRouter2.0 Source Code:

BBox.h Boundary.h BoxRouter.h Design.h Grid.h GRouter.h ILPSolver.h MazeHeap.h Net.h Object.h Param.h Pin.h Point.h Segment.h Util.h Wire.h
BBox.cpp Boundary.cpp BoxRouter.cpp Design.cpp Grid.cpp GRouter.cpp ILPSolver.cpp MazeHeap.cpp Net.cpp Object.cpp Param.cpp Pin.cpp Point.cpp Segment.cpp Util.cpp Wire.cpp dmp2res.cpp res2dmp.cpp
makefile
fix_mps.pl

You need:

b) Software packages (free for academic research) used in BoxRouter2.0

I: FLUTE:
II: glpk ILP solver:
III: STLport:

Histrory Release
IV: MOSEK:

History Release

c) Complied executable file

res2dmp.x dmp2res.x br_ispd07.x

To help you test, we also put one example here:

ibm01.par, the BoxRouter2.0 configuration file.

bench/ibm01.modified.txt -> input file, one of ISPD98 benchmarks.
bench/ibm01.modified.stt -> the Steiner tree generated by FLUTE.
bench/ibm01.modified.txt.log-> log file.
bench/ibm01.modified.res -> output result.
bench/ibm01.modified.dmp -> dump file.
bench/ibm01.modified.res.map -> the final congestion map.

2. How to compile the code ?

Please first make sure you setup those software packages correctly.

a) Download FLUTE package and set it up in your BoxRouter2.0 folder.

For your convenience, Flute files which we are using currently can be also downloaded from http://www.cerc.utexas.edu/utda/download/FLUTE.tar.gz. You can download it and extract into your BoxRouter2.0 folder.
b) Download glpk package and set it up in your BoxRouter2.0 folder.

For your convenience, glpk-4.10 which we are using currently can be also downloaded from http://www.cerc.utexas.edu/utda/download/glpk-4.10.tar.gz. You can download it and extract into your BoxRouter2.0 folder.
c) Download STLPORT package and set it up in your BoxRouter2.0 folder.
d) Download MOSEK package and set it up in your BoxRouter2.0 folder.

Then, please compile the code as:

a) make

Generate the BoxRouter2.0 executable file br_ispd07.x
b) make dmp2res:

Generate the executable file dmp2res.x
c) make res2dmp:

Generate the executable file res2dmp.x

3. How to run the BoxRouter2.0?

./br_ispd07.x configuration_file

Here we provide one example ibm01.par for configuration_file.

4. What are the meanings of those parameters in our configuration file?

a) INPUT_FILE input_filename

Specify the input circuit in ISPD 2007 Routing Contest format.
b) TREE_FILE tree_filename

Input Steiner tree. If tree_filename is not found,BoxRouter2.0 will call FLUTE to make Steiner trees for you. The format of the Steiner tree file will be discussed later.
c) OUTPUT_FILE output_filename

Specify the routing result output file and the format can be found in our BoxRouter2.0 website.
d) DUMP_FILE dump_filename

The dump file is used to store intermediate routing solution in binary format.

If the file dump_filename exists before you run the BoxRouter2.0, the BoxRouter2.0 will just read the dump file to get intermediate solution and start from there , skipping certain steps.

If the file dump_filename doesn't exist, the BoxRouter2.0 will do the whole routing from the first beginning and write several intermediate results into dump files.
e) MULTI_LAYER a

a = 0 disables multi layer option. a = 1 enables multi layer option.
f) PREROUTING a

a = 0 will NOT perform the prerouting stage. a = 1 will perform the prerouting stage.
g) BOXROUTING a

a = 0 will NOT perform the boxrouting stage. a = 1 will perform the boxrouting stage.
h) BOXROUTING_STEP n

n is the number of variables which can be affordably solved by GLPK.
i) BOXROUTING_ILP n

n is used to specify the algorithm which is used in boxrouting stage.

n = 0;use mazerouting. n = 1:use ILP solver and set ILP objective is max. n = 2:use ILP solver and set ILP objective is min. n = 3:use pattern routing. n = 4:use hybrid ILP mode. n = 5:set ILP objective max and use round up to achieve the solution.
j) ILP_SOLVER n

n = 0:GLPK is used. n = 1;MOSEK is used.
k) REROUTING a

a = 0 will NOT perform the rerouting stage. a = 1 will perform the rerouting stage.
l) REROUTING_COUNT n

n is the number of most rerouting functions.
m) REROUTING_REPEAT n

n is the number of rerouting for reducing wirelength.
n) REROUTING_STEP n

n is used to control the number of wires to be ripup on congestion edges.
o) REROUTING_PUSH p
p) REROUTING_STUCK s

The above two parameters are used together to control the routing cost function. e.g. Cost = a*(b.^(PUST_VALUE))+1; a&b are constants. p is the starting PUSH_VALUE; s is predefined STUCK_VALUE;

During the rerouting stage, for every new PUSH_VALUE, we set STUCK_VALUE 0. If we use this PUSH VALUE and during following rerouting, we can not improve our result for continuous STUCK_VLAUE times, we will increase p by 1.
q) MAZEROUTING_MARGIN n

n is used to control mazerouting to avoid too much searching space.
r) RELAYERING a

a = 0 will NOT perform BoxRouter2.0 layer assignment algorithm. a = 1 will perform BoxRouter2.0 layer assignment algorithm.

You can always comment out some line in the configuration file by putting # in the beginning of the line as

#MULTI_LAYER

The BoxRouter2.0 will assign default value accordingly.

5. How does the TREE FILE format looks like?

You can specify your own tree topology and write it into file as following format. The BoxRouter2.0 perform the routing algorithm based on you file.

net[name from the input] [net ID from the input] [# of wires]
([x11],[y11])-(x[12],y[12])
([x21],[y21])-(x[22],y[22])
....
....
!

for example

 net10122 3 6 // a net with name"net10122" has netID 3 and the Steiner tree has 6 wires
 17 61 - 18 61 // the 1st wire is from (17,61 to 18.61)
 23 61 - 23 62
 25 62 - 23 62
 18 61 - 21 61
 21 61 - 21 62
 23 62 - 21 62
 !

Authors

Minsik Cho, Kun Yuan, Katrina Lu and David Z. Pan

LICENSE

Please see LICENSE for information.

Awards & Publications

2nd Place in 3D Routing Contest
3rd Place in 2D Routing Contest
Minsik Cho and David Z. Pan , "BoxRouter: A New Global Router Based on Box Expansion and Progressive ILP", Proc. Design Automation Conference (DAC), July, 2006. (Nominated for Best Paper Award, 12 out of 865 submissions)
Minsik Cho, Katrina Lu, Kun Yuan, David Z. Pan, "BoxRouter 2.0: Architecture and Implementation of a Hybrid and Robust Global Router", Proc. IEEE/ACM Int'l Conference on Computer-Aided Design (ICCAD), November, 2007.

Disclaimer

BoxRouter2.0 was originally released in 2007. Many interfaces, for example MOSEK, may have been changed. Please use the software only for reference.

utda-group / boxrouter Goto Github PK

boxrouter's Introduction