The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Dans cet article, nous considérons un problème d’attribution n tâches indépendantes sur m processeurs identiques de manière à minimiser le temps d'exécution global des tâches. Contrairement aux problèmes d'affectation de tâches classiques, nous supposons que le temps d'exécution de chaque tâche n'est pas fixé à l'avance, et que seules les limites supérieure et inférieure du temps d'exécution sont données au moment de la compilation. Dans ce qui suit, nous fournissons d’abord une analyse théorique de plusieurs politiques de planification conventionnelles en termes de ralentissement dans le pire des cas par rapport au résultat d’une politique de planification hors ligne optimale. Il est démontré que l'algorithme le plus connu dans la littérature atteint un rapport de performance dans le pire des cas de 1 + 1/f(n) où f(n) = O(n2/3) pour tout fixe m, qui se rapproche de un en augmentant n à l'infini. Nous proposons ensuite un nouveau schéma qui permet d'obtenir le meilleur ratio du pire cas de 1 + 1/g(n) où g(n) = Θ (n/Journal n) pour tout fixe m, qui s'en rapproche plus rapidement que les schémas précédents.
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.
Copier
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
Copier
@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},}
Copier
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 -