Predicting Parallel Speed-ups for Las Vegas Algorithms

Speaker: Philippe Codognet, JFLI, CNRS & UPMC & The University of Tokyo

Date: 22nd March 2013

Time: 14:00

Place: room 214, Faculty of Science Bldg. 7, Hongo Campus, The University of Tokyo

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 analyzing the runtime distribution of the sequential runs of the algorithm. 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.

This is a joint work with Charlotte Truchet and Florian Richoux from University of Nantes, France.

 

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *