Competitive Two-Level Adaptive Scheduling Using Resource Augmentation
Competitive Two-Level Adaptive Scheduling Using Resource Augmentation
复制标题
DOI：
10.1007/978-3-642-04633-9_12
复制
发表时间：
2009-10
期刊：
影响因子：
--
通讯作者：
Hongyang Sun;Yangjie Cao;W. Hsu
中科院分区：
文献类型：
--
作者：
Hongyang Sun;Yangjie Cao;W. Hsu
随着多核处理器的激增，确保多处理器系统上的并行作业的高效执行变得比以往任何时候都重要。本文研究了多处理机上具有任意释放时间的并行工件的调度问题，同时考虑了工件的平均响应时间。我们专注于非透视调度计划，自适应重新分配处理器的基础上定期反馈的个人工作。由于它是已知的，没有确定性的非透视算法是有竞争力的这个问题，我们专注于资源增强分析，并表明，两个自适应算法，Agdeq和Abgdeq，实现竞争力的性能使用O（1）倍的处理器比对手快。这些结果是通过一个通用的框架，用于分析任何两级自适应调度的平均响应时间。我们的模拟结果验证了Agdeq和Abgdeq的有效性，通过评估其性能在很大范围内的工作负载组成的合成并行作业具有不同的并行特性。
As multi-core processors proliferate, it has become more important than ever to ensure efficient execution of parallel jobs on multiprocessor systems. In this paper, we study the problem of scheduling parallel jobs with arbitrary release time on multiprocessors while minimizing the jobs’ mean response time. We focus on non-clairvoyant scheduling schemes that adaptively reallocate processors based on periodic feedbacks from the individual jobs. Since it is known that no deterministic non-clairvoyant algorithm is competitive for this problem, we focus on resource augmentation analysis, and show that two adaptive algorithms,AgdeqandAbgdeq, achieve competitive performance usingO(1) times faster processors than the adversary. These results are obtained through a general framework for analyzing the mean response time of any two-level adaptive scheduler. Our simulation results verify the effectiveness ofAgdeqandAbgdeqby evaluating their performances over a wide range of workloads consisting of synthetic parallel jobs with different parallelism characteristics.