dr-cu-fastpass

Dr.CU-Fastpass, an enhanced version of Dr.CU (https://github.com/cuhk-eda/dr-cu), is a VLSI detailed router developed by the research team supervised by Prof. Evangeline F. Y. Young at The Chinese University of Hong Kong (CUHK). Compared with Dr.CU, Dr.CU-FastPass integrates a pin access engine and several other techniques for better DRC convergence.

For now, it only supports design rules in the ISPD 2018 contest benchmark suite.

Please read our paper for more technical details:

• Fangzhou Wang, Jinwei Liu, Jinwei Liu, Wing Ho Lau, Haocheng Li, Evangeline F.Y. Young, "FastPass: A Fast Pin Access Analysis Framework for Detailed Routability Enhancement", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems ( Volume: 43, Issue: 5, May 2024).
• Fangzhou Wang, Jinwei Liu, Evangeline F.Y. Young, "FastPass: Fast Pin Access Analysis with Incremental SAT Solving", ACM International Symposium on Physical Design (ISPD), Virtual Conference, March 26-29, 2023.
• Gengjie Chen, Chak-Wa Pui, Haocheng Li, Jingsong Chen, Bentian Jiang, and Evangeline F.Y. Young, "Detailed Routing by Sparse Grid Graph and Minimum-Area-Captured Path Search", IEEE/ACM Asia and South Pacific Design Automation Conference (ASPDAC), Tokyo, Japan, Jan 21-24, 2019.
• Gengjie Chen, Chak-Wa Pui, Haocheng Li, and Evangeline F.Y. Young, "Dr. CU: Detailed Routing by Sparse Grid Graph and Minimum-Area-Captured Path Search", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 39, no. 9, pp. 1902–1915, 2020.
• Haocheng Li, Gengjie Chen, Bentian Jiang, Jingsong Chen, and Evangeline F.Y. Young, "Dr. CU 2.0: A Scalable Detailed Routing Framework with Correct-by-Construction Design Rule Satisfaction", IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Westminster, CO, USA, Nov 4-7, 2019.

1. How to Build

Step 1: Download the source code. For example,

$ git clone https://github.com/cuhk-eda/dr-cu-fastpass.git

Step 2: Go to the project root and build by

$ cd dr-cu-fastpass
$ scripts/build.py -o release

Note that this will generate two folders under the root, build and run (build contains intermediate files for build/compilation, while run contains binaries and auxiliary files). More details are in scripts/build.py.

1.1. Dependencies

• GCC (version >= 5.5.0) or other working c++ compliers
• CMake (version >= 2.8)
• Boost (version >= 1.58)
• Python (version 3, optional, for utility scripts)
• Innovus® (version 17.1, optional, for design rule checking and evaluation)
• Rsyn (a trimmed version is used, already added under folder rsyn)
• Minisat (v2.2, under folder thirdparty)

2. How to Run

2.1. Toy Test

Run Binary Directly

Go to the run directory and run the binary ispd19dr with a toy case ispd18_sample:

$ cd run
$ ./ispd19dr -lef ../toys/ispd18_sample/ispd18_sample.input.lef -def ../toys/ispd18_sample/ispd18_sample.input.def -guide ../toys/ispd18_sample/ispd18_sample.in
put.guide -output ispd18_sample.solution.def -threads 8

Run with a Wrapping Script [recommended]

Instead of running the binary directly, you may also use a wrapping script run.py to save typing and do more (see the file for more details):

$ cd run
$ ./run.py 8s -p ../toys/

If Innovus® has been properly installed in your OS, an evaluation can be launched by

$ ./run.py 8s -s eval -p ../toys/

In the end, a result table will be printed in the terminal.

Furthermore, the solution can be visualized by

$ ./run.py 8s -s view -p ../toys/

The three steps, route, eval and view of run.py can also be invoked in a single line:

$ ./run.py 8s -s route eval view -p ../toys/

More usage about run.py can be known by the option -h.

2.2. Batch Test

The benchmarks can be downloaded from the hompage of ISPD'18 Contest . You may let run.py know the benchmark path by setting OS environmental variable BENCHMARK_PATH or specifying it under option -p. Then,

$ cd run
$ ./run.py <benchmark_name...|all> -s route eval [option...]

3. Modules

• ispd18eval: scripts and other files for evaluation, provided by ISPD'18 Contest
• ispd19eval: scripts and other files for evaluation, provided by ISPD'19 Contest
• rsyn: code from Rsyn for file IO
• scripts: utility python scripts
• src: C++ source code
  • db: database, including the global grid graph and the net information
  • single_net: routing a single net, including querying the global grid graph, building the local grid graph, running maze routing, and some post processing
  • multi_net: routing all nets with "rip-up and rereoute" and multithreading
  • utils: some utility code
  • pa: pin access engine
• toys: toy test cases

4. Results

Experiments are performed on a Linux server with a 2.90 GHz Intel Xeon CPU. Consistent with the contest, 16 threads are used. Note that we set rrrIter to be 8 for better DRC convergence. With rrrIter=16, better result can be observed for ispd18_test10.

Benchmarks	Wire Length	# Via	# Short	Short Area	# Min Area	# Spacing	Total DRC #	RT (s)
ispd18_test1	440,604	37,442	0	0.0	0	0	0	9
ispd18_test2	7,929,759	376,531	0	0.0	0	1	1	68
ispd18_test3	8,817,839	380,749	11	1.5	0	6	17	1,545
ispd18_test4	26,394,567	760,959	13	10.9	112	60	185	2,254
ispd18_test5	27,874,102	942,666	3	2.8	125	92	220	2,009
ispd18_test6	35,821,552	1,446,618	0	0.0	200	99	299	1,239
ispd18_test7	65,338,312	2,346,860	9	3.7	237	157	403	4,035
ispd18_test8	65,622,748	2,357,369	4	1.7	265	152	421	3,936
ispd18_test9	54,921,494	2,352,642	0	0.0	263	174	437	2,435
ispd18_test10	68,461,622	2,560,944	2,626	1,494.0	400	1,173	4,199	20,618