附加信息对负载可任意划分应用调度的影响

Additional Information-aware Divisible Load Scheduling

研究需要附加信息的可任意划分应用的调度问题.文章首先引入附加信息的概念,扩展了DLS模型,在此基础上重新分析了在这类应用中经典的平均划分(EQS)算法的缺陷,并提出了一个无空闲时间调度算法(NIS).基于这两个算法的解析表达解,严格地证明了NIS算法的调度性能总是优于EQS算法.由于在这类应用中典型的情况是每个处理器需要相同的附加信息,文章进一步研究了这类典型应用.分析表明,与EQS算法相比有更大范围的应用能利用NIS算法获得并行计算的收益,NIS算法所能利用的资源也更多.

This paper introduces overhead of additional information into the divisible load scheduling model. We revised a common and efficient-proved algorithm called Equally Partitioning Scheme under the extended model, and proposed a novel scheduling algorithm which is based on LIFO policy and makes the master processor receive the results continuously without idle. Closed-form solutions for the processing time for both schemes are derived. Based on these solutions, we rigorously proved that the proposed algorithm is always better than the equally partitioning scheme in terms of the total time cost. Assigning equal additional information to every processor in one system is a typical class of applications. For these applications, our analysis showed that the proposed algorithm can make use of more computing resources and benefit extensive applications compared to equally partitioning scheme.