Please use this identifier to cite or link to this item:
Title: A Quatum based Method for FPGA Routing
Authors: Chopra, Vinay
Supervisor: Singh, Amardeep
Keywords: floor planning;fpga;fpga routing using sat;routing types
Issue Date: 1-May-2007
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.
Appears in Collections:Masters Theses@CSED

Files in This Item:
File Description SizeFormat 
92034.pdf497.35 kBAdobe PDFView/Open    Request a copy

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.