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.
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.
Copy
Sanjeev BASKIYAR, "Scheduling Task In-Trees on Distributed Memory Systems" in IEICE TRANSACTIONS on Information,
vol. E84-D, no. 6, pp. 685-691, June 2001, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e84-d_6_685/_p
Copy
@ARTICLE{e84-d_6_685,
author={Sanjeev BASKIYAR, },
journal={IEICE TRANSACTIONS on Information},
title={Scheduling Task In-Trees on Distributed Memory Systems},
year={2001},
volume={E84-D},
number={6},
pages={685-691},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={June},}
Copy
TY - JOUR
TI - Scheduling Task In-Trees on Distributed Memory Systems
T2 - IEICE TRANSACTIONS on Information
SP - 685
EP - 691
AU - Sanjeev BASKIYAR
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E84-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2001
AB - 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.
ER -