FastRoute

Min Pan, Yue Xu, Yanheng Zhang, Chris Chu

Contacts: yuexu@iastate.edu

Work in progress.
Last updated:  Mar. 10, 2010

Contents

I.  Introduction 
II.  Experimental Results 
III.  Source Code
IV. License
V. Literature
VI. Other Academic Routing Tools


I. Introduction

FastRoute is a global routing tool for VLSI back-end design. It  is based on sequential rip-up and re-route (RRR) and a lot of novel techniques. FastRoute 1.0 first uses FLUTE to construct congestion-driven Steiner trees, which will later undergo the edge shifting process to optimize tree structure to reduce congestion. It then uses pattern routing and maze routing with logistic function based cost function to solve the congestion problem. FastRoute 2.0 proposed monotonic routing and multi-source multi-sink maze routing techniques to enhance the capability to reduce congestion. FastRoute 3.0 introduced the virtual capacity technique to adaptively change the capacity associated with each global edge to divert wire usage from highly congested regions to less congested regions. FastRoute 4.0 proposed via-aware Steiner tree, 3-bend routing and a delicate layer assignment algorithm to effectively reduce via count while maintaining outstanding congestion reduction capability. FastRoute 4.1 simplifies the way the virtual capacities are updated and applies a single set of tuning parameters to all benchmark circuits.
II. Experimental Results

The results shown below are for FastRoute 4.1. We perform all experiments in single thread on a 2.8-GHz Intel machine with 32GB memory.

Benchmarks

TOF

WL(e5)

cpu(s)

adaptec1

0

53.8

193

adaptec2

0

52.2

51

adaptec3

0

131.2

183

adaptec4

0

121.3

61

adaptec5

0

155.8

407

newblue1

0

46.3

744

newblue2

0

75.2

40

newblue3

31276

108.4

1053

newblue4

136

130.5

3777

newblue5

0

230.9

565

newblue6

0

177.5

598

newblue7

54

353.4

51809

bigblue1

0

56.6

255

bigblue2

0

91.2

687

bigblue3

0

130.0

114

bigblue4

138

230.2

5650


III. Application for Source Code Download

The latest version of FastRoute available is FastRoute 4.1, which incorporates the newest techniques. It also keeps all the previous techniques in the package.

Please read the license agreement below and fill out the following agreement form. We will e-mail you the instruction for FastRoute downloads.


IV. 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 FastRoute

Copyright (c) 2008 by Min Pan, Yue Xu, Yanheng Zhang, Chris Chu
All rights reserved

ATTRIBUTION ASSURANCE LICENSE (adapted from the original BSD license) Redistribution and use in source and binary forms, with or without modification, are permitted provided that the conditions below are met. These conditions require a modest attribution to Min Pan, Yue Xu, Yanheng Zhang, Chris Chu (the "Authors").
  1. Redistributions of the source 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) Min Pan, Yue Xu, Yanheng Zhang, and Chris Chu ("AUTHORS"),
    (b) Iowa State University ("PROFESSIONAL IDENTIFICATION"), and
    (c) http://home.engineering.iastate.edu/~cnchu/ ("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.

V. Literature

[1] Chris Chu and Yiu-Chung Wong, FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design. In IEEE Transactions on Computer-Aided Design, vol. 27, no. 1, pages 70-83, January 2008.
[2] Min Pan and Chris Chu, FastRoute: A Step to Integrate Global Routing into Placement. IEEE/ACM International Conference on Computer-Aided Design, pages 464-471, 2006.
[3] Min Pan and Chris Chu, FastRoute 2.0: A High-quality and Efficient Global Router. Asian and South Pacific Design Automation Conference, pages 250-255, 2007.
[4] Yanheng Zhang, Yue Xu and Chris Chu, FastRoute 3.0: A Fast and High Quality Global Router Based on Virtual Capacity. IEEE/ACM International Conference on Computer-Aided Design, pages 344-349, 2008.
[5] Yue Xu, Yanheng Zhang and Chris Chu. "FastRoute 4.0: Global Router with Efficient Via Minimization. Asian and South Pacific Design Automation Conference, pages 576-581, 2009.


VI. Other Academic Routing Tools