| Presentation | 2014-06-12 FPGA Acceleration of SAT/MaxSAT Solving using Variable-way Set Associative Cache Kenji KANAZAWA, Tsutomu MARUYAMA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | WalkSAT (WSAT) is one of the stochastic local search algorithms for Boolean Satisfiability (SAT) and Maximum Boolean Satisfiability (MaxSAT), and it is very suitable for hardware acceleration, because of its high inherent parallelism. Formal verification is one of the most important applications of SAT and MaxSAT, however, the size of the formal verification problems is significantly larger than on-chip memory size, and most of the data have to be placed in off-chip DRAM. In this approach, however, the acceleration was still limited by the DRAM access delay. In this paper, we propose a method to hide the access delay by using on-chip memory banks as a variable-way associative cache memory. With this cache memory, up to 60% DRAM access delay can be hidden, and the performance can be improved up to 26%. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | FPGA / SAT / MaxSAT / WSAT |
| Paper # | RECONF2014-14 |
| Date of Issue |
| Conference Information | |
| Committee | RECONF |
|---|---|
| Conference Date | 2014/6/4(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Reconfigurable Systems (RECONF) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | FPGA Acceleration of SAT/MaxSAT Solving using Variable-way Set Associative Cache |
| Sub Title (in English) | |
| Keyword(1) | FPGA |
| Keyword(2) | SAT |
| Keyword(3) | MaxSAT |
| Keyword(4) | WSAT |
| 1st Author's Name | Kenji KANAZAWA |
| 1st Author's Affiliation | Faculty of, University of Tsukuba() |
| 2nd Author's Name | Tsutomu MARUYAMA |
| 2nd Author's Affiliation | Division of Intelligent Interaction Technologies, Faculty of Systems and Information Engineering, University of Tsukuba |
| Date | 2014-06-12 |
| Paper # | RECONF2014-14 |
| Volume (vol) | vol.114 |
| Number (no) | 75 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |