首页 | 本学科首页   官方微博 | 高级检索  
     

基于Backfilling调度算法的“扩履适足”改进算法
引用本文:付云虹,白树仁,方俊.基于Backfilling调度算法的“扩履适足”改进算法[J].计算机工程与科学,2006,28(9):94-96.
作者姓名:付云虹  白树仁  方俊
作者单位:1. 湖南大学软件学院,湖南,长沙,410082;湖南大学高性能计算中心,湖南,长沙,410082
2. 湖南大学软件学院,湖南,长沙,410082
3. 长沙民政职业技术学院软件学院,湖南,长沙,410004
摘    要:在众多的并行作业调度算法中,Backfilling通常被广泛认为是有效提高CPU利用率的一种算法。该算法是在FCFS算法的基础上,将队列中较小的作业回填(Backfill)到空闲 CPU,以提高CPU利用率。但是,当空闲CPU数量仍然无法满足Backfilling算法中小作业的回填要求时,系统仍有部分CPU闲置,因而也难以达到更好地提高CPU利用率的目的。 。对于共享内存体系结构的并行计算机系统,本文提出了基于Backfilling算法的“扩履适足”的改进算法。该算法以正在运行的作业的CPU利用率为依据,通过动态调整正在运行作业的CPU数,扩大可供回填(backfill)的CPU空间,使得Backfilling算法无法回填的作业得到运行,弥补了Backfilling算法的不足,大大提高了共享内存体系结构并
并行计算机系统的CPU利用率。

关 键 词:并行计算  作业调度  CPU利用率  Backfilling算法  扩履适足
文章编号:1007-130X(2006)09-0094-03
修稿时间:2006年2月10日

An Algorithm for Backfilling-Based "Enlarge Five to Ten"Parallel Job Scheduling
FU Yun-hong,BAI Shu-ren,FANG Jun.An Algorithm for Backfilling-Based "Enlarge Five to Ten"Parallel Job Scheduling[J].Computer Engineering & Science,2006,28(9):94-96.
Authors:FU Yun-hong  BAI Shu-ren  FANG Jun
Abstract: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 CPUs 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 CPUs which are idle.So it is difficult to get the goal of improving CPU utilization.As for memory-shared 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 CPUs 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.
Keywords:parallel computing  jobs scheduling  CPU utilization  backfilling algorithm  enlarge five to ten
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《计算机工程与科学》浏览原始摘要信息
点击此处可从《计算机工程与科学》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号