Reducing FPGA Router Run-Time Through Algorithm and Architecture

Abstract—We 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. Our approach begins with traditional 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 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. Our approach points to a new research direction: reducing FPGA CAD run-time by exploring FPGA architectures and algorithms together. I