Digitale Medien
Springer
Annals of mathematics and artificial intelligence
17 (1996), S. 381-400
ISSN:
1573-7470
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
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 topologiesd-dimensional processor grid and linear processor array. Tests with up to 256 processors have shown very good efficiency-values (〉0.95).
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF02127976
Permalink
|
Standort |
Signatur |
Erwartet |
Verfügbarkeit |