A Detailed Router for Field-Programmable Gate Arrays

Abstract

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 connections. CGE has a linear run time over circuit size.

Reference

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)