Böhm, Max and Speckenmeyer, Ewald (1996). A Fast Parallel SAT-Solver - Efficient Workload Balancing. Baltzer. ["eprint_fieldopt_monograph_type_preprint" not defined].

[img]
Preview
 PDF
zpr94-159.pdf - Draft Version
Download (237kB) | Preview

Abstract

We present a fast parallel SAT-solver on a message based MIMD machine. The input formula is dynamically divided into disjoint subformulas. Small subformulas are solved by a fast sequential SAT-solver running on every processor, which is based on the Davis-Putnam procedure with a special heuristic for variable selection. The algorithm uses optimized data structures to modify boolean formulas. Additionally efficient workload balancing algorithms are used, to achieve a uniform distribution of workload among the processors.We consider the communication network topologies d-dimensional processor grid and linear processor array. Tests with up to 256 processors have shown very good efficiency-values (>0.95).

Item Type: Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])
Creators:
CreatorsEmailORCIDORCID Put Code
Böhm, MaxUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Speckenmeyer, EwaldUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-546874
Journal or Publication Title: Annals of Mathematics and Artificial Intelligence
Volume: 17
Number: 2
Page Range: pp. 381-400
Date: 1996
Publisher: Baltzer
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54687

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item