Nearly-2-SAT Solutions for Segmented-Channel Routing
Shyamapada Mukherjee, Suchismita Roy · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2015
This paper proposes a nearly-2-satisfiability (SAT) routing solution for segmented-channels in row-based field programmable gate array architectures. Both dogleg-free routing and routing with dog-legging are considered here. The constraints for these problems have been expressed as Boolean conjunctive norm form (CNF) clauses and the conjunction of these clauses creates a Boolean function. The formulation ensures that the maximum number of clauses created consist of 2 literals. Hence, it converts the routing problem, which is an optimization problem, to a nearly-2-SAT problem. Since 2-SAT, i.e., checking the SAT of a Boolean CNF function with clauses having maximum 2 literals, is polynomial time computable, a nearly-2-SAT problem will also compute faster than other SAT-based solutions. We have used statistical distributions to experimentally test the efficiency of our technique and compared the performance with existing SAT-based technique for segmented-channel routing. The results show that more than 90% clauses are 2-literal for both routing options in the proposed methodology and around 20× speedup is observed with respect to existing technique.