FPGA-Based Hardware Acceleration for Boolean Satisfiability

被引：16

作者：

Gulati, Kanupriya ^{[1
]}

Paul, Suganth

Khatri, Sunil P. ^{[1
]}

Patil, Srinivas

Jas, Abhijit

机构：

[1] Texas A&M Univ, College Stn, TX 77843 USA

来源：

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS | 2009年 / 14卷 / 02期

关键词：

Performance; Algorithms; Design; Boolean satisfiabilty (SAT); boolean constant propagation (BCP); conflict induced clauses; non-chronological backtrack; FPGA;

D O I：

10.1145/1497561.1497576

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present an FPGA-based hardware solution to the Boolean satisfiability (SAT) problem, with the main goals of scalability and speedup. In our approach the traversal of the implication graph as well as conflict clause generation are performed in hardware, in parallel. The experimental results and their analysis, along with the performance models are discussed. We show that an order of magnitude improvement in runtime can be obtained over MiniSAT (the best-in-class software based approach) by using a Virtex-4 (XC4VFX140) FPGA device. The resulting system can handle instances with as many as 10K variables and 280K clauses.

引用

页数：11

共 50 条

[21] FPGA-NHAP: A General FPGA-Based Neuromorphic Hardware Acceleration Platform With High Speed and Low Power
Liu, Yijun
Chen, Yuehai
Ye, Wujian
Gui, Yu
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS, 2022, 69 (06) : 2553 - 2566
[22] An FPGA-based Hardware Accelerator for Iris Segmentation
Avey, Joe
Jones, Phillip
Zambreno, Joseph
2018 INTERNATIONAL CONFERENCE ON RECONFIGURABLE COMPUTING AND FPGAS (RECONFIG), 2018,
[23] HARDWARE REDUCTION IN FPGA-BASED MOORE FSM
Barkalov, Alexander
Titarenko, Larysa
Malcheva, Raisa
Soldatov, Kyryll
JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS, 2013, 22 (03)
[24] Protocol Aware ATE with FPGA-based Hardware
Aggarwal, Vineet
2008 IEEE AUTOTESTCON, VOLS 1 AND 2, 2008, : 322 - 324
[25] FPGA-Based Hardware Accelerator for Matrix Inversion
Kokkiligadda V.S.K.
Naikoti V.
Patkotwar G.S.
Sabat S.L.
Peesapati R.
SN Computer Science, 4 (2)
[26] Modular FPGA-Based Hardware Platform for Emulation
Matoga, Lukasz
Koczor, Arkadiusz
Golek, Michal
Zadek, Pawel
Penkala, Piotr
2015 22ND INTERNATIONAL CONFERENCE MIXED DESIGN OF INTEGRATED CIRCUITS & SYSTEMS (MIXDES), 2015, : 402 - 408
[27] FPGA-based hardware to achieve the stereoscopic display
Zhang Guangwei
An Zhiyong
Zheng Fangyin
Zhang Weiwei
ISTM/2007: 7TH INTERNATIONAL SYMPOSIUM ON TEST AND MEASUREMENT, VOLS 1-7, CONFERENCE PROCEEDINGS, 2007, : 1732 - 1735
[28] A survey of FPGA-based hardware implementation of ANNs
Liu, JH
Liang, DQ
PROCEEDINGS OF THE 2005 INTERNATIONAL CONFERENCE ON NEURAL NETWORKS AND BRAIN, VOLS 1-3, 2005, : 915 - 918
[29] Reducing Hardware in FPGA-based Mealy FSM
Kolopienczyk, Malgorzata
Titarenko, Larysa
Mielcarek, Kamil
Barkalov, Alexander
PHOTONICS APPLICATIONS IN ASTRONOMY, COMMUNICATIONS, INDUSTRY, AND HIGH ENERGY PHYSICS EXPERIMENTS 2017, 2017, 10445
[30] An FPGA-based Coprocessor for Hash Unit Acceleration
Fairouz, Abbas
Khatri, Sunil P.
2017 IEEE 35TH INTERNATIONAL CONFERENCE ON COMPUTER DESIGN (ICCD), 2017, : 301 - 304

← 1 2 3 4 5 →