Loading...
Please wait, while we are loading the content...
Similar Documents
Run-time performance optimization of an fpga-based deduction engine for sat solvers (2001).
| Content Provider | CiteSeerX |
|---|---|
| Author | Prasanna, Viktor K. Thiruvengadam, Bharani Dandalis, Andreas Andreas, D. |
| Abstract | FPGAs are a promising technology for accelerating SAT solvers. Besides their high density, fine granularity, and massive parallelism, FPGAs provide the opportunity for run-time customization of the hardware based on the given SAT instance. In this paper, a parallel deduction engine is proposed for backtrack search algorithms. The performance of the deduction engine is critical to the overall performance of the algorithm since, for any moderate SAT instance, millions of implications are derived. We propose a novel approach in which, p, the amount of parallelization of the engine is fine-tuned during problem solving in order to optimize performance. Not only the hardware is initially customized based on the input instance, but it is also dynamically modified in terms of p based on the knowledge gained during solving the SAT instance. Compared with conventional deduction engines that correspond to p =1, we demonstrate speedups in the range of 2:87 ; 5:44 for several SAT instances. |
| File Format | |
| Publisher Date | 2001-01-01 |
| Access Restriction | Open |
| Subject Keyword | Massive Parallelism High Density Deduction Engine Input Instance Moderate Sat Instance Conventional Deduction Engine Novel Approach Backtrack Search Algorithm Sat Instance Run-time Performance Optimization Promising Technology Parallel Deduction Engine Fpga-based Deduction Engine Sat Solver Overall Performance Several Sat Instance Fine Granularity Run-time Customization |
| Content Type | Text |
