ABSTRACT

In this paper ANT colony optimization algorithm has been proposed to solve FPGA routing in FPGA design architecture with minimum umbers of tracks per channel. 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 equationis then modeled as Constraint Satisfaction problem. 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 of this method ant colony optimization algorithm is applied on the Boolean equation for solving routing alternatives utilizing approach of hard combinatorial optimization problems. The ACO based solution to SAT is then compared with the other SAT solver algorithms such as zChaff and GRASP. The experimental results suggested that the developed ant colony optimization algorithm is taking fewer amounts of time and minimum channel width to route a FPGA chip.