Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 3:10:00 PM
Last modification on : Saturday, January 27, 2018 - 1:31:23 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 4:46:15 PM


  • 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⟩



Record views


Files downloads