文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 元计算环境下支持依赖任务的OGS算法研究
侵权投诉

元计算环境下支持依赖任务的OGS算法研究

一个应用程序只有经过分解,产生若干任务后才能在元计算系统上调度和运行,论文提出了基于DAG的,优化的分代任务调度算法OGS,该算法为每个DAG结点指派一个固定优先数,根据优先数过滤出互不依赖的任务,然后对这些独立任务使用先辈算法进行调度,OGS算法不仅考虑机器就绪时间,还考虑每个任务全部先导的完成时间,这样可以减少全部参与调度的节点的空闲时间,从而优化Makespan,实现表明,OGS算法的性能优于GS和Beam算法。

维普资讯 doc.guandang.net

第2 5卷

第6期

计

算

机

学

报

V o1 25 N o. 6 .

20 0 2年 6 月

CHI NES E J CoM PU TERS

J n 0 2 u e 2 0

元计算环境下的支持依赖任务的 O S算法研究 G 桂小拣 摘要

钱德沛

(西安交通大学计算机科学与技术系西安 7 0 4 ) 1 0 9

一十应用程序只有经过分解。生若干任务后才能在元计算系统上调度和运行.产论文提出了基于 DA G

的、优化的分代任务调度算法 OG . S该算法为每个 D AG结点指派一个固定优先数,根据优先数过滤出互不依赖的 任务,后对这些独立任务使用先辈算法进行调度 . GS算法不仅考虑机器就绪时间,考虑每个任务全部先导的然 O还

完成时间.这样可以减少全部参与调度的节点的空闱时间,从而优化 Ma epn实验表明, G ksa. O S算法的性能优于 G S和 B aa算法 . er

关键词

映射与调度,启发式算法,依赖任务,元计算系统,异构系统

中围法分类号: T 3 1 P 0

OG S Al o ihm o a p ng De nd ntTa ks g rt f r M p i pe e s t e a o pu i n i o oM tc m tng E v r nm e nt

G I a— i QI N De P i o Ln xi A — e D p r n o p t S i tⅡ Teh oo y-。 J a tn ie sytXi e a t t f C m u ̄ c ̄ c me o e c n l g XiⅡ ioo g Unv ri t 7 0 4 10 9

Ab t a t s r c

An a p ia i n mu t b e o p l t c o s e d c mp s d i t o e t s s ( r s b a k )t e e e u e n o e n o s m a k o u t s s o b x c t d i

me a y t ms I h s s u y,a p i l g n r to c e u i g ( t s se . n t i t d n o tma e e a i n s h d l n OGS) a g rt m s i to u e . lo i h i n r d c d Fis,t e ag rt m s i n i e ro i o a h t s . I,t e r t h l o ih a sg s a f d p ir t f r e c a k x y t h

n,f t r u l i d p n e t i e s o tal n e e d n l t s s a c r i g t h a e p i rt . Fi a l a k c o d n o t e s m ro iy n l y,i ma s t e e i d p n e t t s s t l m a h n s t p h s n e e d n a k o al c ie a a l b e u i g s me h u it s b o e u n r o o p rs n I v i l s n o e rs i y f r r n e s f r c m a io . n OGS Al o ih,e p c R a c g rt m x e tm— c i e r a y tme i u e h n e d i s s d,t e c mp e i n tme fa l r d c s o s a e as o s d r d a e r t h o l t i s o l p e e e s r r lo c n i e e s h u i i o s c if r ain n o m to .S o,il i e n ma h n s c n b e r a e d et m s i c i e a e d c e s d,a d t e M a e p n t e e i r v d n h k s a h n b mp o e . By t s,i i e e t t s d mo s r t d t a h e f r n e o n ta e h tt e p r o ma c fOGS e c e s GS a g rt ms x e d l o ih .

Ke wo d y rs Sys em t

ma p n n c e u i g,h u i t s,d p n e t t s p ig a d s h d l n e rs i c e e d n a k, me a y t m,h t r g n o s t s se ee o e e u

构均一系统上调度的例子 .关于依赖任务在异构系

1引

言

统上调度的典型算法是分代算法 ( nrt nAlo Geeai g— o r h, ),.文基于 G i ms GS Ea论 t z。 S算法的基本思路,提出了基于优先数过滤的、持依赖任务的、化的分支优代调度算法 OGS Opi l S . GS算法不同的 ( t )与 ma G是: S不只考虑机器就绪时间,考虑每个任务 OG还全部先导的完成时间.样可以减少全部参与调度这

在广域异构的元计算系统上开发优他的任务调度算法是 N— P HAR的, D

因此必须提出一些启发 式调度算法来获得最优或近优解.有的启发式调现度算法大多是基于独立任务的,有依赖任务在同也

收穑 E期: 0 10 8修改稿收到日期: 0 11—3奉课题得到国家“六三高技术研究发展计划项目( 0 1 l 2 0 52{ 2 0 20八 2 0AAI 18}6—0一 I 0 1 8 33 6

Z O 62资助和西安交通大学行动计划项目资助挂小林, 1 6年生, T l0—)男, 9 6博士研究生,副教授 究兴趣为新型网络计算技术和网培研安全技术 E m【 x u j .d .n戡德沛 . .9 2侧, l i t euc g@x u男 1 5年生 .授,教博士生导师,目前研究*趣为高性能计算机体系结构和计算机网 络新技术

元计算环境下支持依赖任务的OGS算法研究

第1页

你可能喜欢

热门文档

相关文档

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