Please use this identifier to cite or link to this item:
|Title:||Hardware implementations of real-time reconfigurable WSAT variants||Authors:||Yap, R.H.C.
|Issue Date:||2003||Citation:||Yap, R.H.C.,Wang, S.Z.Q.,Henz, M.J. (2003). Hardware implementations of real-time reconfigurable WSAT variants. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2778 : 488-496. ScholarBank@NUS Repository.||Abstract:||Local search methods such as WSAT have proven to be successful for solving SAT problems. In this paper, we propose two host-FPGA (Field Programmable Gate Array) co-implementations, which use modified WSAT algorithms to solve SAT problems. Our implementations are reconfigurable in real-time for different problem instances. On an XCV1000 FPGA chip, SAT problems up to 100 variables and 220 clauses can be solved. The first implementation is based on a random strategy and achieves one flip per clock cycle through the use of pipelining. The second uses a greedy heuristic at the expense of FPGA space consumption, which precludes pipelining. Both of the two implementations avoid re-synthesis, placement, routing for different SAT problems, and show improved performance over previously published reconfigurable SAT implementations on FPGAs. © Springer-Verlag Berlin Heidelberg 2003.||Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)||URI:||http://scholarbank.nus.edu.sg/handle/10635/39298||ISSN:||03029743|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Oct 14, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.