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.
Keywords :
Document type :
Reports
Domain :

https://hal.inria.fr/inria-00073739
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 1:39:20 PM
Last modification on : Friday, February 4, 2022 - 3:18:41 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:40:31 PM

Identifiers

• HAL Id : inria-00073739, version 1

Citation

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

Record views