In the last three decades, task scheduling problems onto parallel processing systems have been extensively studied. Some of those problems take communication delays into account. In most of previous works, the structure of the parallel processing systems of the scheduling problem is restricted to be fully connected. However, the realistic models of parallel processing systems, such as hypercubes, grids, tori, and so forth, are not fully connected and the communication delay has a great effect on the completion time of tasks. In this paper, we show that the problem of scheduling tasks onto a hypercube/grid is NP-complete even if the task set forms an out- or in-tree and the execution time of each task and each communication take one unit time. Moreover, we construct linear time algorithms for computing an optimal schedule of some classes of binary and ternary trees onto a hypercube if each communication has one unit time.
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
Satoshi TAYU, "Scheduling Trees onto Hypercubes and Grids" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 1011-1019, May 2002, doi: .
Abstract: In the last three decades, task scheduling problems onto parallel processing systems have been extensively studied. Some of those problems take communication delays into account. In most of previous works, the structure of the parallel processing systems of the scheduling problem is restricted to be fully connected. However, the realistic models of parallel processing systems, such as hypercubes, grids, tori, and so forth, are not fully connected and the communication delay has a great effect on the completion time of tasks. In this paper, we show that the problem of scheduling tasks onto a hypercube/grid is NP-complete even if the task set forms an out- or in-tree and the execution time of each task and each communication take one unit time. Moreover, we construct linear time algorithms for computing an optimal schedule of some classes of binary and ternary trees onto a hypercube if each communication has one unit time.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_1011/_p
Copy
@ARTICLE{e85-a_5_1011,
author={Satoshi TAYU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Scheduling Trees onto Hypercubes and Grids},
year={2002},
volume={E85-A},
number={5},
pages={1011-1019},
abstract={In the last three decades, task scheduling problems onto parallel processing systems have been extensively studied. Some of those problems take communication delays into account. In most of previous works, the structure of the parallel processing systems of the scheduling problem is restricted to be fully connected. However, the realistic models of parallel processing systems, such as hypercubes, grids, tori, and so forth, are not fully connected and the communication delay has a great effect on the completion time of tasks. In this paper, we show that the problem of scheduling tasks onto a hypercube/grid is NP-complete even if the task set forms an out- or in-tree and the execution time of each task and each communication take one unit time. Moreover, we construct linear time algorithms for computing an optimal schedule of some classes of binary and ternary trees onto a hypercube if each communication has one unit time.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Scheduling Trees onto Hypercubes and Grids
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1011
EP - 1019
AU - Satoshi TAYU
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2002
AB - In the last three decades, task scheduling problems onto parallel processing systems have been extensively studied. Some of those problems take communication delays into account. In most of previous works, the structure of the parallel processing systems of the scheduling problem is restricted to be fully connected. However, the realistic models of parallel processing systems, such as hypercubes, grids, tori, and so forth, are not fully connected and the communication delay has a great effect on the completion time of tasks. In this paper, we show that the problem of scheduling tasks onto a hypercube/grid is NP-complete even if the task set forms an out- or in-tree and the execution time of each task and each communication take one unit time. Moreover, we construct linear time algorithms for computing an optimal schedule of some classes of binary and ternary trees onto a hypercube if each communication has one unit time.
ER -