ASTEC 2009 Workshop/Summer school on Algorithms and Techniques for Scheduling on Clusters and Grids

Scheduling Pipelined Applications: Models, Algorithms and Complexity

In this talk, I explore the problem of scheduling pipelined applications onto large-scale distributed platforms, in order to optimize several criteria. A particular attention is given to the throughput maximization, (i.e., the number of data sets that can be processed every time unit), the latency minimization (i.e., the time required to process one data set entirely), and the failure probability minimization. First, I accurately define the models and the scheduling problems, and exhibit surprising results, such as the difficulty to compute the optimal throughput and/or latency that can be obtained given a mapping. In particular, I detail the importance of the communication model on the encountered difficulties. Second, I give an overview of complexity results for various cases, both for mono-criterion and for bi-criteria optimization problems. I illustrate the impact of the model on the problem complexity. Finally, I will show some extensions of this work to a different applicative context, such as filtering tasks (that can be found in Web services for instance).