Scheduling of Parallel Programs in Single-Bus Multiprocessor Systems

Abstract : Consider a scheduling problem of parallel computations in multiprocessor systems. Let a parallel program be represented by a task graph, where vertices represent tasks and arcs represent the communications between the 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 resource constraints. More specifically, we consider the case where all interprocessor communications take place on a single bus. We show that even for very specific subproblems, the minimization of the makespan of parallel programs in such a single-bus multiprocessor system is NP-hard. Thus, the general scheduling problem of parallel programs with communication resource constraints is NP-hard. We consider several variants of the problem: tasks with or without preallocation, communications with independent-data semantics or common-data semantics. Our results are extended to the cases of blocking communications and of broadcasting communications, and can be applied to multiprocessor systems with shared memory.
Type de document :
[Research Report] RR-2302, INRIA. 1994
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:10:00
Dernière modification le : samedi 27 janvier 2018 - 01:31:23
Document(s) archivé(s) le : mardi 12 avril 2011 - 16:46:15



  • HAL Id : inria-00074371, version 1



Lucian Finta, Zhen Liu. Scheduling of Parallel Programs in Single-Bus Multiprocessor Systems. [Research Report] RR-2302, INRIA. 1994. 〈inria-00074371〉



Consultations de la notice


Téléchargements de fichiers