Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-540-45234-8_48
Title: Hardware implementations of real-time reconfigurable WSAT variants
Authors: Yap, RHC 
Wang, SZQ
Henz, MJ 
Keywords: Science & Technology
Technology
Computer Science, Theory & Methods
Computer Science
SAT
Issue Date: 1-Jan-2003
Publisher: SPRINGER-VERLAG BERLIN
Citation: Yap, RHC, Wang, SZQ, Henz, MJ (2003-01-01). Hardware implementations of real-time reconfigurable WSAT variants. FIELD-PROGRAMMABLE LOGIC AND APPLICATIONS, PROCEEDINGS 2778 : 488-496. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-540-45234-8_48
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: FIELD-PROGRAMMABLE LOGIC AND APPLICATIONS, PROCEEDINGS
URI: https://scholarbank.nus.edu.sg/handle/10635/200924
ISSN: 03029743
16113349
DOI: 10.1007/978-3-540-45234-8_48
Appears in Collections:Staff Publications
Elements

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
fpl2003.pdf95.96 kBAdobe PDF

CLOSED

None

SCOPUSTM   
Citations

11
checked on Dec 6, 2021

Page view(s)

31
checked on Dec 9, 2021

Download(s)

3
checked on Dec 9, 2021

Google ScholarTM

Check

Altmetric


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