Using Sequential Runtime Distributions for the Parallel Speedup Prediction of SAT Local Search
This work addresses performance prediction for parallel SAT solvers, which is incremental as it applies statistical methods to an existing problem.
The paper tackles the problem of predicting parallel performance for SAT local search algorithms by analyzing sequential runtime distributions, showing that the model accurately predicts performance close to empirical data on up to 384 cores.
This paper presents a detailed analysis of the scalability and parallelization of local search algorithms for the Satisfiability problem. We propose a framework to estimate the parallel performance of a given algorithm by analyzing the runtime behavior of its sequential version. Indeed, by approximating the runtime distribution of the sequential process 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 parallel performance of two SAT local search solvers, namely Sparrow and CCASAT, and compare the predicted performances to the results of an actual experimentation on parallel hardware up to 384 cores. We show that the model is accurate and predicts performance close to the empirical data. Moreover, as we study different types of instances (random and crafted), we observe that the local search solvers exhibit different behaviors and that their runtime distributions can be approximated by two types of distributions: exponential (shifted and non-shifted) and lognormal.