BoxRouter 2.0
Authors: Minsik Cho, Kun Yuan, Katrina Lu and David Z. Pan
|
|
|
|
|
|
Introduction
BoxRouter2.0 is a new global router for ultimate routability.
It is inspired by BoxRouter [1], but can perform multi-layer routing with 2D
global routing and layer assignment. The 2D global routing is equipped with
several ideas: such as robust negotiation-based A* search for routing
stability, and topology-aware wire ripup for flexibility and so on. After 2D
global routing, 2D-to-3D mapping is done by the layer assignment which is
powered by progressive via/blockage-aware integerlinear programming.
ISPD 2007 contest format
net[net NAME from the input] [net ID from the
input] [# of routes]
([x11],[y11],[z11])-([x12],[y12],z[12])
([x21],[y21],z[21])-([x22],[y22],z[22])
...
...
!
ISPD98 benchmarks & ISPD2007 Global Routing Contest benchmarks
Two modified ISPD98 benchmarks for study in [2]. ISPD98h benchmarks & ISPD98i benchmarks
A simple PERL script to evaluate the routing solution can be found here.
READ THIS LICENSE AGREEMENT CAREFULLY BEFORE USING
THIS PRODUCT. BY USING THIS PRODUCT YOU INDICATE YOUR ACCEPTANCE OF THE TERMS OF
THE FOLLOWING AGREEMENT. THESE TERMS APPLY TO YOU AND ANY SUBSEQUENT LICENSEE OF
THIS PRODUCT.
License Agreement for BoxRouter2.0
Copyright (c)
2007 by Minsik Cho, Kun Yuan, Katrina Lu, David Z. Pan
All rights reserved
ATTRIBUTION
ASSURANCE LICENSE (adapted from the original BSD license) Redistribution of the
any code, with or without modification, are permitted provided that the
conditions below are met. These conditions require a modest attribution to Minsik Cho, Kun Yuan, Katrina Lu and Dr. Daivd Z. Pan (the "Author").
THIS FREE SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR ANY CONTRIBUTOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, EFFECTS OF UNAUTHORIZED OR MALICIOUS NETWORK ACCESS; PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
IF YOU AGREE TO THE ABOVE AGREEMENT, PLEASE FILL IN FOLLOWING FORM. WE WILL DISTRIBUTE THE MOST UPDATED (Sep-12-2007) CODE TO YOU ONCE YOU GET OUR APPROVAL.
Available source: 32 bit & 64 bit Linux distribution (Debian)
[1] 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)
[2] 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.
Experimental results show that our global router has better routability with comparable wire-length than other routers on ISPD07 benchmark , and it can complete (no overflow) the widely used ISPD98 benchmark for the first time in the literature with the shortest wire-length. The number quoted below is based on ICCAD 2007 paper [2].
Results can be downloaded here: ISPD07 benchmark results LINK, ISPD98 benchmark results LINK, ISPD98h benchmark results LINK, ISPD98i benchmark results LINK,
FLUTE: Chris C. N. Chu http://home.eng.iastate.edu/~cnchu/flute.html
MaizeRouter: Michael Moffitt http://www.eecs.umich.edu/~mmoffitt/MaizeRouter/
FGR: Jarrod Roy and Igor L.Markov vlsicad.eecs.umich.edu/BK/FGR/
Labyrinth: Kastner, Bozorgzadeh, and Sarrafzadeh www.ece.ucsb.edu/~kastner/labyrinth/
GLPK: http://www.gnu.org/software/glpk/
MOSEK: http://www.mosek.com/
STLPORT: http://sourceforge.net/projects/stlport
last updated by Nov 14 2007