Ant Colony Based Approach for Solving FPGA routing
This paper is based on an ant colony optimization algorithm
(ASDR) for solving FPGA routing for a route based routing
constraint model in FPGA design architecture. In this approach
FPGA routing task is transformed into a Boolean Satisfiabilty
(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 step ant colony optimization
algorithm is applied on the Boolean equation for solving routing
alternatives utilizing approach of hard combinatorial optimization
problems. The experimental results suggest that the developed ant
colony optimization algorithm based router has taken extremely
short CPU time as compared to classical Satisfiabilty based
detailed router (SDR) and finds all possible routes even for large
FPGA circuits.
Keywords: Ant colony optimization, FPGA Routing, Ant Satisfiabilty based detailed routing (ASDR), Boolean Satisfiabilty SAT
Download Full-Text