Performance Evaluation of Work Stealing for Streaming Applications

Jonatha Anselmi 1 Bruno Gaujal 1, *
* Auteur correspondant
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : This paper studies the performance of parallel stream computations on a multiprocessor architecture using a work-stealing strategy. Incoming tasks are split in a number of jobs allocated to the processors and whenever a processor becomes idle, it steals a fraction (typically half) of the jobs from a busy processor. We propose a new model for the performance analysis of such parallel stream computations. This model takes into account both the algorithmic behavior of work-stealing as well as the hardware constraints of the architecture (synchronizations and bus contentions). Then, we show that this model can be solved using a recursive formula. We further show that this recursive analytical approach is more efficient than the classic global balance technique. However, our method remains computationally impractical when tasks split in many jobs or when many processors are considered. Therefore, bounds are proposed to efficiently solve very large models in an approximate manner. Experimental results show that these bounds are tight and robust so that they immediately find applications in optimization studies. An example is provided for the optimization of energy consumption with performance constraints. In addition, our framework is flexible and we show how it adapts to deal with several stealing strategies.
Type de document :
Communication dans un congrès
International Conference On Principles Of Distributed Systems (OPODIS), 2009, Nimes, France. pp.18-32, 2009, 〈10.1007/978-3-642-10877-8_4〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00788927
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 15 février 2013 - 13:46:34
Dernière modification le : jeudi 11 janvier 2018 - 06:21:39

Identifiants

Collections

Citation

Jonatha Anselmi, Bruno Gaujal. Performance Evaluation of Work Stealing for Streaming Applications. International Conference On Principles Of Distributed Systems (OPODIS), 2009, Nimes, France. pp.18-32, 2009, 〈10.1007/978-3-642-10877-8_4〉. 〈hal-00788927〉

Partager

Métriques

Consultations de la notice

154