NCTU-GR 2.0

Authors: Wen-Hao Liu, Ke-Ren Dai, Wei-Chun Kao, Yih-Lang Li

Download The 64bit Binary of NCTU-GR 2.0 (lasted updated: 2013/07/01)

Download ISPD08 Global Routing Benchmarks

Download ISPD11, DAC12, and ICCAD12 Placement Benchmarks and Placement Solutions

Contact: NCTUGR {at} gmail {dot} com

Update History

2013/05/15: NCTU-GR 2.0 is available for download.

2013/07/01: Add a parameter that users can control the maximum runtime of the R&R stage in NCTU-GR 2.0. (Note: when this utility is used, the routing result may become nondeterministic.)

Introduction

NCTU-GR 2.0 is a unified placement and routing tool that includes the following four utilities, in which the regular mode of NCTU-GR 2.0 is selected to be the evaluation tool in DAC12 and ICCAD12 placement contests.

Regular mode

: A powerful global router to efficiently remove overflows and find shorter routing wirelength

Fast mode

: A fast light global router that can be used to predict routing congestion in the early stages before routing

Routability optimizer

: A post-placer that reads a placement solution and then do re-placement to improve routability

Format Converter

: Translate ISPD11 and DAC12 placement solutions from the academic format to LEF/DEF format

 

Users can use following commands to perform the utilities of NCTU-GR 2.0.

command

Input and Output Files of NCTU-GR 2.0:

1.      <ISPD’08 format benchmark> is the global routing benchmark released by ISPD 2008 global routing contest.

2.      <Circuit.aux> is the placement benchmark released by ISPD 2011, DAC 2012 and ICCAD 2012 placement contests.

3.      <Placement_solution.pl> is the placement solution for the placement benchmark released by the placement contests.

4.      [GR result] is the output file of regular mode and fast mode, which is a multi-layer global routing result.

5.      [PL result] is the output file of routability optimizer, which is a legalized placement result with better routability.

6.      <Design.rule> is a parameter file used in the format converter to set the basic design rules in the LEF/DEF files.

7.      <Parameter.set> is a parameter file used in the regular mode, fast mode and routability optimizer to control the solution quality and runtime. Please read README file in the downloaded package of NCTU-GR 2.0 so that the user can learn how to tune the parameters to control the behavior of NCTU-GR 2.0.

 

If the user unzipped the downloaded package of NCTU-GR 2.0, the user can see the following files, in which NCTUgr is the execution binary; please put NCTUgr, PORT.dat, POST9.dat and POWV9.dat in the same directory. The directory [Parameter_Files] contains several parameter setting files that are recommended setting for NCTU-GR 2.0 with different objectives. Of course, users can modify the parameters in these setting files or create their own parameter setting files.

=FILE_LIST=

NCTUgr

PORT9.dat

POST9.dat

POWV9.dat

README

[Parameter_Files]

RegularDefault.set       //Recommended setting to perform the regular mode

RegularHighQuality.set   //Regular mode with this setting file would get better routing result but spend longer runtime

RegularDacContest.set   //DAC12 placement contest adopts the regular mode with this setting to evaluate placement solutions

RegularIccadContest.set  //ICCAD12 placement contest adopts the regular mode with this setting to evaluate placement solutions

FastDefault.set          //Recommended setting to perform the fast mode

PlaceForGR.set          //Recommended setting to perform routability optimizer to optimize global routability

PlaceForDR.set          //Recommended setting to perform routability optimizer to optimize detailed routability

[DesignRule_Files]             

design22nm.rule

design28nm.rule          //Converting academic placement benchmarks into LEF/DEF format under 28nm basic design rules. 

design45nm.rule

design90nm.rule

 

 

Experiments

The following experiments were performed on a quad-core 3.0 GHz Intel Xeon-based server with E5450 CPU and 32GB memory. Placement benchmarks and the placement solutions used in the following experiments are downloaded from ISPD11 placement contest website. Note that, the regular mode and the fast mode of NCTU-GR 2.0 both consist of the 2D routing stage and layer assignment stage, so the columns of “Routing time” and “LA time” in the following tables denote the runtime of the 2D routing stage and layer assignment stage, respectively.

 

Regular Mode

The routing results in Table 1 are obtained by the following command.

./NCTUgr  REGULAR  <Circuit.aux>  <Placement_solution.pl>  <Parameter.set>  [GR result]

