Reducing FPGA Router Run-Time Through Algorithm and Architecture
The authors propose a new FPGA routing approach that, when combined with a low-cost architecture change, results in a 34% reduction in router run-time, at the cost of a 3% area overhead, with no increase in critical path delay. Their approach begins with traditional Path-Finder-style routing, which they run on a coarsened representation of the routing architecture. This leads to fast generation of a partial routing solution where 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. Their approach points to a new research direction: reducing FPGA CAD run-time by exploring FPGA architectures and algorithms together.