A Fairly Good Router

Authors: Jarrod A. Roy and Igor L. Markov
Contact: fgr.request@gmail.com
Funding: National Science Foundation, Sun Microsystems

Last updated by jinhu on April 10, 2014

FGR is free open-source software for global routing, based on Lagrange Multipliers --- an approach similar to what industry routers use, but with greater mathematical rigor and robust performance. Unlike most other academic tools, FGR is self-contained and does not rely on ILP or external Steiner-tree constructors. At the ISPD 2007 Global Routing Contest, FGR won in the 2-dim category and placed 3rd in the 3-dim category. BFG-R - a newer router spun out of FGR, was used as an official evaluator of solutions at the ICCAD 2012 place-and-route contest.

FGR Supported I/O formats and benchmarks

Input: Labyrinth format and ISPD 2007 contest format
Output: BoxRouter format

ISPD98 benchmarks (Labyrinth format)
ISPD 2007 Global Routing Contest benchmarks (with a verification script)

B-FGR Supported I/O formats and benchmarks

Official formats of the DAC 2012 place-and-route contest
Official formats of the ISPD 2011 place-and-route contest
Official formats of the ICCAD 2012 place-and-route contest

Source code and binary distributions

Best solutions provided by FGR as of Nov. 5, 2007 are available in the performance section below.
Source code and binaries are available upon request from fgr.request@gmail.com.
Please include the following information in your message:

Your name and affiliation
Possible uses of FGR and/or reason for interest
Computing platform (OS, compiler version, etc.)
A statement indicating agreement to our license terms (revised March 5, 2008).
The current license is for academic use only; if you are interested in industry or commercial use, please request a separate license.

Currently available source code and binary distributions:

BFG-R for Linux (64 bit) used to evaluate solutions at the ICCAD 2012 place-and-route contest.

If you are using FGR in your work, please reference our publications below rather than only this website.

Publications and press coverage

Jin Hu, Jarrod A. Roy, and Igor L. Markov, ``Completing high-quality global routes'' (.pdf), ISPD 2010, pp. 35-4.
Jarrod A. Roy and Igor L. Markov, ``High-Performance Routing at the Nanometer Scale'' (.pdf) , IEEE Trans. on CAD of Integrated Circuits and Systems 27(6) pp. 1066-1077 (2008).
J. A. Roy and I. L. Markov, ``High-performance Routing at the Nanometer Scale'' (.pdf), in Proc. Int'l Conf. on Computer-Aided Design (ICCAD), pp. 496-502, San Jose, CA, November 2007.

FGR in the news:

R. Goering, ``Open-source IC Routers Aid CAD Research,'' SCDsource, November 16, 2007. Online
R. Goering, ``IC Routing Contest Boosts CAD Research,'' EE Times, March 22, 2007. Online
Michigan Engineering news releases
Michigan EECS announcements

Performance

We currently provide two sets of results for FGR 1.1:

Default solutions for FGR 1.1 which provide a reasonable trade-off between runtime and solution quality. All runtimes were generated using a 2.4GHz Opteron processor (to convert our runtimes to a 3.6GHz Intel Xeon processor, divide them by 1.67)
Best-seen results for FGR 1.1 where non-default parameters are chosen for each benchmark and a runtime limit of 48 hours is imposed.

If you are comparing your results with FGR, please clearly state which set(s) of results are used.

For a paper where runtimes are not reported, comparisons should be made against best-seen results.
If runtime is reported, comparisons can be made against both sets of results.
When comparing against best-seen results, please give the date of download for the results.
For comparisons against default results, report the version of FGR used to generate the results since the results are likely to improve in future versions.

Summary comparison between FGR 1.1 and other academic routers:

ISPD 2007 benchmarks	FGR 1.1 best-seen	Archer ICCAD 2007	BoxRouter 2.0 ICCAD 2007
2-d	--	+3.98%	+5.80%
3-d	--	+25.69%	+4.05%
All	--	+10.11%	+4.85%

