BoxRouter 2.0   

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


Introduction
Formats&Benchmarks
Code Release
Awards&Publications
Performance&Results
 Link

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.

 adaptec1 
adaptec2
 adaptec3
adaptec4
adaptec5
newblue1
newblue2

Formats & Benchmarks

          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.


Code Release

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").

  1. Redistributions of any code, with or without modification (the "Code"), must be accompanied by any documentation and, each time the resulting executable program or a program dependent thereon is launched, a prominent display (e.g., splash screen or banner text) of the Author's attribution information, which includes:
    (a) Minsik Cho, Kun Yuan, Katrina Lu and Dr. David Z. Pan ("AUTHOR"),
    (b) The University of Texas at Austin ("PROFESSIONAL IDENTIFICATION"), and
    (c) http://www.cerc.utexas.edu/utda/ ("URL").
  2. Use is limited to academic research groups only. Users who are interested in industry or commercial purposes must notify Author and request separate license agreement.
  3. Neither the name nor any trademark of the Author may be used to endorse or promote products derived from this software without specific prior written permission.
  4. Users are entirely responsible, to the exclusion of the Author and any other persons, for compliance with (a) regulations set by owners or administrators of employed equipment, (b) licensing terms of any other software, and (c) local, national, and international regulations regarding use, including those regarding import, export, and use of encryption software.

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.

Name:
Orgnization:
E-mail:
Intended Usage and Comment:
I agree to the licensing terms above.

Available source: 32 bit & 64 bit Linux distribution (Debian)                                                                        


Awards & Publications

 2nd Place in 3D Routing Contest

 3rd Place in 2D Routing Contest

  [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.


Performance & Results

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,


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