The search functionality is under construction.
The search functionality is under construction.

Scheduling Task In-Trees on Distributed Memory Systems

Sanjeev BASKIYAR

  • Full Text Views

    0

  • Cite this

Summary :

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.

Publication
IEICE TRANSACTIONS on Information Vol.E84-D No.6 pp.685-691
Publication Date
2001/06/01
Publicized
Online ISSN
DOI
Type of Manuscript
PAPER
Category
Theory and Models of Software

Authors

Keyword