Open AccessA Distribution Method for Solving SAT in Grids
Author(s) -
Antti E. J. Hyvärinen,
Tommi Junttila,
Ilkka Niemelä
Publication year - 2006
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
ISBN - 3-540-37206-7
DOI - 10.1007/11814948_39
Subject(s) - computer science , grid , solver , heuristic , distributed computing , computation , key (lock) , problem solver , scale (ratio) , mathematical optimization , theoretical computer science , computational science , algorithm , parallel computing , mathematics , artificial intelligence , physics , geometry , computer security , quantum mechanics , programming language
The emerging large-scale computational grid infrastructure is providing an interesting platform for massive distributed computations. In this paper a novel distribution method called scattering is introduced for solving SAT problem instances in grid environments. The key advantages of scattering are that it can be used in conjunction with any sequential SAT solver (including industrial black box solvers), the distribution heuristic is strictly separated from the heuristic used in sequential solving, and it requires no communication between processes solving subproblems but still allows coordination of such processes. An implementation of the method has been developed for NorduGrid, a large widely distributed production-level grid running in Scandinavia.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom