Chunkai Fu, Ben Trombley, et al.
ISVLSI 2023
This paper presents empirical analyses of two Boolean Satisfiability (SAT) formulations of FPGA (Field Programmable Gate Array) detailed routing constraints. Boolean SAT-based routing transforms a routing problem into a Boolean SAT instance by rendering geometric routing constraints as an atomic Boolean function. The generated Boolean function is satisfiable if and only if the corresponding routing is possible. Two different Boolean SAT-based routing models are analyzed: the track-based and the route-based routing constraint model. The track-based routing model transforms a routing task into a net-to-track assignment problem, whereas the route-based routing model reduces it into a routability-checking problem with explicitly enumerated set of detailed routes for nets. In both models, routing constraints are represented as CNF Boolean Satisfiability clauses. Through comparative experiments, we demonstrate that the route-based formulation yields an easier-to-evaluate and more scalable routability Boolean function than the track-based method. This is empirical evidence that a smart/efficient Boolean formulation can achieve significant performance improvement in real-world applications.
Chunkai Fu, Ben Trombley, et al.
ISVLSI 2023
Haoxing Ren, David Z. Pan, et al.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Jeonghee Shin, John A. Darringer, et al.
SOCC 2011
Gi-Joon Nam
ISPD 2006