Complexity of Task Graph Scheduling with Fixed Communication Capacity

Abstract : Consider a scheduling problem of parallel computations in multiprocessor systems. Let a parallel program be modeled by a task graph, where vertices represent tasks and arcs the communications between tasks. An interprocessor communication time incurs when two tasks assigned to two different processors have to communicate. Such a scheduling problem has recently been studied in the literature, mostly for the case where interprocessor communication times are fully determined. In this paper, we consider the scheduling problem with communication resource constraints. More specifically, we consider the case where all interprocessor communications take place on a network (communication medium) of bounded capacity. We consider two variants of the problem: %tasks with or without preallocation, communications with independent-data semantics or common-data semantics. We show that even for very specific subproblems, viz. scheduling of general graphs on two processors and scheduling of binary trees on infinite number of processors, the minimization of the makespan of parallel programs in such a multiprocessor system is strongly $\NP$-hard. We first establish the results for the case of capacity 1, referred to as the single-bus system. We then extend the results to the more general case of fixed communication capacities. As a consequence, the general scheduling problem of parallel programs with communication resource constraints is strongly $\NP$-hard. These results are to be contrasted with the corresponding scheduling problems without constraint on the communication capacity, where the two-processor case has unknown time complexity and the infinite-processor case is polynomial. Our results are also extended to the case of broadcasting communications, and can be applied to multiprocessor systems with shared memory.
Type de document :
Rapport
RR-2959, INRIA. 1996
Liste complète des métadonnées

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

Fichiers

Identifiants

  • HAL Id : inria-00073739, version 1

Collections

Citation

Lucian Finta, Zhen Liu. Complexity of Task Graph Scheduling with Fixed Communication Capacity. RR-2959, INRIA. 1996. 〈inria-00073739〉

Partager

Métriques

Consultations de la notice

149

Téléchargements de fichiers

223