Optimal Grain Size Determination for Tree-Structured Parallel Programs

Tsuyoshi KAWAGUCHI  

IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.1   pp.35-43
Publication Date: 1992/01/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)
time complexity,  multiprocessors,  an optimal schedule,  communication delay,  

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

In this paper we study the problem of scheduling a tree-structured program on multiprocessors so as to minimize the total execution time, which includes communication delay between processors. It is assumed in the problem that a sufficiently large number of processors are available. It is known that if the program structures are restricted to be out-trees, the problem can be solved in O(n2) time, where n denotes the number of modules of a program. However, this problem is known to be NP-hard if the program structures are allowed to be in-trees. Up to now, no optimal algorithm, except an obvious one, was known for the latter case while some approximation algorithms were shown. We present an optimization algorithm with a nontrivial time bound O((1.52)nn log n) for the in-tree case.