Reducing FPGA Router Run-Time Though Algorithm and Architecture

Marcel Gort

University of Toronto

September, 2011

This talk describes 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.