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.
Type de document :
Communication dans un congrès
27th International Conference on Microelectronics (ICM), Dec 2015, Casablanca, Morocco. 2015 27th International Conference on Microelectronics (ICM), 〈10.1109/ICM.2015.7438045〉
Liste complète des métadonnées

https://hal.univ-lorraine.fr/hal-01333300
Contributeur : Khadija Bousmar <>
Soumis le : vendredi 17 juin 2016 - 11:11:41
Dernière modification le : lundi 19 février 2018 - 17:02:01

Identifiants

Collections

Citation

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. 2015 27th International Conference on Microelectronics (ICM), 〈10.1109/ICM.2015.7438045〉. 〈hal-01333300〉

Partager

Métriques

Consultations de la notice

90