摘要
在众多的并行作业调度算法中,Backfilling通常被广泛认为是有效提高CPU利用率的一种算法。该算法是在FCFS算法的基础上,将队列中较小的作业回填(Backfill)到空闲CPU,以提高CPU利用率。但是,当空闲CPU数量仍然无法满足Backfilling算法中小作业的回填要求时,系统仍有部分CPU闲置,因而也难以达到更好地提高CPU利用率的目的。对于共享内存体系结构的并行计算机系统,本文提出了基于Backfilling算法的“扩履适足”的改进算法。该算法以正在运行的作业的CPU利用率为依据,通过动态调整正在运行作业的CPU数,扩大可供回填(backfill)的CPU空间,使得Backfilling算法无法回填的作业得到运行,弥补了Backfilling算法的不足,大大提高了共享内存体系结构并行计算机系统的CPU利用率。
There is a wide agreement that backfilling produces significant benefits in scheduling parallel jobs among many algorithms. Backfilling is based on the FCFS algorithm, which backfills smaller queued jobs into idle CPU＇s to improve CPU utilization. But when idle CPUs are still not able to meet the needs for the backfilling algorithm to backfill smaller queued jobs, there are still some CPU＇s which are idle. So it is difficult to get the goal of improving CPU utilization. As for memoryshared architecture parallel computer systems, this paper presents an ＂Enlarge Five to Ten＂ algorithm based on the backfilling algorithm. The algorithm is based on the CPU utilization of running jobs to enlarge the CPU space for backfilling by adjusting dynamically the number of CPU＇s which are running jobs, so it can backfill the jobs which can＇t be backfilled by the backfilling algorithm. The presented algorithm remedies the drawbacks of the backfilling algorithm and improves the CPU utilization of the memory-shared architecture parallel computer systems.
出处
《计算机工程与科学》
CSCD
2006年第9期94-96,122,共4页
Computer Engineering & Science
