BoxRouter: A New Global Router based on Box Expansion and Progressive ILP

Minsik Cho, David Z. Pan

Work in progress.
Last updated: Dec. 16, 2006

Contents

I.  Introduction 
II.  Code Release
III. Output Format (Revised for ISPD07)
IV. Literature
V. License
I. Introduction

 BoxRouter is a new global router powered by the concept of box expansion and progressive integer linear programming (ILP). It spreads out the congestion from the most congested region to less congested regions by incrementally performing BoxRouting. It also provides smooth control over radeoff between wirelength and routability without Ripup&Reroute. Details are in [1].

 Our experimental results show that BoxRouter significantly outperforms the state-of-the-art published global routers, e.g., 91% better routability than Labyrinth (with 14.3% shorter wirelength and 3.3x speedup), 79% better routability than Chi Dispersion Router implemented in Fengshui (with similar wirelength and 2x speedup), 4.2% less wirelength and 16x speedup than multicommodity flow-based global router (with similar routability). Given the fundamental importance of routing, such dramatic improvement shall sparkle renewed interests in routing which plays a key role in nanometer design and manufacturing closure.

II. Code Release

The current BoxRouter is available only as a form of a binary. Note that the BoxRouter is using Flute algorithm to build steiner trees, and a part of original/modified data file for flute is provided here together. Also, GNU Linear Programming Kit (glpk-4.8) is used as ILP solver.  This package contains the following files: br.tar.gz

br.x                        -- The BoxRouter binary. It is tested on Debian GNU/Linux and RedHat Enterprise Linux WS on Intel Xeon platform.
my_port.bin           -- The replacement of PORT9.dat in Flute which is essentially a look-up table.
POWV9.dat           -- The lookup-table of optimal POWVs up to degree 9 in Flute.
chk.pl                     -- A PERL script to verify/analyze the global routing result from the BoxRouter
run_k_15.pl           -- A PERL script to regenerate the results in [1]
run_k_b.pl             -- A PERL script to regenerate the results in [1]
ibm_k_15.tar.gz    -- Routing results from run_k_15.pl
ibm_k_b.tar.gz      -- Routing results from run_k_b.pl
ibm.tar.gz              -- ISPD98 IBM benchmark in Labyrinth format for gloabl routing. Also available in Labyrinth

III. Output Format

This output format is slightly different from the original BoxRouter format, but more intuitive and suitable for ISPD07 global routing contest, as the original one has some redundant and unnecessary information as well. A simple PERL script to evaluate the routing solution can be found here.

IV. Literature

[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

กก
V. License

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 BoxRouter

Copyright (c) 2006, 2007 by Minsik Cho, David Z. Pan
All rights reserved

ATTRIBUTION ASSURANCE LICENSE (adapted from the original BSD license) Redistribution and use in binary forms, with or without modification, are permitted provided that the conditions below are met. These conditions require a modest attribution to Minsik Cho and Dr. Daivd Z. Pan (the "Author").
  1. Redistributions of the 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 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. Users who intend to use the Code for commercial purposes will notify Author prior to such commercial use.
  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 (1) regulations set by owners or administrators of employed equipment, (2) licensing terms of any other software, and (3) 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.
กก