FGR - A Fairly Good Router (original) (raw)

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 formatand 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 theDAC 2012 place-and-route contest
Official formats of theISPD 2011 place-and-route contest
Official formats of theICCAD 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 theICCAD 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 newsreleases
Michigan EECSannouncements

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 2007benchmarks	FGR 1.1best-seen	ArcherICCAD 2007	BoxRouter 2.0ICCAD 2007
2-d	--	+3.98%	+5.80%
3-d	--	+25.69%	+4.05%
All	--	+10.11%	+4.85%

ISPD 2007Benchmark	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)	Solutiondownload
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