IEICE TRANSACTIONS on Information
Optimal Grain Size Determination for Tree-Structured Parallel Programs
Summary :
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)n
- Publication
- IEICE TRANSACTIONS on Information Vol.E75-D No.1 pp.35-43
- Publication Date
- 1992/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Theoretical Foundations of Computing)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tsuyoshi KAWAGUCHI, "Optimal Grain Size Determination for Tree-Structured Parallel Programs" in IEICE TRANSACTIONS on Information,
vol. E75-D, no. 1, pp. 35-43, January 1992, doi: .
Abstract: 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)n
URL: https://global.ieice.org/en_transactions/information/10.1587/e75-d_1_35/_p
Copy
@ARTICLE{e75-d_1_35,
author={Tsuyoshi KAWAGUCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Optimal Grain Size Determination for Tree-Structured Parallel Programs},
year={1992},
volume={E75-D},
number={1},
pages={35-43},
abstract={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)n
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - Optimal Grain Size Determination for Tree-Structured Parallel Programs
T2 - IEICE TRANSACTIONS on Information
SP - 35
EP - 43
AU - Tsuyoshi KAWAGUCHI
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1992
AB - 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)n
ER -
English
