主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第12期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
杜晓丽,蒋昌俊,徐国荣,丁志军.一种基于模糊聚类的网格DAG任务图调度算法.软件学报,2006,17(11):2277-2288
一种基于模糊聚类的网格DAG任务图调度算法
A Grid DAG Scheduling Algorithm Based on Fuzzy Clustering
投稿时间:2006-05-22  修订日期:2006-08-07
DOI:
中文关键词:  网格  DAG(direct acyclic graph)  任务调度  模糊聚类  异构计算环境
英文关键词:grid  DAG(direct acyclic graph)  task scheduling  fuzzy clustering  heterogeneous computing environment
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60534060 (国家自然科学基金); the National Grand Fundamental Research 973 Program of China under Grant No.2003CB316902 (国家重点基础研究发展计划(973)); the Key Technologies R&D Program of China under Grant No.2004BA908B07-10 (国家科技攻关计划); the Program of Shanghai Subject Chief Scientist of China under Grant No.04XD14016 (上海市优秀学科带头人计划); the 2006 Mountaineering Program of Shanghai, China under Grant No.06JC14065 (上海市科委2006年度"登山行动计划")
作者单位
杜晓丽 同济大学,电子与信息工程学院,上海,201804
国家高性能计算机工程技术研究中心,同济分中心,上海,201804 
蒋昌俊 同济大学,电子与信息工程学院,上海,201804
国家高性能计算机工程技术研究中心,同济分中心,上海,201804 
徐国荣 同济大学,电子与信息工程学院,上海,201804
国家高性能计算机工程技术研究中心,同济分中心,上海,201804 
丁志军 同济大学,电子与信息工程学院,上海,201804
国家高性能计算机工程技术研究中心,同济分中心,上海,201804 
摘要点击次数: 5657
全文下载次数: 4380
中文摘要:
      针对网格环境中,任务调度的目标系统具有规模庞大、分布异构和动态性等特点,提出一种基于模糊聚类的网格异构任务调度算法.以往的很多调度算法需要在调度的每一步遍历整个目标系统,虽然能够获得较小的makespan,但是疑增加了整个调度的Runtime.定义了一组刻画处理单元综合性能的特征,利用模糊聚类方法对目标系统(处理单元网络)进行预处理,实现了对处理单元网络的合理划分,使得在任务调度时能够较准确地优先选择综合性能较好的处理单元聚类,从而缩小搜索空间,大量减少任务调度时选择处理单元的时间耗费.此外,就绪任务优先级的构造既隐含考虑了关键路径上节点的执行情况对整个程序执行的影响,又考虑了异构资源对任务执行的影响.实验及性能分析比较的结果表明,定义的处理器特征能够实现对处理器网络的合理划分,而且随着目标系统规模的增大,所提出的算法优越性越来越明显.
英文摘要:
      Focusing on the problem of task scheduling under large-scale,heterogeneous and dynamic environments in grid computing,a heuristic algorithm based on fuzzy clustering is presented.Many previous scheduling algorithms need to search and compare every processing cell in the target system in order to choose a suitable one for a task.Though those methods can get an approving Make-span,undoubtedly,it would increase the entire runtime.A group of features,which describe the synthetic performance of processing cells in the target system,are defined in this paper.With these defined features,the target system,also called processing cell network,is pretreated by fuzzy clustering method in order to realize the reasonable clustering of processor network.In the scheduling stage,the cluster with better synthetic performance will be chosen first.There is no need to search every processing cell in the target system at every scheduling step.Therefore,it largely reduces the cost on choosing which processing cell to execute the current task.The design of the ready task's priority considers not only the influence that comes from the executing of nodes on critical path,but also the influence induced by heterogeneous resource,on which the task will be scheduled.In the last part,the algorithm's performance is analyzed and compared with other algorithms,and the test results show that the bigger the target system is,the better performance the algorithm shows.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利