In this experiment, <Parameter.set> is RegularDefault.set that is included in the downloaded package of NCTU-GR 2.0.

Because the overflow reduction of sb2 and sb4 is almost stuck after iteration 20th, we specially set Maze_Routing_Iteration=20 in RegularDefault.set for sb2 and sb4 to reduce runtime.

Placement
Benchmark

Placement
solution

Table 1: Global Routing Result Obtained by the Regular Mode of NCTU-GR 2.0 with RegularDefault.set

Maximum Overflow

Total Overflow

WL

VIA

WL+VIA

Iteration

IO Time (sec)

Routing Time (sec)

LA Time (sec)

Download GR Results

Sb1

SimPLR

0

0

10137408

4597616

14735024

6

11.7

61.38

17.58

-

Sb2

Ripple

8

1728

24965490

6413918

31379408

20

17.29

2955.01

53.44

-

Sb4

Ripple

4

304

7467683

3308937

10776620

20

8.55

474.09

16.66

-

Sb5

Ripple

0

0

12898722

4650756

17549478

22

11.38

483.44

21.93

-

Sb10

RADIANT

0

0

18789609

6304110

25093719

19

15.8

3265.38

29.15

-

Sb12

SimPLR

0

0

13537448

8913075

22450523

13

18.81

436.24

33.07

-

Sb15

Ripple

0

0

11680491

6143517

17824008

24

15.26

576.2

26.86

-

Sb18

mPL11

0

0

5978268

3582687

9560955

12

7.15

127.69

13.61

-

 

The routing results in Table 2 are obtained by the following command.

./NCTUgr  REGULAR  <Circuit.aux>  <Placement_solution.pl>  <Parameter.set>  [GR result]

In this experiment, <Parameter.set> is RegularHighQuality.set that is included in the downloaded package of NCTU-GR 2.0.

Because the overflow reduction of sb2 and sb4 is almost stuck after iteration 120th, we specially set Maze_Routing_Iteration=120 in RegularHighQuality.set for sb2 and sb4 to reduce runtime.

Placement
Benchmark

Placement
solution

Table 2: Global Routing Result Obtained by the Regular Mode of NCTU-GR 2.0 with RegularHighQuality.set

Maximum Overflow

Total Overflow

WL

VIA

WL+VIA

Iteration

IO Time (sec)

Routing Time (sec)

LA Time (sec)

Download GR Results

Sb1

SimPLR

0

0

10115818

4520749

14636567

18

11.79

248.77

93.87

-

Sb2

Ripple

8

1728

24428876

5973247

30402123

120

16.3

19047.5

285.9

-

Sb4

Ripple

4

278

7352568

3106370

10458938

120

7.95

2643.96

95.38

-

Sb5

Ripple

0

0

12724564

4447930

17172494

255

11.1

5308.47

94.64

-

Sb10

RADIANT

0

0

18479742

5884191

24363933

134

15.16

13308.44

154.9

-

Sb12

SimPLR

0

0

13285037

8256102

21541139

42

17.93

1096.26

179.07

-

Sb15

Ripple

0

0

11545682

5759838

17305520

141

14.25

3017.98

127.28

-

Sb18

mPL11

0

0

5910977

3327816

9238793

23

6.99

399.13

77.96

-

 

By comparing Table 1 and Table2, we can find that the routing results in Tabl2 have shorter wirelength and fewer vias than that in Table 1. However, the regular mode spends longer routing time and LA time to get the routing results in Table 2 compared that in Table 1, because the parameter settings in RegularDefault.set and RegularHighQuality.set are different. To learn more details about how to tune parameters, the user can compare the content in RegularDefault.set and RegularHighQuality.set.

 

 

Fast Mode

The routing results in Table 3 are obtained by the following command.

./NCTUgr  FAST  <Circuit.aux>  <Placement_solution.pl>  <Parameter.set>  [GR result]

In this experiment, <Parameter.set> is FastDefault.set that is included in the downloaded package of NCTU-GR 2.0.

Because the overflow reduction of sb2 and sb4 is almost stuck after iteration 20th, we specially set Maze_Routing_Iteration=20 in FastDefault.set for sb2 and sb4 to reduce runtime.

Placement
Benchmark

Placement
solution

Table 3: Global Routing Result Obtained by the Fast Mode of NCTU-GR 2.0 with FastDefault.set

