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
본 논문에서는 할당 문제를 고려한다. n 독립적인 작업 m 작업의 전체 실행 시간이 최소화되는 방식으로 동일한 프로세서를 사용합니다. 기존 작업 할당 문제와 달리 각 작업의 실행 시간이 미리 고정되어 있지 않고 컴파일 시점에 실행 시간의 상한과 하한만 주어진다고 가정합니다. 다음에서는 최적의 오프라인 스케줄링 정책의 결과와 비교하여 최악의 경우 속도 저하 측면에서 여러 기존 스케줄링 정책에 대한 이론적 분석을 먼저 제공합니다. 문헌에서 가장 잘 알려진 알고리즘은 1 + 1/의 최악의 성능 비율을 달성하는 것으로 나타났습니다.f(n) 어디 f(n) = O(n2/3) 고정된 경우 m, 증가하여 1에 접근합니다. n 무한대로. 그런 다음 1 + 1/의 더 나은 최악의 경우 비율을 달성하는 새로운 방식을 제안합니다.g(n) 어디 g(n) = Θ (n/로그 n) 고정된 경우 m, 이는 이전 방식보다 더 빠르게 하나에 접근합니다.
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.
부
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
부
@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},}
부
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 -