第26卷第1期 2005年1月
小型微型计算机系统M
![同构计算环境中一种新的静态任务调度算法[2]](https://img.doc.guandang.net/pic/729bd5a758cb4911ffdf99ea/1-118-png_6_0_0_45_1089_37_22_831_1129.5-200-0-16-200.jpg)
INI-MICROSYSTEMSVol126No.1
Jan.2005
同构计算环境中一种新的静态任务调度算法
韩建军1,AbbasA.Essa2,李庆华1
1(2(
华中科技大学计算机科学与技术学院,湖北武汉430074)南京大学电子科学与工程系,江苏南京210093)
E2mail:han-j-j@163.com
摘 要:延伸了TTIG模型并提出新的算法.在模拟实验中,将此算法与MATE和其它同构环境中基于DAG的调度算法,在不同测试条件下进行了比较,结果显示该算法性能明显优于MATE,与基于DAG模型的调度算法比较而言,在性能方面各有千秋,但在算法时间复杂度方面具有显著的优势.关键词:任务调度;表调度;启发式方法
中图分类号:TP302 文献标识码:A 文章编号:100021220(2005)0120059205
NewStaticTaskSchedulingAlgorithminHomogeneousComputingEnvents
121
HANJian2Jun,AbbasA.Essa,LIQing2Hua1(2(
DepartmentofComputerScienceandTechnology,HuazhongUniversityofT,China)DepartmentofElectronicScienceandEngineering,NanjingU)
Abstract:ExtendedTTIGmodelandprithmcalledGBHA(group2basedhybridalgorithm).Inthiswork,ouralgorithmTsomewell2knownschedulingalgorithmsbasedonDAGinhomoge2.ThesineoussystemssuchonsmulationexperimentresultsandanalysisoftimecomplexityshowthatthisalgorithmousMATEgreatlyandcanbecomparabletoefficientschedulingalgorithmbased2onDAGbutwithasignificantlylowertimcomplexity.
Keywords:taskscheduling;list2scheduling;heuristics
1 引 言
快速有效的任务调度是并行与分布式系统中一个非常关键的问题,其算法的实质在于将任务映射至处理器,并重新排列任务的执行顺序,以符合任务优先权的要求并生成最小调度长度(schedulinglength).该问题在[2]中已被证明是NP难度问题,因此中外研究者在该领域已经进行了大量的研究.例如,表调度算法[1,7,8,11,13],基于群的调度[2,6],遗传算法[4,12],动态调度[5]等等.在这些算法中,表调度具有良好的成本22性能均衡性,在任务依赖关系 计算成本 通讯成本已知情况下,其调度性能优于动态调度算法.但是目前大多数调度算法都是基于DAG模型,而在该模型中,每个任务仅在任务开始及完成时才能与其它任务通讯,因而对于任务间反复交替计算及通信步骤这样一些问题并不十分有效.通常在DAG中处理这类问题的方式是从程序最内层的循环开始分解任务,并限定这些分解的子任务映射到相同的处理器,因此在DAG中将产生大量的顶点(在本文中图的顶点等价于任务),提高了调度的成本.在文献[10]中,提出了一种新的刻画任务依赖关系的模型22TTIG及相应的算法22MATE,从
而克服上述的DAG模型的缺陷.在该文中通过实验证明了
该算法的性能优于DAG模型中的ETF算法及PVM缺省的轮询算法.
本文延伸了TTIG模型,并提出了一种新的表调度算法:基于组的混合算法(GBHA).该算法首先以组为单位消除了TTIG中的回路,自底向上对任务排序,以期获得最小调度长度.模拟实验结果显示,该算法性能在绝大多数情况下,在同构计算环境中明显优于MATE,与基于DAG模型的调度算法比较而言,在性能方面针对任务的不同类型而各有千秋,但在算法时间复杂度方面具有显著的优势.
2 TTIG模型及MATE算法
2.1 TTIG模型
在文献[10]中,TTIG模型以一种更有效更实际的方式来描述并行程序.TTIG模型首先通过时态数据流图(TFG)来获取信息.TFG获取程序的全局行为,反映计算与通信的步骤和事件,并用一种简化的方法表达程序循环中的计算成本与通信成本,通过单步数据描述整个循环的稳定状态行为.这种简化策略的具体方法参见[9].
收稿日期:2003207209 基金项目:国家自然科学基金(60273075)资助. 作者简介:韩建军,男,1972年生,博士研究生,主要研究领域为并行分布式计算 调度算法;AbbasA.Essa,男,1966生,博士后,研究领域为网络计算;李庆华,男,1940年生,博士生导师,研究领域为并行算法 入侵检测.
一种灵巧同构系统的任务静态调度算法卢再奇,肖立,何峻,范红旗(国防科技大学电子科学与工程学院,湖南长沙410073)摘要:针对高性能的灵巧同构系统计算环境特点,提出了一...
因此,专门针对Join任务图,提出一个能产生最优调度的同构贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(v2),其中,v表示任务集中任务的个数。实验...
网格计算中一种改进的启发式任务调度算法_专业资料。网格计算技术是20世纪90年代... 网格计算中一种基于属性... 3人阅读 5页 2.00 树型网格计算环境下的...
基于任务复制的网格任务调度算法[1]_电脑基础知识_IT/计算机_专业资料。... 基于平均分配原则的任务... 同构计算环境中一种新的...1/2 相关文档推荐...
基于平均分配原则的任务调度算法[1]_信息与通信_工程科技_专业资料。... 基于任务复制的网格任务... 同构计算环境中一种新的...1/2 相关文档推荐...
因 此, 在一个开放的并行计算环境中, 迫切需要...2〕 12 调度算法模型 . 一种任务调度算法可定义为...“ 、同构” 等约束形式; ②对T G进 行约束 如...
第36卷第2期2013年2月 计 算 机 学 报 V01.36 No.2 CHINESEJOURNALOF...和环境参数等特征自动调节,导致调度 算法存在一定的局限性.文中提出一种面向同构...
(33) 9 一个新的基于通信竞争的任务调度算法杨 斌1, 张建军 2 YANGBin1,...同时, 适应同构计算环境的大量典 聚基 型的调度算法, 例如表调度、 集调度、...
有向图并行计算中一种新的结点调度算法_IT/计算机...(2)给出新调度算法的收敛性证明, 为新 算法提供...(莫则尧, 袁国兴, 消息传递并行编程环境 MPI. ...
本文提出了一种新的更加 有效的并行调度算法,该...相关任务图是将并行程序划分后得到的,在静态任务调 ...1 P , P2 ,∧ , Pp 全互连组成,且网络同构。...
热门文档