Prediction of Parallel Speed-ups for Las Vegas Algorithms
Preprint
Abstract
We propose a probabilistic model for the parallel execution of Las Vegas algorithms, i.e., randomized algorithms whose runtime might vary from one execution to another, even with the same input. This model aims at predicting the parallel performances (i.e., speedups) by analysis the runtime distribution of the sequential runs of the algorithm. Then, we study in practice the case of a particular Las Vegas algorithm for combinatorial optimization, on three classical problems, and compare with an actual parallel implementation up to 256 cores. We show that the prediction can be quite accurate, matching the actual speedups very well up to 100 parallel cores and then with a deviation of about 20% up to 256 cores.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Explicit expressions for moments of order statisticsStatistics & Probability Letters, 2008
- TTT plots: a perl program to create time-to-target plotsOptimization Letters, 2006
- Musical constraint satisfaction problems solved with adaptive searchSoft Computing, 2004
- Cooperative Parallel Variable Neighborhood Search for the p-MedianJournal of Heuristics, 2004
- Introduction to the Special Issue on Parallel Meta-HeuristicsJournal of Heuristics, 2002
- Probability Distribution of Solution Time in GRASP: An Experimental InvestigationJournal of Heuristics, 2002
- Parallel local searchJournal of Heuristics, 1995
- Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problemsArtificial Intelligence, 1992
- Algebraic constructions for costas arraysJournal of Combinatorial Theory, Series A, 1984
- Computer Solutions of the Traveling Salesman ProblemBell System Technical Journal, 1965