-
题名一种基于模糊聚类的网格DAG任务图调度算法
被引量:48
- 1
-
-
作者
杜晓丽
蒋昌俊
徐国荣
丁志军
-
机构
同济大学电子与信息工程学院
-
出处
《软件学报》
EI
CSCD
北大核心
2006年第11期2277-2288,共12页
-
基金
国家自然科学基金No.60534060
国家重点基础研究发展计(973)No.2003CB316902
+2 种基金
国家科技攻关计划No.2004BA908B07-10
上海市优秀学科带头人计划No.04XD14016
上海市科委2006年度"登山行动计划"No.06JC14065~~
-
文摘
针对网格环境中,任务调度的目标系统具有规模庞大、分布异构和动态性等特点,提出一种基于模糊聚类的网格异构任务调度算法.以往的很多调度算法需要在调度的每一步遍历整个目标系统,虽然能够获得较小的makespan,但是无疑增加了整个调度的Runtime.定义了一组刻画处理单元综合性能的特征,利用模糊聚类方法对目标系统(处理单元网络)进行预处理,实现了对处理单元网络的合理划分,使得在任务调度时能够较准确地优先选择综合性能较好的处理单元聚类,从而缩小搜索空间,大量减少任务调度时选择处理单元的时间耗费.此外,就绪任务优先级的构造既隐含考虑了关键路径上节点的执行情况对整个程序执行的影响,又考虑了异构资源对任务执行的影响.实验及性能分析比较的结果表明,定义的处理器特征能够实现对处理器网络的合理划分,而且随着目标系统规模的增大,所提出的算法优越性越来越明显.
-
关键词
网格
dag(direct
acyclic
grapb)
任务调度
模糊聚类
异构计算环境
-
Keywords
grid
dag (direct acyclic graph)
task scheduling
fuzzy clustering
heterogeneous computing environment
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
-
题名处理顺序约束的信息物理融合系统静态任务表调度算法
被引量:7
- 2
-
-
作者
王小乐
黄宏斌
邓苏
-
机构
国防科学技术大学信息系统工程重点实验室
-
出处
《自动化学报》
EI
CSCD
北大核心
2012年第11期1870-1879,共10页
-
基金
国家高技术研究发展计划(863计划)(2011AA010106)
国家自然科学基金(71071160)资助~~
-
文摘
针对异构环境并行计算的静态任务调度问题,以最小化有向无环图(Directed acyclic graph,DAG)的执行跨度为目标,改变HEFT(Heterogeneous earliest finish time)算法中任务上行权重的计算方法,获得更加合理的任务顺序排列,提出了一种最早完成时间优先的表调度算法IHEFT(Improvement heterogeneous earliest finish time).该算法在计算任务的上行权重时,分别计算该任务分配给不同资源的上行权重,取其最小值,比使用所有资源对该任务的平均处理时间进行计算的HEFT算法更为准确.确定任务的处理顺序后采用最早完成时间越小越优先的策略将任务分配给最优资源,并使得任务的开始执行时间和结束时间满足DAG中有向边的通讯时间约束.通过使用部分文献中的算例数据以及随机生成满足一定结构要求的DAG进行算法测试,将IHEFT与HEFT,CPOP(Critical-path-on-a-processor)和LDCP(Longest dynamic critical path)进行了比较,结果显示IHEFT算法更有效,而且时间复杂度较低.
-
关键词
异构计算环境
信息物理融合系统
有向无环图
任务调度
表调度
静态任务
-
Keywords
heterogeneous computing environment, cyber-physical systems (cps), directed acyclic graph (dag), task
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名云计算环境下基于路径优先级的任务调度算法
被引量:9
- 3
-
-
作者
祝家钰
肖丹
-
机构
重庆邮电大学计算机网络与通信技术市级重点实验室
重庆邮电大学计算智能市级重点实验室
-
出处
《计算机工程与设计》
CSCD
北大核心
2013年第10期3511-3515,共5页
-
基金
重庆邮电大学自然科学基金项目(A2011-25)
-
文摘
为了最小化云计算系统的任务调度长度,结合表启发式调度技术和任务复制的思想提出基于路径优先权的任务调度算法。采用一种新方法计算DAG图中任务节点及边的权值,从最高优先权的路径开始依次选择任务进行调度,并通过有选择性地复制任务节点的父任务来减少任务间信息传送的时间花费,最后将任务安排到使其执行完成时间最早的虚拟机上。通过随机产生的DAG图与HEFT算法进行对比分析,实验结果表明了该算法能获得较短的调度长度。
-
关键词
云计算
异构系统
表启发式调度
有向无环图
路径优先级
任务复制
-
Keywords
cloud computing
heterogeneous systems
list heuristic scheduling algorithm
directed acyclic graph (dag)
path priority-based
task duplication
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-