A Detailed Routing Algorithm for Allocating Wire Segments in Field-Programmable Gate Arrays

This paper describes a new detailed routing algorithm that has been designed specifically for the types of routing architectures that are found in the most recent generation of Field-Programmable Gate Arrays (FPGAs). The router is intended for FPGAs that fit within the symmetrical category, which means that the architecture consists of rows and columns of logic cells with both vertical and horizontal routing channels. The routing algorithm, called SEGA, is unique in that it focuses on not only the issue of achieving success-ful routing of 100 percent of the required connections for a circuit, but also addresses the allocation of wire segments to connections in a way that matches the lengths of the segments to the lengths of the connec-tions. The implementation of the SEGA program is designed in a way that supports a wide range of routing architectures, making the algorithm useful as a research vehicle for exploring new architectures for future FPGAs. SEGA has been used to obtain excellent routing results over a set of several benchmark circuits. The results show that the algorithm can route all of the circuits tested in very close to the theoretical minimum number of routing tracks per channel. In addition, SEGA has been shown to adeptly allocate the wire seg-ments in a segmented FPGA according to the lengths of connections. More specifically, the router does a good job of limiting the number of segments used for long connections and the length of segments assigned to short connections.