Dynamic Scheduling of Parallel Computations

Abstract : Structures of parallel programs are usually modeled by task graphs in the scheduling literature. Such graphs are sometimes obtained while compiling the parallel programs. In many other cases, however, they can be determined only at run time. In this paper, we consider the scheduling of parallel computations whose task graphs are generated at run time. We analyze the case where the task graph has a random out-tree structure. When the number of offspring of a task has geometric distribution with a parameter which is decreasing and convex in the level, or the generation, then the breadth first policy stochastically minimizes the makespan. If, however, this parameter is increasing and concave, then the depth first policy stochastically minimizes the makespan.
Type de document :
Rapport
RR-3048, INRIA. 1996
Liste complète des métadonnées

https://hal.inria.fr/inria-00073644
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:24:27
Dernière modification le : samedi 27 janvier 2018 - 01:31:28
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:37:41

Fichiers

Identifiants

  • HAL Id : inria-00073644, version 1

Collections

Citation

Zhen Liu. Dynamic Scheduling of Parallel Computations. RR-3048, INRIA. 1996. 〈inria-00073644〉

Partager

Métriques

Consultations de la notice

134

Téléchargements de fichiers

73