For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Scheduling Task In-Trees on Distributed Memory Systems
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/06/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Theory and Models of Software
scheduling, NP-completeness, task-tree, makespan, multiprocessors, interprocessor communication,
Full Text: PDF(288KB)>>
Tree task structures occur frequently in many applications where parallelization may be desirable. We present a formal treatment of non-preemptively scheduling task trees on distributed memory multiprocessors and show that the fundamental problems of scheduling (i) a task tree in absence of any inter-task communication on a fixed number of processors and (ii) a task tree with inter-task communication on an unbounded number of processors are NP-complete. For task trees that satisfy certain constraints, we present an optimal scheduling algorithm. The algorithm is shown optimal over a wider set of task trees than previous works.