文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 电脑基础知识 > 同构计算环境中一种新的静态任务调度算法[2]
侵权投诉

同构计算环境中一种新的静态任务调度算法[2]

 第26卷第1期  2005年1月

小型微型计算机系统M

同构计算环境中一种新的静态任务调度算法[2]

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年生,博士生导师,研究领域为并行算法 入侵检测.

第1页

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email