{
"title": "Faster FPGA Routing Solution using DNA Computing",
"authors": "Manpreet Singh, Parvinder Singh Sandhu, Manjinder Singh Kahlon",
"country": "India",
"institution": "Rayat & Bahra",
"volume": "12",
"journal": "International Journal of Computer, Electrical, Automation, Control and Information Engineering",
"pagesStart": 3847,
"pagesEnd": 3852,
"ISSN": "1307-6892",
"URL": "http:\/\/waset.org\/publications\/15969",
"abstract": "There are many classical algorithms for finding\r\nrouting in FPGA. But Using DNA computing we can solve the routes\r\nefficiently and fast. The run time complexity of DNA algorithms is\r\nmuch less than other classical algorithms which are used for solving\r\nrouting in FPGA. The research in DNA computing is in a primary\r\nlevel. High information density of DNA molecules and massive\r\nparallelism involved in the DNA reactions make DNA computing a\r\npowerful tool. It has been proved by many research accomplishments\r\nthat any procedure that can be programmed in a silicon computer can\r\nbe realized as a DNA computing procedure. In this paper we have\r\nproposed two tier approaches for the FPGA routing solution. First,\r\ngeometric FPGA detailed routing task is solved by transforming it\r\ninto a Boolean satisfiability equation with the property that any\r\nassignment of input variables that satisfies the equation specifies a\r\nvalid routing. Satisfying assignment for particular route will result in\r\na valid routing and absence of a satisfying assignment implies that\r\nthe layout is un-routable. In second step, DNA search algorithm is\r\napplied on this Boolean equation for solving routing alternatives\r\nutilizing the properties of DNA computation. The simulated results\r\nare satisfactory and give the indication of applicability of DNA\r\ncomputing for solving the FPGA Routing problem.",
"references": null,
"publisher": "World Academy of Science, Engineering and Technology",
"index": "International Science Index 12, 2007"
}