关键词: 并行计算 作业调度 CPU利用率 Backfilling算法 扩履适足

Abstract:

There is a wide agreement that backfilling produces significant benefits in scheduling parallel jobs among many algorithms. Backfilling is based on th e 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 nee   eds 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 imp  proving CPU utilization. As for memoryshared architecture parallel computer systems, this paper presents an ＂Enlarge Five to Ten＂ algorithm based on t the backfilling algorithm. The algorithm is based on the CPU utilization of running jobs to enlarge the CPU space for backfilling by adjusting dynamical ly 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 algor  rithm remedies the drawbacks of the backfilling algorithm and improves the CPU utilization of the memory-shared architecture parallel computer systems.

Key words: （parallel computing;jobs scheduling;CPU utilization, backfilling algorithm, enlarge five to ten）