20 Nov 10:15 Antti Hyvärinen: Constraint-Based Search in Computational Grids

HIIT seminar, Friday Nov 20, 10:15 a.m. (coffee from 10), Exactum C222

Antti Hyvärinen (Lic.Sc. (Tech.))
Department of Information and Computer Science
Helsinki University of Technology TKK

Constraint-Based Search in Computational Grids

Abstract:
This talk addresses the following question: given an instance of propositional satisfiability problem, a randomized satisfiability
solver, and a cluster of $n$ computers, what is the best way to use the computers to solve the problem? Two approaches, simple parallelization and search space partitioning, are compared both analytically and empirically. The results depend heavily on the type of the problem (unsatisfiable, satisfiable with few solutions, and satisfiable with many solutions) as well as on how good the search space partitioning algorithm is. In addition, the behavior of a real search space partitioning algorithm is evaluated in the same framework. The results suggest that in practice one should combine the simple distribution and search space partitioning approaches.

Bio:
Antti E. J. Hyvärinen, PhD student at TKK, received his master's degree in 2006. His research topic is distributed propositional
satisfiability (SAT) solving using grid and cloud computing. He is the author of a job management software employed in grid-based medical image recognition and SAT solving. The software has attained wide attention: he has been invited to both present and give tutorials on the ideas employed therein, and it has in part driven the development of the NorduGrid and KnowARC projects and contributed to the stability of the Globus toolkit. His current research focuses on enabling solving
of hard SAT instances using massive parallelism, dynamically learned structures, and structure-originating search behavior. He continues to actively participate in development of cloud computing environments.