Seminario di Informatica: Predicting Parallel Speed-ups for Las Vegas Algorithms

Giovedì 5 Settembre, ore 15:30 - Aula 1BC45 - Philippe Codognet



Giovedì 5 Settembre 2013 alle ore 15:30 in aula 1BC45 della Torre Archimede, Philippe Codognet (JFLI - CNRS / UPMC / University of Tokyo) terrà un seminario dal titolo "Predicting Parallel Speed-ups for Las Vegas Algorithms".

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 an 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 (a constraint-based local search method) on three classical CSP 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. We will also present an application of this framework for the prediction of parallel speedups of two SAT local search solvers on a variety of instances. In this domain again, the predicted results are in accordance with the parallel experiments.

This is a joint work with Charlotte Truchet & Florian Richoux from University of Nantes, France, and Alejandro Arbelaez from JFLI / University of Tokyo, Japan.

Download Seminari di Informatica