Maximum Overflow

Total Overflow

WL

VIA

WL+VIA

Iteration

IO Time (sec)

Routing Time (sec)

LA Time (sec)

Download GR Results

Sb1

SimPLR

0

0

10192433

4692144

14884577

3

11.71

13.37

17.51

-

Sb2

Ripple

8

1766

26093933

8033518

34127451

20

17.99

289.32

41.77

-

Sb4

Ripple

8

312

7677562

3632215

11309777

20

8.22

32.43

12.8

-

Sb5

Ripple

0

0

13323554

5201018

18524572

43

12.2

74.8

22.73

-

Sb10

RADIANT

0

0

19564343

7532051

27096394

25

17.27

225.65

30.98

-

Sb12

SimPLR

0

0

14655041

10152879

24807920

28

19.77

185.17

35.62

-

Sb15

Ripple

0

0

12011664

6791785

18803449

26

15.26

60.08

27.88

-

Sb18

mPL11

0

0

6193659

3870369

10064028

14

7.44

21.57

14.11

-

 

The fast mode uses the techniques presented in the following papers to speed up the 2D routing, so the runtime of 2D routing in Table 3 is about 2.4X~14.5X faster than that in Table1.

W.-H. Liu, Y.-L. Li and C.-K Koh, "A Fast Maze-Free Routing Congestion Estimator With Hybrid Unilateral Monotonic Routing," in Proc. ICCAD, 2012.

 

 

Routability Optimizer

The experiment in Table 4 shows the effectiveness of the routability optimizer in NCTU-GR 2.0, in which we use the following command to optimize the placement solutions in ISPD11 placement contest and then to get the optimized placement solutions.

./NCTUgr  PLACE  <Circuit.aux>  PlaceForGR.set  <Parameter.set>  [PL result]

Then, we use the following command to route the optimized placement solutions to show their global routing results in Table 4.

./NCTUgr  REGULAR  RegularDefault.set  <PL result>  <Parameter.set>  [GR result]

Placement
Benchmark

Placement
solution

Table 4: The Effectiveness of Routability Optimizer (Ropt)

Maximum Overflow

Total Overflow

WL

VIA

WL+VIA

Iteration

IO Time (sec)

Routing Time (sec)

LA Time (sec)

Download GR Results

Sb1

SimPLR + Ropt

0

0

9651239

3992506

13643745

5

11.86

37.55

16.1

-

Sb2

Ripple + Ropt

0

0

22422750

5346928

27769678

25

15.99

996.61

34.9

-

Sb4

Ripple + Ropt

0

0

7210040

3002888

10212928

47

8.38

255.51

11.87

-

Sb5

Ripple + Ropt

0

0

12340595

4237636

16578231

15

11.27

363.66

20.53

-

Sb10

RADIANT+Ropt

0

0

18383943

6021880

24405823

24

16.4

2748.94

37.29

-

Sb12

SimPLR + Ropt

0

0

12209561

7494394

19703955

6

17.4

121.14

28.35

-

Sb15

Ripple + Ropt

0

0

11055531

5646181

16701712

15

14.05

186.81

24.86

-

Sb18

mPL11 + Ropt

0

0

5516695

3227680

8744375

6

6.95

69.28

12

-

 

By comparing Table 1 and Table 4, we can find that the routability optimizer can let the routing results of sb2 and sb4 become overflow-free, and the routing results in Table 4 have 2.7%~12.2% improvement on “WL+VIA” compared to that in Table 1.

 

 

Format Convertor

Because ISPD11 and DAC12 placement benchmarks cannot be easily fed into commercial routers, NCTU-GR 2.0 provides a format convertor to translate their format into LEF/DEF files so that placement-related researches can rely on the format convertor to evaluate the routability of their placement solutions by commercial routers. The user can use the format convertor by the following commend.

./NCTUgr  CONVERT  <Circuit.aux>  <Placement_solution.pl>  <Design.rule>  [LEF/DEF files]

 

We use an example to illustrate how to utilize the format convertor and then evaluate the placement solution by commercial router WROUTE. For example, sb1.aux and sb1.pl are a placement benchmark and the corresponding placement solution in the ISPD11 format, respectively. The user can use the following command to get three files: sb1ForWroute.aux, sb1ForWroute.lef, and sb1ForWroute.def. The basic wire spacing, wire width, and via spacing rules are specified in sb1ForWroute.lef file based on 28nm technology node.

