Estimating the Runtime of Parallel SAT Local Search (Extended Abstract)

Abstract : 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
Type de document :
Communication dans un congrès
Metaheuristics International Conference (MIC 2013), Aug 2013, Singapore, Singapore. 2013
Liste complète des métadonnées

https://hal.inria.fr/hal-00850975
Contributeur : Alejandro Arbelaez <>
Soumis le : samedi 10 août 2013 - 10:45:50
Dernière modification le : jeudi 5 avril 2018 - 10:36:49

Identifiants

  • HAL Id : hal-00850975, version 1

Collections

Citation

Alejandro Arbelaez, Charlotte Truchet, Philippe Codognet. Estimating the Runtime of Parallel SAT Local Search (Extended Abstract). Metaheuristics International Conference (MIC 2013), Aug 2013, Singapore, Singapore. 2013. 〈hal-00850975〉

Partager

Métriques

Consultations de la notice

230