Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39298
Title: Hardware implementations of real-time reconfigurable WSAT variants
Authors: Yap, R.H.C. 
Wang, S.Z.Q.
Henz, M.J. 
Issue Date: 2003
Source: 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.

Page view(s)

54
checked on Dec 8, 2017

Google ScholarTM

Check


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