In this paper, we consider a problem of assigning n independent tasks onto m identical processors in such a way that the overall execution time of the tasks will be minimized. Unlike conventional task assignment problem, we assume that the execution time of each task is not fixed in advance, and merely upper and lower bounds of the execution time are given at the compile time. In the following, we first provide a theoretical analysis of several conventional scheduling policies in terms of the worst case slowdown compared with the outcome of an optimal off-line scheduling policy. It is shown that the best known algorithm in the literature achieves a worst case performance ratio of 1 + 1/f(n) where f(n) = O(n2/3) for any fixed m, which approaches to one by increasing n to the infinity. We then propose a new scheme that achieves better worst case ratio of 1 + 1/g(n) where g(n) = Θ (n/log n) for any fixed m, which approaches to one more quickly than previous schemes.
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 FUJITA, "Semi-Dynamic Multiprocessor Scheduling with an Asymptotically Optimal Performance Ratio" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 8, pp. 1764-1770, August 2009, doi: 10.1587/transfun.E92.A.1764.
Abstract: In this paper, we consider a problem of assigning n independent tasks onto m identical processors in such a way that the overall execution time of the tasks will be minimized. Unlike conventional task assignment problem, we assume that the execution time of each task is not fixed in advance, and merely upper and lower bounds of the execution time are given at the compile time. In the following, we first provide a theoretical analysis of several conventional scheduling policies in terms of the worst case slowdown compared with the outcome of an optimal off-line scheduling policy. It is shown that the best known algorithm in the literature achieves a worst case performance ratio of 1 + 1/f(n) where f(n) = O(n2/3) for any fixed m, which approaches to one by increasing n to the infinity. We then propose a new scheme that achieves better worst case ratio of 1 + 1/g(n) where g(n) = Θ (n/log n) for any fixed m, which approaches to one more quickly than previous schemes.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.1764/_p
Copy
@ARTICLE{e92-a_8_1764,
author={Satoshi FUJITA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Semi-Dynamic Multiprocessor Scheduling with an Asymptotically Optimal Performance Ratio},
year={2009},
volume={E92-A},
number={8},
pages={1764-1770},
abstract={In this paper, we consider a problem of assigning n independent tasks onto m identical processors in such a way that the overall execution time of the tasks will be minimized. Unlike conventional task assignment problem, we assume that the execution time of each task is not fixed in advance, and merely upper and lower bounds of the execution time are given at the compile time. In the following, we first provide a theoretical analysis of several conventional scheduling policies in terms of the worst case slowdown compared with the outcome of an optimal off-line scheduling policy. It is shown that the best known algorithm in the literature achieves a worst case performance ratio of 1 + 1/f(n) where f(n) = O(n2/3) for any fixed m, which approaches to one by increasing n to the infinity. We then propose a new scheme that achieves better worst case ratio of 1 + 1/g(n) where g(n) = Θ (n/log n) for any fixed m, which approaches to one more quickly than previous schemes.},
keywords={},
doi={10.1587/transfun.E92.A.1764},
ISSN={1745-1337},
month={August},}
Copy
TY - JOUR
TI - Semi-Dynamic Multiprocessor Scheduling with an Asymptotically Optimal Performance Ratio
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1764
EP - 1770
AU - Satoshi FUJITA
PY - 2009
DO - 10.1587/transfun.E92.A.1764
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2009
AB - In this paper, we consider a problem of assigning n independent tasks onto m identical processors in such a way that the overall execution time of the tasks will be minimized. Unlike conventional task assignment problem, we assume that the execution time of each task is not fixed in advance, and merely upper and lower bounds of the execution time are given at the compile time. In the following, we first provide a theoretical analysis of several conventional scheduling policies in terms of the worst case slowdown compared with the outcome of an optimal off-line scheduling policy. It is shown that the best known algorithm in the literature achieves a worst case performance ratio of 1 + 1/f(n) where f(n) = O(n2/3) for any fixed m, which approaches to one by increasing n to the infinity. We then propose a new scheme that achieves better worst case ratio of 1 + 1/g(n) where g(n) = Θ (n/log n) for any fixed m, which approaches to one more quickly than previous schemes.
ER -