Estimating parallel runtimes for randomized algorithms in constraint solving

Charlotte Truchet (), Alejandro Arbelaez (), Florian Richoux () and Philippe Codognet ()
Additional contact information
Charlotte Truchet: University of Nantes
Alejandro Arbelaez: University College Cork
Florian Richoux: University of Nantes
Philippe Codognet: University of Tokyo

Journal of Heuristics, 2016, vol. 22, issue 4, No 12, 613-648

Abstract: Abstract This paper presents a detailed analysis of the scalability and parallelization of Local Search algorithms for constraint-based and SAT (Boolean satisfiability) solvers. 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 a constraint-based Local Search solver (Adaptive Search), two SAT Local Search solvers (namely Sparrow and CCASAT), and a propagation-based constraint solver (Gecode, with a random labeling heuristic). We compare the performance predicted by our model to actual parallel implementations of those methods using up to 384 processes. We show that the model is accurate and predicts performance close to the empirical data. Moreover, as we study different types of problems, we observe that the experimented solvers exhibit different behaviors and that their runtime distributions can be approximated by two types of distributions: exponential (shifted and non-shifted) and lognormal. Our results show that the proposed framework estimates the runtime of the parallel algorithm with an average discrepancy of 21 % w.r.t. the empirical data across all the experiments with the maximum allowed number of processors for each technique.

Keywords: Constraint solving; Parallel processing; Performance model; Randomized constraint solving (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-015-9292-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:22:y:2016:i:4:d:10.1007_s10732-015-9292-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-015-9292-3

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().