ACO Based SAT Solver for FPGA Routing: A Novel Approach

Abstract

In this paper ANT colony optimization algorithm are used to solve geometric FPGA routing for a route based routing constraint model in FPGA design architecture. In our method geometric FPGA routing task is transformed into a Boolean satisfiability (SAT) equation with the property that any assignment of input variables that satisfies the equation specifies a valid route. The satisfiability equation is then modeled as Constraint Satisfaction problem, which helps in reducing procedural programming. Satisfying assignment for particular route will result in a valid routing and absence of a satisfying assignment implies that the layout is unroutable. In second phase ant colony optimization algorithm is applied on the Boolean equation for solving routing alternatives utilizing approach of hard combinatorial optimization problems for stationary and non-stationary environments. The ACO based solution to SAT is then compared with the other SAT solver algorithms such as zChaff and GRASP. Preliminary experimental results suggest that the developed ant colony optimization algorithm is taking mlogm iterations, where m is number of Boolean instances. The experiments has shown that that ACO has performed efficiently to solve SAT based FPGA routing than classical algorithms and has improved complexity of O(nm/ρ log n).