HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 3:10:00 PM
Last modification on : Friday, February 4, 2022 - 3:15:09 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