FastRoute
Contents
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.
BSD 3-Clause License
Copyright (c) 2018, Iowa State University
All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:
* Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.
* Neither the name of the copyright holder nor the names of its
contributors may be used to endorse or promote products derived from this
software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 COPYRIGHT HOLDER OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
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.
[6] Min Pan, Yue Xu, Yanheng Zhang and Chris
Chu. "FastRoute: An Efficient and
High-Quality Global Router. VLSI Design, Article ID 608362, 2012.
VI. Other Academic Routing Tools
