Scheduling algorithms for linear workflow optimization

Abstract : Pipelined workflows are a popular programming paradigm for parallel applications. In these workflows, the computation is divided into several stages, and these stages are connected to each other through first-in first-out channels. In order to execute these workflows on a parallel machine, we must first determine the mapping of the stages onto the various processors on the machine. After finding the mapping, we must compute the schedule, i.e., the order in which the various stages execute on their assigned processors. In this paper, we assume that the mapping is given and explore the latter problem of scheduling, particularly for linear workflows. Linear workflows are those in which dependencies between stages can be represented by a linear graph. The objective of the scheduling algorithm is either to minimize the period (the inverse of the throughput), or to minimize the latency (response time), or both. We consider two realistic execution models: the one-port model (all operations are serialized) and the multi-port model (bounded communication capacities and communication/computation overlap). In both models, finding a schedule to minimize the latency is easy. However, computing the schedule to minimize the period is NP-hard in the one-port model, but can be done in polynomial time in the multi-port model. We also present an approximation algorithm to minimize the period in the one-port model. Finally, the bi-criteria problem, which consists in finding a schedule respecting a given period and a given latency, is NP-hard in both models.
Type de document :
Communication dans un congrès
IPDPS - 24th IEEE International Parallel and Distributed Processing Symposium - 2010, Apr 2010, Atlanta, United States. pp.1-12, 2010, 〈10.1109/IPDPS.2010.5470346〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00787895
Contributeur : Equipe Roma <>
Soumis le : mercredi 13 février 2013 - 11:46:03
Dernière modification le : mardi 16 janvier 2018 - 15:42:56

Identifiants

Collections

Citation

Kunal Agrawal, Anne Benoit, Loic Magnan, Yves Robert. Scheduling algorithms for linear workflow optimization. IPDPS - 24th IEEE International Parallel and Distributed Processing Symposium - 2010, Apr 2010, Atlanta, United States. pp.1-12, 2010, 〈10.1109/IPDPS.2010.5470346〉. 〈hal-00787895〉

Partager

Métriques

Consultations de la notice

236