NTUgr

2nd Place, ISPD 2008 Global Routing Contest

National Taiwan University
Authors: Huang-Yu Chen, Chin-Hsiung Hsu, and Prof. Yao-Wen Chang
Contact: arious@eda.ee.ntu.edu.tw
Last update: 2009-01-03

 

Introduction
.
.

NTUgr is a high-quality global router. It mainly contains two parts: initial routing and iterative forbidden-region rip-up/rerouting (IFR). The IFR features two new techniques of (1) multiple forbidden regions expansion and (2) look-ahead historical cost increment. At the ISPD 2008 Global Routing Contest, NTUgr generated the high-quality solutions in terms of both overflow and runtime for 16 benchmarks among all participating global routers and won the 2nd place.

 

ISPD'08 Global Routing Contest Benchmarks
.
.
The ISPD'08 benchmark suit.

 



Experienmental Results
.
.
We tested NTUgr on ISPD'08 benchmarks in a 2.0-GHz Intel-64 machine with 16GB of memory, and the latest experimental results are given below.
ISPD'08 Benchmarks NTUgr Output Data
Circuit #Nets Total Overflow Wirelength Runtime (s)
adaptec1 176715 0 5601012 362 Download
adaptec2 207972 0 5358910 91 Download
adaptec3 368494 0 13413749 351 Download
adaptec4 401060 0 12405440 129 Download
adaptec5 548073 0 16051339 1087 Download
bigblue1 196885 0 5909656 944 Download
bigblue2 428968 0 9425565 17718 Download
bigblue3 665629 0 13456081 447 Download
bigblue4 1133535 188 23955778 26235 Download
newblue1 270713 6 4852883 67850 Download
newblue2 373790 0 7666642 64 Download
newblue3 442005 31106 17148888 49799 Download
newblue4 531292 142 13546764 72415 Download
newblue5 891920 0 24114870 2200 Download
newblue6 835267 0 18546983 1167 Download
newblue7 1647410 310 37039828 85127 Download

 

Related Publications
.
.
  1. H.-Y. Chen, C.-H. Hsu, and Y.-W. Chang, "High-Performance Global Routing with Fast Overflow Reduction," (.pdf), in Proc. of ACM/IEEE Asia and South Pacific Design Automation Conference (ASP-DAC), Yokohama, Japan, pp. 582-587, January 2009.
  2. C.-H. Hsu, H.-Y. Chen, and Y.-W. Chang, "Multi-layer Global Routing Considering Via and Wire Capacities," (.pdf), in Proc. of IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Jose, CA, pp. 350-355, November 2008.

 

Binary Distribution and Source Codes Download
.
.
Please fill out the following agreement form.

Agreement Form
Name
Email
Possible purposes of using NTUgr

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 NTUgr

Copyright (c) 2008 by Huang-Yu Chen, Chin-Hsiung Hsu, and Yao-Wen Chang ("Authors")
http://eda.ee.ntu.edu.tw/~yellowfish/ntugr/ ("URL")

All right reserved

Redistribution and use in source and binary form, with or without modification, are permitted provided that the following conditions are met:
  1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
  2. 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.
  3. Neither the names nor any trademark of the Authors may be used to endorse or promote products derived from this software without specific prior written permission.
  4. Use is limited to academic research groups only. Users who are interested in industry or commercial purposes must notify Authors and request separate license agreement.
  5. Redistributions of the Code in executable form, or a program dependent upon the Code, must show at launch a prominent display (e.g., splash screen or banner text) of the copyright information, including Authors' attribution, shown above.

License Terms

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.

I agree to the license terms above
Get NTUgr binary (64-bit, 4x CPUs, LINUX workstation):
Get NTUgr source codes (please compile by at least 4x CPUs, LINUX workstation):

 

Other Academic Global Routing Tools on the Web
.
.