A Detailed Router for Field-Programmable Gate Arrays
This paper describes a new kind of detailed routing algorithm that has been
designed specifically for Field-Programmable Gate Arrays (FPGAs).
The algorithm is unique in that it approaches this problem in a general
way, allowing it to be used over a wide range of different FPGA routing
architectures. The detailed routing of FPGAs is a new problem that
can be more difficult than classic detailed routing because the wiring segments
that are available for routing are pre-placed and can only be connected
together in specified patterns. In some FPGAs, the routing architecture places
exacting limitations on the routing choices for any connection, and
in such cases there will routing channels in the
FPGA where overlapping routing alternatives of two or more
connections creates competition for the same wiring segments. Resolving these
competitions is essential for achieving 100 % routing in these FPGAs. The
algorithm described here, called the Coarse Graph Expansion (CGE) detailed router for FPGAs, addresses the issue of scarce routing resources by considering the side effects that the routing of one connection has on another, and also has the ability to optimize the routing delays of time-critical connections.
CGE has been used to obtain excellent routing results for several industrial
circuits implemented in FPGAs with various routing architectures.
The results show that CGE is able to route relatively large FPGAs in very close to the minimum number of tracks as determined by global routing, and it can
successfully optimize the routing delays of time-critical
CGE has a linear run time over circuit size.
Stephen D. Brown, Jonathan Rose and Zvonko G. Vranesic, "A Detailed Router for Field-Programmable Gate Arrays," IEEE Transactions on Computer Aided Design of Integrated Circuits and System, Vol. 11, No. 5, May 1992, pp. 620-628.
(Download Full Paper)