On the Parallelization of Randomized Propagation-based Constraint Solving

ABSTRACT. We propose to apply a general framework for estimating the parallel performance of Las Vegas algorithms to randomized propagation-based constraint solvers, i.e., when, in the labeling phase, both the variable to instantiate and its value are chosen randomly. Indeed, by analyzing the runtime of the sequential process (which is variable from one run to another because of the stochastic nature of the algorithm) and approximating this runtime distribution with statistical methods, the runtime behavior of the parallel process can be predicted by a model based on order statistics. We apply this approach to study the behavior of a randomized version of the Gecode solver on three classical CSPs problems, and compare the predicted performances to the results of an actual experimentation on parallel hardware up to 256 cores.