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 (FPGA's). 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 FPGA's is a new problem and can be more difficult than classic detailed routing because the wiring segments that are available for routing are preplaced and can only be connected together in specified patterns. In some FPGA's, 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 create competition for the same wiring segments. Resolving this competition is essential for achieving 100% routing in these FPGA's. The algorithm described here, called the coarse graph expansion (CGE) detailed router for FPGA's, addresses the issue of scare 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 FPGA's with various routing architectures. The results show that CGE is able to route relatively large FPGA's 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.