论文研究-网格计算中任务调度研究综述.pdf

所需积分/C币:10 2019-07-22 19:39:23 48KB .PDF
收藏 收藏
举报

阐述了网格计算领域任务调度的特点和目标;综述了现有的任务调度技术和算法,包括启发性智能任务调度,基于Agent的任务调度,基于Petri网的任务调度,基于成本的任务调度等算法,以及任务调度的负载均衡问题,最后给出任务调度的研究展望。
18 计算机应用研究 2005年 |之间随机产生一个整数,作为交叉点,第三,交换从交叉点2.1.3遗传算法与蚂蚁算法的对比分析 开始的后半部分(包括交叉点),于是两个新的染色体就替代 文献[6]指出,遗传算法具有快速随机的全局搜索能力, 了它们的双亲。 但对于系统中的反馈信息利用却无能为力,当求解到一定范围 变异是一个确保发现最仹方案的穊率永不为零的基本操时往往做大量无为的冗佘迭代,求樻确解效率低。蚂蚁算法是 作。变异操作会改变一个染色体的某因。具体步骤是∶对每一通过信息索的累积和更新收敛于最优路径上,具有分布式并行 个染色体,先随机选择一个有变异可能的任务,j产生一个新全局搜索能力。但初期信息索匮乏,求解速度慢。 的PE值;再随机选择一个有变异可能的任务,并产生一个新 通过分析两个算法的优缺点,在实际设计网格仁务调度算 的优先级值 panty。这样,一个新的染色体就膂代∫原来的染法时,可以将遗传算法与蚂蚁算法融合,即采用遗传算法生成 色体。 信息素分布,利用蚂蚁算法求精确解,把两个算法的优势互补。 木义设计的算法日标是减少调度的跨度和所需P的个2.2基于 Agent的任务调度 数,并且消阶无效的仁务复制。 Agt技术源自」人工智能,其概念在60年代就凵提出 2.1.2基于蚂蚁算法( Ant Algorithm,AA)的网格任务调度 来,真正的发展在90年代,现在正向计算机领域的各方面渗 蚂蚁算法是一个新的启发算法,它是基于蚂蚁的行为。当 透⑦2。面向A9ent技术是面向对象技术的发展和飞跃,面向 妈蚁在了找食物时,每个走动的妈蚁都会在其经过的路上释放Agt的软件开发方法是为了更确切地描述复杂的并发系统 些信息素,那么在较短路径上的信息素会很快地增加,每条的行为而采用的一种抽象描述形式,与面向对象技术一样,它 路径上信息素的数量,会反怏山其他蚂蚁选择该路径的概率 是观察客观世界及解决问题的一种方法。面向A9rt技术为 最终,所有的蚂蚁将选择最短的賡径。蚂蚁算法圖有的并发性 复杂、开放、分布系统的丌发和实现提供了新途径。面向A9nt 和可扩充性,使它非常适合用丁阏格计算的任务调度。在同 技术的智能性、代理性、学习性、合作性、持续性使它非常适合 时间内,所有影响资状态的因素都能由一个事情,即信息索网格计算及其务调度的实现。基于Agrt的任务调度其基 描述。那么调度程序就能非常简单、快速地获得预测结果。 本设计思想是:将每个网格赘源节点均封裘成为一个 Agent,把 文献[11]设计了一个网格计算的鲇蚁仁务调度算法:当 网格系统看成是一种多层次A9t系统的集合。这样,所有分 资源j要加入到网格时,它应提交其性能参数,P序号、每个布于网格系统中不同地方的网将资源节点(如一个机群)就构 P的MPs( Mil lion instructi ons per secand)等。资源监控器为成∫底层的A9e系统,它们为基于k格的应用程序提供高性 了确认这些参数应对其进行测试,并对连接的信息素进行初始能计算能力,于是,调度问题被简化成如何在各A9t之间分 化:(0)=m·p+c/s 配计算任务并随吋根据Agt的变化情况进行调整,以及在各 其中,5(0)为资源j的初始信息素,m是PE的序号,P是一个Agrt内如何进行子任务的继续分配。这样的层次结构具有高 PE的MPs,c是参数的长度,9是从资源j到资源监控器的传度的可扩性,便于在网格这样的庞大异构环境运用12。 输时间。 文献[13]提出了一种基于 Agent的计算网格( Agent 每当岀现一个新资源加入到网格中、一个资源出现故障、 based Computational Grid, acc)任务管理方茱,给出了网格资 个任务被分配,或是有一些任务返回等情况时,从调度中心源的摧述,并设计了实现网格资源管理的三个网格协议原型 到相应资源路径上的信息素将会作如下变化: 服务登记协议,服务发现协议和服务访问协议。描述了它们的 构成要件及功能作用。该AG资源管理方案可为网格的计算 其中,Δ是从資源监控都到资源)路径上信息素的变化值;资源和服务提供一个统一的高层管理框架 是持久的信息素(0≤≤1):1p是挥发掉的信息素。 当任务被分配到资源j以后,A;=-KK是在该任务的2.3基于Pet网的任务调度模型 计算和传输质量。 Pe网理论是由德国的 Car adam pe博士提出的,主要 当任务成功地从资游j返回时,△-y=Ce·K,Ce是鼓励因究分布式系统中并发冲突象的一种理论,它描述和分 忻离散事件动态系统的一和模型工具。它综合了数据流、掉制 当任务从資源j失败返回时,△=Cp·K,C是惩罚因 流和状态转移,能自然地描述)发、同步、资源争用等系统特 性,而且本身自含执行控制机制,集规范表示与执行于同一模 在t时刻,任务被分配到每个仁务上去的概率可表示为 型。同时,Pei阏是严格定义的数学对象,借助敚学廾发的 t)]·[nJ° Pei网分析方法和技术,既可用于静态的结构分析,乂可用于 PiCt d[τ(t)]2·[ηd U∈在线资源 动态的行为分析1 其他 文献[15]提出了一个可用于网格计算任务调度的高级时 其中,(切是在t时刻从调度中心到资源j路径上的信息素。间P网( Extended High-Leve Timed Petri Net, EHLTPN)模 η;是资源j的先天的性能,也即τ0)。 型。在该模型中,分配给转移的点火吋间是输入库所Tαkes r(t)是在t时刻从调度中心到资源路径上的信息素。的函数。木文利用团LFN构造了一个网格计算的任务调度 是资源凵先天的性能,也即τ(0)。 的简单模型,并定义了一个 EHLTPN的可达调度图( Reachable x是信息素的杈重。β是资源先天属性的权重。 Scheduling Graph,RSG用来分析任务调度的时间特性。 本文验证了妈蚁算法的可扩機性,提出了一个简单的资源2.4基于成本的任务调度 管理和仁务调度的网格仿真结构 文献[16]在经济原则的基础上为调度问题引入了成本 第5期 罗红等:网格计算中任务调度研究综述 9 (Cost)概念。其核心思想是把诸如U、存储器、带站等不同参考文献 美型资游的使用情况都转变成单一的成本,并按照总成本最小[1]刘忠中网格计算及其技术需求分析[].江西通信科技,2003, 化的目标,对刚格系统中的任务进行调度。为此设计了终通 (2):36-40 信成木函数、①PU成木函数、存储器成木函数。当一个新任务[2lman, NP-Complete Scheduling problems. Jaarnal of Campu 到达后,分别计算相应的成函数为该任务选择一个成本最低 ter and Syst. Sciences, 1975, 10: 384-393 [3 Andoni kos T, Koziris N Optima Sceduling for UET-UCT Grids Into 的主机进行调度。 Fixed Number of Processors C]. Parallel and Distributed Processing 2.5任务调度中的负载均衡 2000 Proceedings, 8th Euromicro Workshop on, 2000. 237-243 [4]查礼,徐志伟,林国璋,等,基于 Sigrid的网格任务调度模拟 文献[17]中提出了一个基于 Agent的冈格管理基础设施, [].计算机工程与应用,2003(14):90-92. 它连接着一个性能驱动的任务调度器,开发该调度器是为了平[5]刘家壮,徐源网络最优化[M]北京高等教育出版社,1991 衡本地网格负载。每个网格调度器都使用可预測的应用性能[6丁建立陈增强,袁者祉.遗传算法与蚂蚁算法的融合[]·计算 数据和迭代启发算法;通过多处理节点达到本地负载平衡。在 机研究与发展,2003,40(9):1351-1356 [刁]陈国良.遗传算法及其应用[M].北京:人民邮电出版社,1996 史高层次上,利用同种Agrt的层次结构代表多网格资源。同[8] Wensheng Yao,a. Genetic Scheduling on Minimal Processing ele- 吋,通过使用服务广告和发现机制,Aget之间相互协作,从而 ments in the grid[ M]. Springer-Verlag Heide berg, 2002 平衡仝局网格的负载。文中还给出了研究例子和相关的实 [9 Di Martinov, et al. Scheduling in a grid Computing Environment U 结果,表明通过本地调度器和其他的Aget共同协作,可对全 sing Genetic algori thms[ C]. Parallel and Distributed Processing Symposium, Proceedings International IPDPS, 2002. 235-239. 局的阏格负载进行平衡,也显著地提高∫网格执行性能和资源[10] Di Matino v. Sub Optimal Schedul ng in A grid Using genetic al g 利用率 rithms[ c]. Parallel and Distributed Processing Symposium, 2003 148-154 2.6其他任务调度算法 [11 Zhihong Xu, Xiangdan Hou, Jizhou Sun. Ant Algaithmrbased Task 除了上述调度算法之外,人们还提出了很多异构系统的启 Schedul ing in Grid Computing[C]. IEEE CCECE, 2003 发调度算法,有不少论文试图把这些算法用于网格环境。文献[12]张颖峰,李毓麟基于进化算法的网格计算资源管理调度系统 [18]提出了一个扩展的 Suffrage,叫 Xsufferage,可在网格环境 [].计算机工程,2003,29(15):110-175. [13]李春林,卢正鼎,李腊元·基于 Agent的计算网格资源管理[J 中调度叁数扫描应用。文献[19]提出了一个期限调度策略, 武汉理工大学学报(交通科学与工程版),2003,27(1):7-10 可适用于多客户多服务器( Mult-Client multi-server)方式,并[14]袁崇义Pe网原理[M].北京:电子工业出版社,198 增加了能够改进算法性能的负载纠错( Load corection和退却 [15 Yaojun Han et a/. Resource Scheduling algorithms for Grid Compuh ting and Its Modeling and analysis Using Petri Net[ C]. Shanghai ( Fall back)机制。文献[20]提出∫利用不同站点多同时请求 The 2nd Internationa Workshop on grid and Cooperati ve Computing 的分布调度算法。文献[21]提出了主人-工人( Master-Wa 2003 ke)应用的调度策略,该策略能动态地检测任务的执行时间,[16] Chuliang WengⅪ Kinda lu.ACst-bεed。 n-line Scheduling Alφ 并利用这个信息去动态地调整工人的数量,从而取得一个理想 rithm for Job Assi gment on Camputati nal Grids[ M]. Springer-Ver l ag Heidelberg, 2003. 的工效 17 Junwei Cao, Daniel P sponer, et a/ Agent-based Gnd Load Balan- cing Using Performance-driven Task Scheduling[ c]. Intemational 3研究展望 Parallel and Distributed Processing Symposium, 2003. 49-58 [ 18] Casanova H Legrand, a Zagorodnov D Berman. Heuristics for Sche- 任务调度是网格计算的基木功能,它面临的问题是一个 duling Parameter Sweep Applications in Grid Envronments[ C] NP完元仝间遨。到日前为止,人们湜出了很多网格系统的调度 Proceedings of the 9th Heterogeneous Computing Workshop, IEEE 技术和算法。但是,不少调度算法还没有完整的理论依据、 LaA| amigos,2000.349-363 [19] Takefusa, A Casanova, Et al. a Sudy of Deadli ne Scheduling for 此调度技术的结论还只是来自仿真结果,至个还没有形成网格 Client-Server Systems on the Coputainal Grid[ c]. Proceedings of 计算的任务调度理论。因此,该领域的研究还有待进一步发展 the l0th IEEE Intemational Symposium on High Performance Distri 和完普。只体地说,今后还要做的工作是: buted Computing, IEEE, Los alamitos, 2001. 406-415 (1)仁务调度算法矿究的粒度需要进一步细化。目前不 Grids Using Multiple Simul taneous Requests[ C]. Proceedings of the 少算法研究资源和任务是粗粒度的,一些调度思想还处」初步 11 th IEEE Internationa Symposium on High Perf armance Distributed 的原型阶段,离具体实现还有较大距离 Computing, IEEE, Los Alamitos, 2002. 359-367. (2)启发性智能化方法将是网格计算任务调度的一个重[21] Heyman E Senar, M A Luque,ea., Adaptive Scheduling for Mas- 要研究领域。前启发性冮务调度算法的硏究还处于模拟仿 ter-worker applications on the Computationa Grid[ M]. springer- ∨ er ag heidelberg,2000 真阶段,还需要在理论和实践中不断完产 [22]崔燕妮.面向 Agent的理论与应用[]].云南师范大学学报,2002 (3)面向 Agent技术将是网格计算及其仁务调度的一个重 22(3):11-14 要的软件开发方法,在该领域同样还有很多工作要做。 作者简介 (4)网格系统中的信息安全离不廾任务调度的攴持。也罗红(193-),男,副教授博士生,主要研究方向为分布式系统、网格 就足说,网格任务调度系统必须具有一定的安全机制,以便为计算等;德俊(1963),男,数授,博士生导师,研究方向为并行处理 网络安全等;邓智群(1976-),男,博士生,主要研究方向为信息安全、 网格提供安全可靠的任务调度服务。目前,安全任务调度技术网格计算等;王晓东(1974-),男,博士生,主要研究方向为分布式处理 有待进一步研究 技术、网络管理等。

...展开详情
试读 4P 论文研究-网格计算中任务调度研究综述.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    上传资源赚积分,得勋章
    最新推荐
    论文研究-网格计算中任务调度研究综述.pdf 10积分/C币 立即下载
    1/4
    论文研究-网格计算中任务调度研究综述.pdf第1页
    论文研究-网格计算中任务调度研究综述.pdf第2页

    试读已结束,剩余2页未读...

    10积分/C币 立即下载 >