A Quatum based Method for FPGA Routing

Abstract

The potential of QUANTUM computing has been used to solve many computationally hard problems. FPGA Routing is a compute intensive problem. Existing conventional methods are unable to perform the required breakthrough in terms of complexity, time and cost. This paper presents a quantum search algorithm for FPGA routing in FPGA design architecture. In this approach 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 routing. 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 quantum search algorithm is applied on the Boolean equation for solving routing alternatives utilizing the properties of quantum parallelism and quantum superposition. The approach relies on quantum satisfiability detailed router (QSDR) that uses systematic search using quantum search algorithms. Paper also shows the comparisons of QSDR results to other routing algorithms like GRASP and ZCHAFF. Preliminary experimental results suggest that the developed quantum search algorithm QSDR is taking N M iterations even for large FPGA circuit. The extendibility of this approach will help the designers to find the routing solution of FPGA circuits easily.