./NCTUgr  CONVERT  sb1.aux  sb1.pl  design28nm.rule  sb1ForWroute

 

Next, if SOC encounter have been installed in the user’s server, the following commands can be used to perform WROUTE on the LEF/DEF files, and finally get a detailed routing result.

         encounter -nowin

         loadLefFile  sb1ForWroute.lef

         loadDefFile  sb1ForWroute.def

         wroute -grouteGrid existing

         wroute -grouteGrid existing -mode postRouteRepair

The above commands are just for reference. If the user is familiar with WROUTE’s commands, the user also can use other commands to control the behavior of WROUTE.

 

If the user wants to adopt the proposed routability optimizer to optimize the placement solutions before performing WROUTE, using PlaceForDR.set to be the parameter setting file for the routability optimizer is recommended. Because, the routability optimizer with PlaceForDR.set can better optimize the local congestion.

 

 

Related Publications to the utilities in NCTU-GR 2.0:

  1. Ke-Ren Dai, Wen-Hao Liu and Yih-Lang Li, "Efficient Simulated Evolution Based Rerouting and Congestion-Relaxed Layer Assignment on 3-D Global Routing," in The 14th Asia and South Pacific Design Automation Conference, Yokohama, pp. 570-575, 2009. (Regular mode)
  2. Wen-Hao Liu, Wei-Chun Kao, Yih-Lang Li, and Kai-Yuan Chao, "Multi-Threaded Collision-Aware Global Routing with Bounded-Length Maze Routing," in Proceedings of ACM/IEEE Design Automation Conference, Anaheim, CA, pp. 200-205, June 2010. (Regular mode)
  3. Ke-Ren Dai, Wen-Hao Liu and Yih-Lang Li, "NCTU-GR: Efficient Simulated Evolution Based Rerouting and Congestion-Relaxed Layer Assignment on 3-D Global Routing," IEEE TVLSI, vol. 20(3), pp. 459-472, Mar. 2012. (Regular mode)
  4. Wen-Hao Liu, Wei-Chun Kao, Yih-Lang Li, and Kai-Yuan Chao, "NCTU-GR 2.0: Multithreaded Collision-Aware Global Routing with Bounded-Length Maze Routing," IEEE TCAD, vol 32(5), pp. 709-722, May 2013. (Regular mode)
  5. Wen-Hao Liu and Yih-Lang Li, "Negotiation-Based Layer Assignment for Via Count and Via Overflow Minimization," in The 16th Asia and South Pacific Design Automation Conference, Yokohama, pp. 539-544, Jan. 2011. (Regular mode)
  6. Wen-Hao Liu, Yih-Lang Li and Cheng-Kok Koh, "A Fast Maze-Free Routing Congestion Estimator With Hybrid Unilateral Monotonic Routing," in Proc. International Conference on Computer-Aided Design, San Jose, CA, pp. 713-719, 2012. (Fast mode)
  7. Wen-Hao Liu, Cheng-Kok Koh and Yih-Lang Li, "Optimization of Placement Solutions for Routability," in Proceedings of Design Automation Conference, to appear, 2013. (Routability optimizer)
  8. Wen-Hao Liu, Cheng-Kok Koh, and Yih-Lang Li, "Case Study for Placement Solutions in ISPD11 and DAC12 Routability-Driven Placement Contests," in Proc. International Symposium on Physical Design, pp.114-119, 2013. (Format converter)

Notice:

l  If you invoke the regular mode in your publication, you could cite papers [3] and [4].

l  If you invoke the negotiation-based layer assignment in your publication, you could cite paper [5].

l  If you invoke the fast mode in your publication, you could cite paper [6].

l  If you invoke the routability optimize in your publication, you could cite paper [7].

l  If you invoke the format converter in your publication, you could cite paper [8].

License Terms

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 NCTU-GR 2.0

Copyright (c) 2013 by Wen-Hao Liu and Yih-Lang Li ("Authors") 
http://cs.nctu.edu.tw/~whliu/NCTU-GR.htm ("URL")
All right reserved

 

Redistribution, with or without modification, are permitted provided that the following conditions are met:

  1. Redistributions 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.
  2. 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.
  3. 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.

 

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.

Go to Wen-Hao Liu’s homepage