ISPD 2007
Benchmark Best competition from ISPD 2007 FGR 1.1 default FGR 1.1 best-seen results as of 11/5/07
Overflow Total WL
(e5) Router Overflow Total WL
(e5) Runtime
(minutes) Overflow Total WL
(e5) Solution
download
Total Max. Total Max. Total Max.
adaptec1 2-d 0 0 58.84 BoxRouter 0 0 54.73 203 0 0 53.71 ad1-2d-best.routes.gz
adaptec1 3-d 0 0 99.61 MaizeRouter 0 0 88.59 212 0 0 88.02 ad1-3d-best.routes.gz
adaptec2 2-d 0 0 55.69 BoxRouter 0 0 52.40 24 0 0 51.86 ad2-2d-best.routes.gz
adaptec2 3-d 0 0 98.12 MaizeRouter 0 0 90.08 28 0 0 89.96 ad2-3d-best.routes.gz
adaptec3 2-d 0 0 137.75 MaizeRouter 0 0 131.50 94 0 0 130.30 ad3-2d-best.routes.gz
adaptec3 3-d 0 0 214.08 MaizeRouter 0 0 200.59 141 0 0 200.14 ad3-3d-best.routes.gz
adaptec4 2-d 0 0 128.45 MaizeRouter 0 0 125.00 14 0 0 123.97 ad4-2d-best.routes.gz
adaptec4 3-d 0 0 194.38 MaizeRouter 0 0 182.99 36 0 0 178.90 ad4-3d-best.routes.gz
adaptec5 2-d 0 0 164.32 BoxRouter 0 0 153.21 616 0 0 151.47 ad5-2d-best.routes.gz
adaptec5 3-d 0 0 298.08 BoxRouter 0 0 261.26 655 0 0 260.53 ad5-3d-best.routes.gz
newblue1 2-d 400 2 51.13 BoxRouter 368 6 46.33 503 234 2 46.42 nb1-2d-best.routes.gz
newblue1 3-d 400 2 101.83 BoxRouter 378 2 90.56 511 238 2 90.68 nb1-3d-best.routes.gz
newblue2 2-d 0 0 79.64 MaizeRouter 0 0 76.54 4 0 0 75.78 nb2-2d-best.routes.gz
newblue2 3-d 0 0 139.66 MaizeRouter 0 0 132.54 9 0 0 129.30 nb2-3d-best.routes.gz
newblue3 2-d 32588 1236 114.63 MaizeRouter 39204 1188 107.23 1549 38386 1196 107.28 nb3-2d-best.routes.gz
newblue3 3-d 32840 1058 184.40 MaizeRouter 39384 396 163.36 1561 38398 400 163.41 nb3-3d-best.routes.gz
Average -7.4% -8.1%

ISPD 2007 Benchmark	Best competition from ISPD 2007	FGR 1.1 default	FGR 1.1 best-seen results as of 11/5/07
Overflow	Total WL (e5)	Router	Overflow	Total WL (e5)	Runtime (minutes)	Overflow	Total WL (e5)	Solution download
Total	Max.	Total	Max.	Total	Max.
adaptec1 2-d	0	0	58.84	BoxRouter	0	0	54.73	203	0	0	53.71	ad1-2d-best.routes.gz
adaptec1 3-d	0	0	99.61	MaizeRouter	0	0	88.59	212	0	0	88.02	ad1-3d-best.routes.gz
adaptec2 2-d	0	0	55.69	BoxRouter	0	0	52.40	24	0	0	51.86	ad2-2d-best.routes.gz
adaptec2 3-d	0	0	98.12	MaizeRouter	0	0	90.08	28	0	0	89.96	ad2-3d-best.routes.gz
adaptec3 2-d	0	0	137.75	MaizeRouter	0	0	131.50	94	0	0	130.30	ad3-2d-best.routes.gz
adaptec3 3-d	0	0	214.08	MaizeRouter	0	0	200.59	141	0	0	200.14	ad3-3d-best.routes.gz
adaptec4 2-d	0	0	128.45	MaizeRouter	0	0	125.00	14	0	0	123.97	ad4-2d-best.routes.gz
adaptec4 3-d	0	0	194.38	MaizeRouter	0	0	182.99	36	0	0	178.90	ad4-3d-best.routes.gz
adaptec5 2-d	0	0	164.32	BoxRouter	0	0	153.21	616	0	0	151.47	ad5-2d-best.routes.gz
adaptec5 3-d	0	0	298.08	BoxRouter	0	0	261.26	655	0	0	260.53	ad5-3d-best.routes.gz
newblue1 2-d	400	2	51.13	BoxRouter	368	6	46.33	503	234	2	46.42	nb1-2d-best.routes.gz
newblue1 3-d	400	2	101.83	BoxRouter	378	2	90.56	511	238	2	90.68	nb1-3d-best.routes.gz
newblue2 2-d	0	0	79.64	MaizeRouter	0	0	76.54	4	0	0	75.78	nb2-2d-best.routes.gz
newblue2 3-d	0	0	139.66	MaizeRouter	0	0	132.54	9	0	0	129.30	nb2-3d-best.routes.gz
newblue3 2-d	32588	1236	114.63	MaizeRouter	39204	1188	107.23	1549	38386	1196	107.28	nb3-2d-best.routes.gz
newblue3 3-d	32840	1058	184.40	MaizeRouter	39384	396	163.36	1561	38398	400	163.41	nb3-3d-best.routes.gz
Average		-7.4%		-8.1%

Other academic routing tools on the Web

BoxRouter, Minsik Cho and David Z. Pan, http://www.cerc.utexas.edu/utda/download/BoxRouter.htm
MaizeRouter, Michael Moffitt, http://www.eecs.umich.edu/~mmoffitt/MaizeRouter/

since November 2, 2007