검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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

Semi-Dynamic Multiprocessor Scheduling with an Asymptotically Optimal Performance Ratio 점근적으로 최적의 성능 비율을 갖는 반동적 다중 프로세서 스케줄링

Satoshi FUJITA

  • 조회수

    0

  • 이것을 인용

요약 :

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

발행
IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.8 pp.1764-1770
발행일
2009/08/01
공개일
온라인 ISSN
1745-1337
DOI
10.1587/transfun.E92.A.1764
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주
이론

작성자

키워드