Ant Colony Optimization Approach for Solving FPGA Routing With Minimum Channel Width
In this paper ANT colony optimization algorithm has been proposed to solve FPGA routing in FPGA design architecture with minimum numbers of tracks per channel. In the authors 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. 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.