An architecture-aware routing optimization via satisfiabilty for hierarchical FPGA

Boolean Satisfiability (SAT) has successfully been applied to the FPGA routing. It has many advantages over the conventional one-net-a-time routing algorithm such as routing all nets concurrently, higher flexibility and unroutability provable. However it also has the limits of scalability and is time-consuming. This paper presents some optimizations to the SAT-based routing approach by applying some architecture related features to the generated the Boolean constraints function. Specifically, Switch Box based connectivity optimization to reduce the variable number for each net, Logic Block pins rearrangement to improve the flexibility for each net and Exclusivity constraints optimization based on net-to-track distribution. Each of the optimizations is discussed in detail in this paper. Some heuristics and algorithms are also presented to implement the optimizations. We implement the SAT-based routing strategy as well as the optimizations on a general hierarchical FPGA architecture. The experimental results show that we can greatly reduce the variable and constraint number of the generated Boolean SAT functions. Hence, the generated SAT functions can be solved much more quickly. It also shows that high routing flexibility is also achieved due to the pins rearrangement.