Scheduling Task In-Trees on Distributed Memory Systems

Sanjeev BASKIYAR  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E84-D   No.6   pp.685-691
Publication Date: 2001/06/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Theory and Models of Software
Keyword: 
scheduling,  NP-completeness,  task-tree,  makespan,  multiprocessors,  interprocessor communication,  

Full Text: PDF(288KB)>>
Buy this Article



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.