Title :
Combined Architecture/Algorithm Approach to Fast FPGA Routing
Author :
Gort, M. ; Anderson, James H.
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Toronto, Toronto, ON, Canada
Abstract :
We propose a new field-programmable gate array (FPGA) routing approach, which, when combined with a low-cost architecture change, results in a 40% reduction in router runtime, at the cost of a 6% area overhead and with no increase in critical path delay. Our approach begins with PathFinder-style routing, which we run on a coarsened representation of the routing architecture. This leads to fast generation of a partial routing solution where the signals are assigned to groups of wire segments rather than individual wire segments. A Boolean satisfiability (SAT)-based stage follows, generating a legal routing solution from the partial solution. We explore approximately 165 000 FPGA switch block architectures, showing that the choice of the architecture has a significant impact on the complexity of the SAT formulation, and by extension, on routing runtime. Our approach points to a new research direction, namely, reducing FPGA computer-aided design runtime by exploring FPGA architectures and algorithms together.
Keywords :
computability; computer architecture; field programmable gate arrays; network routing; Boolean satisfiability; FPGA routing; FPGA switch block architecture; PathFinder-style routing; SAT-based stage; critical path delay; field-programmable gate array; low-cost architecture; Design automation; Field programmable gate arrays; Law; Routing; Runtime; Wires; Computer-aided design (CAD); FPGA routing; field-programmable gate array (FPGA) architecture; satisfiability (SAT);
Journal_Title :
Very Large Scale Integration (VLSI) Systems, IEEE Transactions on
DOI :
10.1109/TVLSI.2012.2202326