Faster FPGA Routing Solution using DNA Computing

Authors: Manpreet Singh, Parvinder Singh Sandhu, Manjinder Singh Kahlon

Abstract:

There are many classical algorithms for finding routing in FPGA. But Using DNA computing we can solve the routes efficiently and fast. The run time complexity of DNA algorithms is much less than other classical algorithms which are used for solving routing in FPGA. The research in DNA computing is in a primary level. High information density of DNA molecules and massive parallelism involved in the DNA reactions make DNA computing a powerful tool. It has been proved by many research accomplishments that any procedure that can be programmed in a silicon computer can be realized as a DNA computing procedure. In this paper we have proposed two tier approaches for the FPGA routing solution. First, geometric FPGA detailed routing task is solved by transforming it into a Boolean satisfiability 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 un-routable. In second step, DNA search algorithm is applied on this Boolean equation for solving routing alternatives utilizing the properties of DNA computation. The simulated results are satisfactory and give the indication of applicability of DNA computing for solving the FPGA Routing problem.

Keywords: FPGA, Routing, DNA Computing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1086137

References:

[1] Eliezer L. Lozinskii, Impurity: Another phase transition of SAT, Journal on Satisfiability, Boolean Modeling and Computation, vol. 1, 2006, pp. 123-14
[2] Gi-Joon Nam, K. A. Sakallah, R. A. Rutenbar, A Comparative Study of Two Boolean Formulations of FPGA Detailed Routing Constraints, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume 21, Issue 6, June 2002 pp. 674 - 684.
[3] E. Bach, A. Condon, E. Glaser and C. Tanguay, DNA models and algorithms for NP-complete problems, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, March 1996, pp. 290.
[4] N. Jonoska and S. A. Karl, A molecular computution of the Road Coloring problem, Proceedings of the 2nd Annual Meeting of DNA based computers, 1996.
[5] Leonard M. Adleman, "Computing with DNA", Scientific American, August 1998.