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

一种适于异构环境的任务调度算法
引用本文:支青,蒋昌俊.一种适于异构环境的任务调度算法[J].自动化学报,2005,31(6):865-872.
作者姓名:支青  蒋昌俊
作者单位:1.同济大学计算机科学与工程系 上海 200092
基金项目:国家高技术研究发展计划(863)(2004AA104340),国家重点基础研究发展规划(973)(2003CB316902),国家自然科学基金重大研究计划(90412013),国家杰出青年科学基金(60125205),上海科技攻关研究项目(03DZ15029)资助
摘    要:针对异构环境独立任务调度问题提出两个调度原则,并基于Min-min算法提出优先级最小最早完成时间算法(Priority min-min,PMM).该算法将任务在各处理机上执行时间的标准误差作为任务的优先级.选取最早完成时间较小的k个任务,优先调度其中优先级最高的一个.在实验基础上分析了参数$k$对PMM算法性能的影响. PMM算法克服了min-min算法单纯追求局部最优的局限性,更适合于异构环境.实验数据表明PMM算法能有效地降低调度跨度,其性能比min-min算法有明显提高.

关 键 词:调度    最早完成时间    最少执行时间    调度跨度    标准误差
收稿时间:2004-11-10
修稿时间:2005-09-29

A Scheduling Algorithm Suitable for Heterogeneous Computing Environment
ZHI Qing,JIANG Chang-Jun.A Scheduling Algorithm Suitable for Heterogeneous Computing Environment[J].Acta Automatica Sinica,2005,31(6):865-872.
Authors:ZHI Qing  JIANG Chang-Jun
Affiliation:1.Department of Computer Science and Engineering, Tongji University, Shanghai 200092
Abstract:This paper presents two scheduling principles suitable to independent job schedul- ing in heterogeneous computing environment.A new algorithm named Priority Min-min (PMM)is presented,which computes jobs' priorities based on their standard deviation of execution time.PMM chooses k jobs which have smaller earliest finish times,and assigns the job with the highest priority to the corresponding processor.This paper analyses how k influences the performance of PMM by experiment.PMM is more suitable for heteroge- neous processor platforms by surmounting the limitation of Min-min.The experimental data show that PMM reduces the makespan effectively and its performance is much better than Min-min.
Keywords:Scheduling  EFT  MET  makespan  standard deviation  
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《自动化学报》浏览原始摘要信息
点击此处可从《自动化学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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