A new FPGA-based DPLL algorithm to improve SAT solvers - Université de Lorraine Access content directly
Conference Papers Year : 2015

A new FPGA-based DPLL algorithm to improve SAT solvers

Abstract

SAT (SATisfiability of Propositional Formula) is a well-known NP-Complete problem [1][2]. Conventional solvers for SAT based on traditional DPLL algorithm presents serious CPU-Times limitations, especially when addressing large size instances. These last decades, a promising approach has emerged for solving efficiently large size instances by using FPGA architectures. This paper follows this last direction and proposes a new and original DPLL solving algorithm based on FPGA. This new FPGA-based DPLL algorithm will use a new backtrack method to reduce the time of problems resolution by using registers which help to save data from the RAM.
No file

Dates and versions

hal-01333300 , version 1 (17-06-2016)

Identifiers

Cite

Khadija Bousmar, Sofiene Dellagi, Fabrice Monteiro, Abbas Dandache, Zineb Habbas. A new FPGA-based DPLL algorithm to improve SAT solvers. 27th International Conference on Microelectronics (ICM), Dec 2015, Casablanca, Morocco. ⟨10.1109/ICM.2015.7438045⟩. ⟨hal-01333300⟩
145 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More