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

[thumbnail of zpr94-159.pdf]
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: Monograph (['eprint_fieldopt_monograph_type_preprint' not defined])
Creators:
Creators
Email
ORCID
ORCID Put Code
Böhm, Max
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
Speckenmeyer, Ewald
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
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