This paper presents a proposed quantum search algorithm for Field Programmable Gate Array (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 a particular route will result in a valid routing, while the absence of a satisfying assignment implies that the layout is unroutable. The quantum search algorithm was applied to the Boolean equation for solving routing alternatives utilizing the properties of quantum parallelism and quantum superposition. The approach relies on the proposed Quantum Satisfiability Detailed Router (QSDR) that conducts a systematic search using quantum search algorithms. The paper also shows the comparisons of the QSDR results to other routing algorithms like GRASP and ZCHAFF. Preliminary experimental results suggest that the developed quantum search algorithm is taking iterations even for large FPGA circuits. The extendibility of this approach will help the designers to find the routing solution of FPGA circuits easily.

Over the past decade, Field Programmable Gate Array (FPGA) has become an invaluable component in many facets of digital design (Brown et al., 1992). There are many different FPGA architectures available from various vendors including Altera, Xilinx (Xilinx, 2001), Actel, Lucent, Quick Logic and Cypress. The layout structure of the FPGAs depends upon three parameters—configurable logic blocks, Input/Output (I/O) blocks, and programmable routing (Wu and Marek-Sadowska, 1997). The main focus of this paper is programmable FPGA routing. Boolean-based routing is a recent approach that is used for solving routing problem in FPGA layout. Boolean-based routing problem can be represented as a large but atomic Boolean function, which is satisfiable if the layout is routable otherwise routing option is not considered, i.e., any satisfying assignment to the variables of the routing Boolean function represents a legal routing solution (Gi-Joon Nam et al.,1999). Recent advances in SAT solving algorithms (learning and non-chronological backtracking (Aloul et al., 2001) and efficient implementation techniques (e.g., fast implication engine) have dramatically improved the efficiency and capacity of solving the routing tasks in FPGAs.

Solving Detailed FPGA Routing Problem using Quantum Computing,layout, Boolean, routing, assignment, quantum, Booleanbased, algorithms, equation, circuits, problem, results, Satisfiability, design, blocks, Cypress, architecture, developed, Detailed, dramatically, architectures, engine, extendibility, geometric, implication, including, iterations, MarekSadowska, parallelism, nonchronological