（计算机科学与技术专业论文）an+algorithm+for+task+scheduling+in+a+heterogeneous+computing+environment.pdf

a na l g o r i t h mf o rt a s ks c h e d u l i n gi nah e t e r o g e n e o u s c o m p u t i n ge n v i r o n m e n t b y t e k l a yt e s f a z g h iy i f t e r b s c ( u n i v e r s i t yo fa s m a r a ，e r i t r e a ) 1 9 9 6 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g c o m p u t e ra p p l i c a t i o n i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rl ik e n l i m a r c h ，2 0 11 硕士学位论文 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 己在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：七啦。哆、 日期：盘p f f 年4 月舀日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在 年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签 导师签 日期：加l r 年年月6 日 日期：扣t t年4 月日 a na l g o r i t h mf o rt a s ks c h e d u l i n gi na h e t e r o g e n e n 璐c o m p u t i n ge n v i r o n m e n t a c k n o w l e d g e m e n t s 1w o u l dl i k et ot h a n km ya d v i s o r ，p r o f e s s o rl ik e n l i ，o ft h es c h o o lo f i n f o r m a t i o ns c i e n c ea n de n g i n e e r i n ga th u n a nu n i v e r s i t y ，f o rh i sa d v i c e ， e n c o u r a g e m e n t ，a n ds u p p o r t ia mi nd e b to fm a n y p e o p l ef o rt h e i rs u p p o r tf o rw r i t i n gt h i st h e s i s i ti sa n h o n o rf o rm et o t oh a v et h es u p p o r ta n de n c o u r a g e m e n tf r o mm yf r i e n d s o k b a m i c h a e l ，t e s f a l i d e t ，h u m p h r e y ，b e nm i n gf e n ga n do t h e r sw h o1w o r k e d w i t hi nt h ec o m p u t e r 1 a bo ft h eh u n a nu n i v e r s i t y 1w a sg e t t i n gt h eh e l pa n d s u p p o r tw h e n e v e r1w a si nn e e do fo n e p e o p l ew h om a d em ys t a yi nc h i n ap l e a s u r a b l ea r en o tt ob ef o r g o t t e n s p e c i a lt h a n k st of o r e i g no f f i c ef o rt h e i rs u p p o r t m a n yt h a n k st oa l lf o r e i g n s t u d e n t sa th u n a nu n i v e r s i t y t h a n ky o ua 1 1 a d d i t i o n a l l y ，1w a n tt ot h a n km yp a r e n t s ，m yb r o t h e r sa n ds i s t e r sf o rt h e i r u n r e s e r v e ds u p p o r ti nm a n yk i n d so fw a y s a n df i n a l l y ，im u s tt h a n km yd e a rw i f ef o rh e rl o v ea n dt a k i n ga l lt h e r e s p o n s i b i l i t yo fo u rb e l o v e dt w os o n sa l la l o n e ，s ot h a tm ys t a yh e r ei nc h i n ah a s b e e nf u l l yd e d i c a t e dt om ys t u d y 硕士学位论文 a bs t r a c t g r i dc o m p u t i n gh a sb e e nu n d e rr e s e a r c hs t a r t i n gf r o ml a t e1 9 8 0 s n o wi th a s b e c o m eav e r yi m p o r t a n tc o m p u t i n gp a r a d i g me s p e c i a l l yf o rp r o b l e m sr e l a t e dt o s c i e n c e ，e n g i n e e r i n g ，b u s i n e s s a n do t h e rf i e l d sw h i c hr e q u i r ea ni n t e n s i v e c o m p u t a t i o n t h e r ee x i s tm a n ys y s t e m sw h i c he m p l o yg r i dc o m p u t i n gw i t hal o t o fs u c c e s s b u ta sg r i dc o m p u t i n gc r e a t e sa v e r yp o w e r f u lc o m p u t a t i o n e n v i r o n m e n ti ta l s ob r i n g sm a n yc h a l l e n g e s ，w h i c hn o r m a l l yd on o te x i s ti nt h e t r a d i t i o n a lw a yo fc o m p u t i n g a m o n gt h ec h a l l e n g q s ，a n dm o s ti m p o r t a n t ，i s s c h e d u l i n g h o wt od i v i d et h eb i gp r o b l e mi nt os u bp r o b l e m s ( s u bt a s k s ) a n d a s s i g nt h es u bp r o b l e m s ( s u bt a s k s ) i nt ot h em a n yc o m p u t a t i o nd e v i c e s ，w h i c h f o r mt h eg r i dc o m p u t i n gs y s t e m ，i sac h a l l e n g e s ot h ep r o b l e mo fs c h e d u l i n g c o m e sa sav e r yi m p o r t a n tc h a l l e n g et h a tm u s tb ed e a l tw i t h ，s ot h a t ，t om a k et h e w h o l eg r i dc o m p u t i n gs y s t e mas u c c e s s t h em a t c h i n go ft a s k st om a c h i n e sa n d s c h e d u l i n gt h ee x e c u t i o no r d e ro ft h e s et a s k si sr e f e r r e dt oa sm a p p i n g t h ep r o b l e mo fm a p p i n gi n d e p e n d e n tt a s k si nt o h e t e r o g e n e o u sc o m p u t i n g s y s t e m ss ot h a tt h ec o m p l e t i o nt i m eo ft h el a s tf i n i s h i n gc o m p u t i n gs y s t e m ， c a l l e dm a k e - s p a n ，i sm i n i m u mh a v eb e e np r o v e dt ob en p c o m p l e t e a sar e s u l t m a n yh e u r i s t i c se x i s ti nt h el i t e r a t u r ef o rs o l v i n gt h i sp r o b l e m a m o n gt h e m ，t h e a l g o r i t h m sh l t f ( t h eh e t e r o g e n e o u sl a r g e s tt a s kf i r s t ) a n ds e g m e n t e d m i n m i nh a v eb e t t e rm a k e s p a n sw i t hl o w e r c o m p l e x i t i e s h e r ei nt h i sp a p e r ，w eh a v ed e v i s e dan e wh e u r i s t i cc a l l e dh e t e r o g e n e o u s p r i o r i t yf o ra v o i d a n c eo fl a r g e s tp e n a l t y ( h p a l p ) w h i c hi m p l e m e n t st h e h e u r i s t i c si nh l t fa n ds e g m e n t e dm i n - m i nb y a d d r e s s i n gt h ep r o b l e mo f h l t f sl a c k o ft a k i n gi nt oc o n s i d e r a t i o nt h eh e t e r o g e n e i t yo fm a c h i n e sa n d s e g m e n t e dm i n m i n sn o th a v i n g ac l e a r c u t s e g m e n t s b a s e do nt h e h e t e r o g e n e i t yo fm a c h i n e s t h en e wp r o p o s e dh e u r i s t i ca n ds e v e r a lr e l a t e do n e s h a v eb e e n i m p l e m e n t e do n as i m u l a t e d h e t e r o g e n e o u sc o m p u t i n g ( h c ) e n v i r o n m e n tw h i c hi sb a s e do ns i m j a v a ，t h ee x p e r i m e n t a lr e s u l t ss h o wt h a to u r h e u r i s t i co u t p e r f o r m st h et r a d i t i o n a lo n e s k e y w o r d s ：h e u r i s t i c ；s c h e d u l i n g ；m i n m i n ；h l t f ；h a s s ed i a g r a m u l 一 a na l g o r i t h mf o rt a s ks c h e d u l i n gi nah e t e r o g e n e o u sc o m p u t i n ge n v i r o n m e n t 摘要 网格计算一直到8 0 年代后期开始研究。现在它己成为一个非常重要的计算 模式，尤其是有关科学，工程问题，企业和那些需要密集计算等领域。存在许多 成功应用网格计算的系统。网格计算创建了一个非常强大的计算环境，同时也带 来了许多挑战，通常在平常的计算方式中是不不存在的。其中最大的问题是调度。 如何把一个大的问题划分成小的问题并且分配到网格计算系统的各个计算终端上 就是网格计算系统所管理的。因此，调度的问题就成了非常重要的挑战，如果这 个问题解决得话，那么整个的网格计算系统就能成功的运行。 映射独立任务到异构计算系统，到整个系统中最后完成得任务所需要的时间 就是所谓的跨度，这是已经被证明的n p 一完全问题。因此，许多文献中存在解 决这个问题的启发式算法其中，h l t f ( t h eh e t e r o g e n e o u sl a r g e s tt a s kf i r s t ) 和 s e g m e n t e dm i n m i n 有较好的低复杂度的跨度。在这份文件中。我们提出 h e t e r o g e n e o u sp r i o r i t yf o ra v o i d a n c eo fl a r g e s tp e n a l t y ( h p a l p ) 算法，它通过解 决h l t f 在异构计算环境中的问题和在异构的计算环境中s e g m e n t e dm i n - m i n 没有一个清晰的分段来实现在h l t f 和s e g m e n t e dm i n m i n 中的启发式。新提 出的启发式和几个相关的已在基于s i m j a v a 的模拟异构计算( h c ) 的环境中实 现，实验结果表明，我们的启发式算法比传统的算法性能更优 关键词：启发式；调度；最小化；高级别工作队：h a s s e 图 乃b l eo fc o n t e n t s a c k n o w l e d g e m e n t s a b s t r a c t a b s t r a c t i i 卜c h i n e s e p a g e 1 1 i n t a b l eo fc o n t e n t 8 v l i s to ft a b l e s v i i l i s to ff i g u r e s v i i i c h a p t e r 1i n t r o d u c t i o n 1 1 1g r i dc o m p u t i n g 1 2 t y p e so fg r i d s 1 2 1 c o m p u t a t i o n a lg r i d s 1 2 2 s c a v e n g i n gg r i d s j 1 2 3e s c i e n c eg r i d s 1 2 4 d a t ag r i d s 1 2 5 e n t e r p r i s eg r i d s ： 1 3 h e t e r o g e n e o u sg r i dc o m p u t i n g 1 4 s c h e d u l i n g ：a ni m p o r t a n tg r i dm e c h a n i s m 1 5t y p e so fs c h e d u l i n gi ng r i d s 1 5 1 i n d e p e n d e n ts c h e d u l i n g 1 5 2g r i dw o r k f l o w s 1 5 3c e n t r a l i z e d h i e r a r c h i c a la n dd e c e n t r a l i z e ds c h e d u l i n g 1 5 4s t a t i cv s d y n a m i cs c h e d u l i n g 1 5 5i m m e d i a t ev s b a t c hm o d es c h e d u l i n g 1 5 6 a d a p t i v es c h e d u l i n g 1 5 7e c o n o m y - b a s e ds c h e d u l i n g 1 6o u rp r o p o s a l 2 c o m p u t a t i o nm o d e l s 2 1 e x p e c t e dt i m et oc o m p u t em o d e l 2 2 m o d e l i n gh e t e r o g e n e i t ya n dc o n s i s t e n c yo fc o m p u t i n g 2 3s o m ee x i s t i n gh e u r i s t i c s 2 4e t cm a t r i xc h a r a c t e r i z a t i o n 3 i n t r o d u c i n gh a s s ed i a g r a m 3 1d e f i n i t i o n s 3 2h a s s ed i a g r a m 3 2 1 u s a g eo fh a s s ed i a g r a mi no u rh e u r i s t i c 4o u rn e wh e u r i s t i cf o rt 缸ks c h e d u l i n gi nh e t e r o g e n o u se n v i r o n m e n t s 4 1 t p d $ m i n c t m i n c t 4 2o u rp r o p o s e dh p a l ph e u r i s t i c ： 4 2 1h p a l ph e u r i s t i cd i s c u s s e di nd e t a i l v ，i_，_，llj，_j，ij 1 l ，i j 1 1 1 2 2 2 3 3 3 4 4 4 5 5 6 6 6 7 8 8 8 9 1 3 3 3 3 5 与占与 5 6 4 1 4 2 4 3 4 4 4 5 5 1 5 2 5 3 5 4 5 5 5 6 l i s to ft a b l e s s a m p l ee t c m a t r i x c a l c u l a t e dd i f f e r e n c ev e c t o r s c tm a t r i xa f t e rt a s k0i sm a p p e do nt om a c h i n e3 c tm a t r i xa f t e rt a s k s3 1a n d7a r em a p p e d c tm a t r i xa f t e rt a s k s5 , 4a n d2a r em a p p e d s i m u l a t i o nr e s u l t s ( 1 0m a c h i n e s ，k n s k = 0 1 ，= o 1 ) ( 1 0m a c h i n e s ，s k = 0 8 ，= o 1 ) ( 1 om a c h i n e s ，七= o 8 ，= o 8 ) ( 5 0m a c h i n e s ，j k = 0 1 ，= o 1 ) ( 5 0m a c h i n e s ，f k = 0 8 ，= o 1 ) 。 ( 5 0m a c h i n e s ，k = 0 8 ，= o 8 ) v 1 1 竹坞硌均均 弱弱艏船舶弱 2 1t h em i n r a i nh e u r i s t i c 1 0 2 2t h es e g m e n t e dr a i n m i nh e u r i s t i c 1 1 4 ，lt h et p d f m i n c t m i n c th e u r i s t i c 4 2t h eh p a l ph e u r i s t i c 4 j 3 h a s s e d i a g r a m 一1 。，。，。 4 4 h a s s e _ d i a g r a m _ 2 4 5 h a s s e _ d i a g r a m _ 3 4 6t a s k st om a c h i n e sm a p p i n gu s i n gm i n m i n 4 7 m a p p i n gu s i n gs e g m e n t e dm i n - m i n ( 3s e g m e n t s l 4 8 m a c h i n e sm a p p i n gu s i n gs e g m e n t e dm i n - m i n ( 2s e g m e n t s ) 4 9 m a p p i n gu s i n gt p d $ - m i n c t - m i n c t 一 4 1 0m a p p i n gu s i n gh p a l p 4 11g e n e r a t i n gt h er e l a t i o nm a t r i xc o r r e s p o n d i n gt ot h eh a s s ed i a g r a m 5 1t h eg e n e r a lc o y - b a s e dm e t h o df o rg e n e r a t i n ge t cm a t r i c e s 。 2 3 蝣拍坞均玛加加虹殂勉 c h a p t e r1 i n t r o d u c t i o n 1 1g r i dc o m p u t i n g g r i dc o m p u t i n ga n dg r i dt e c h n o l o g i e sh a v ep r i m a r i l ye m e r g e df o rs c i e n t i f i ca n dt e c h n i c a l w o r k ，w h e r eg e o g r a p h i c a l l yd i s t r i b u t e dc o m p u t e r s ，l i n k e dt h r o u g hi n t e r n e t ，a r eu s e dt o c r e a t ev i r t u a ls u p e r c o m p u t e r so fv a s ta m o u n to fc o m p u t i n gc a p a c i t ya b l et os o l v ec o m p l e x p r o b l e m sf r o me s c i e n c ei nl e s st i m et h a nk n o w nb e f o r e h o wt om a k eu s eo fm i l l i o n so fc o m p u t e r sw o r l d - w i d e ，r a n g i n gf r o ms i m p l el a p t o p s ，t o c l u s t e r so fc o m p u t e r sa n ds u p e r c o m p u t e r sc o n n e c t e d t h r o u g hh e t e r o g e n o u sn e t w o r k si na n e f f i c i e n t ，s e c u r ea n dr e l i a b l em a n n e r ? t h et e r mg r i di sa d o p t e dt od e s i g n a t eac o m p u t a t i o n a li n f r a s t r u c t u r eo fd i s t r i b u t e d r e s o u r c e s ，h i g h l yh e t e r o g e n e o u s ( a sr e g a r d st h e i rc o m p u t i n gp o w e ra n da r c h i t e c t u r e ) ，i n - t e r c o n n e c t e db yh e t e r o g e n e o u sc o m m u n i c a t i o nn e t w o r k sa n db ya m i d d l e w a r et h a to f f e r s r e l i a b l e ，s i m p l e ，t r a n s p a r e n t ，e f f i c i e n ta n dg l o b a la c c e s st ot h e i rp o t e n t i a lo fc o m p u t a t i o n t h er o o t so fg r i dc o m p u t i n gc a nb et r a c e db a c kt ot h el a t e1 9 8 0 sa n dt h ef i r s tc o n c e p t t h a tl a i dt h eb a s i so ft o d a y sg r i ds y s t e m sw e r ed e v e l o p e db yr e s e a r c h e r sf r o md i s t r i b u t e d s u p e r - c o m p u t i n gf o rn u m e r i c a lo ro p t i m i z a t i o nw i t hp a r t i c u l a re m p h a s i so ns c h e d u l i n g a l g o r i t h m st oa c h i e v eh i g hp e r f o r m a n c ec o m p u t i n g ( e g c o n d o r - g ) b yt h el a t e1 9 9 0 s ，t h e t e r mo fc o m p u t a t i o n a lg r i d sa n dg r i dc o m p u t i n gw e r ep o p u l a r i z e db yf o s t e re t a 1 【3 】 w h od e v e l o p e dt h eg l o b u st o o l k i ta sag e n e r a lm i d d l e w a r ef o rg r i ds y s t e m s s i n c et h e n ， g r i dc o m p u t i n g ，g r i ds y s t e m sa n dg r i dt e c h n o l o g ya r ea d v a n c i n gi nu n s t o p p a b l ew a y ! 1 2 t y p e so fg r i d s g r i dc o m p u t i n gs y s t e m sa r ea b o u ts h a r i n gc o m p u t a t i o n a lr e s o u r c e s ，s o f t w a r ea n dd a t aa t al a r g es c a l e t om a k et h eg r i dc o m p u t i n gf u l l yb e n e f i c i a lt or e s e a r c h e r s ，p r a c t i t i o n e r s ， a c a d e m i aa n di n d u s t r y , t h e r ea r es t i l lp l e n t yo fi s s u e st od e a lw i t ha n d c u r r e n t l yr e s e a r c h e r s a r ev e r ya c t i v e l yi n v e s t i g a t i n g o n es u c hi s s u ei st h e p e r f o r m a n c er e q u i r e m e n to nt h er e s u l t i n gg r i ds y s t e mo rt h ev i r t u a lg r i d - e n a b l e ds u p e r c o m p u t e r a c h i e v i n gh i g hp e r f o r m a n c e g r i dc o m p u t i n gr e q u i r e st e c h n i q u e st oe f f i c i e n t l ya n d a d a p t i v e l ya l l o c a t ej o b sa n da p p l i c a - t i o n st oa v a i l a b l er e s o u r c e si na l a r g es c a l e ，h i g h l yh e t e r o g e n e o u sa n dd y n a m i ce n v i r o n m e n t a st h ea p p l i c a t i o no fg r i da r ew i d er a n g e dt h e r ea r ed i f f e r e n tt y p e so fg r i d s 1 2 1 c o m p u t a t i o n a lg r i d s o n eo ft h ef i 、r s tq u e s t i o n sr a i s e db yt h i se m e r g i n gt e c h n o l o g yi si t su t i l i t yo rt h en e e do f d i s p o s i n gc o m p u t a t i o n a lg r i d s t h e r ee x i s tm a n yp r o b l e m st h a tc h a l l e n g eo re x c e e do u r a b i l i t yt os o l v et h e m ( i ns c i e n t i f i c ，e n g i n e e r i n g ，b u s i n e s s ，p e r s o n a l ，e t c ) ，t y p i c a l l yb e c a u s e t h e yr e q u i r ep r o c e s s i n gal a r g eq u a n t i t yo fo p e r a t i o n so rd a t a i ns p i t eo ft h ef a c tt h a t t h ec a p a c i t yo ft h ec o m p u t e r sc o n t i n u e si m p r o v i n g ，t h ec o m p u t a t i o n a lr e s o u r c e sd on o t r e s p o n dt ot h ec o n t i n u o u sd e m a n df o rm o r ec o m p u t a t i o n a lp o w e r o nt h eo t h e rh a n d ，s t a t i s t i c a ld a t as h o wt h a tc o m p u t e r sa r eu s u a l l yi n f r a u t i l i z e d m o s t o fc o m p u t e r sf r o mc o m p a n i e s ，a d m i n i s t r a t i o n ，e t c a r em o s to ft h et i m ei d l eo ra r eu s e df o r b a s i ct a s k st h a td on o tr e q u i r et h ew h o l ec o m p u t a t i o np o w e r o n eo ft h em a i no b j e c t i v e s o ft h eg r i dt e c h n o l o g yi s ，t h e r e f o r e ，t ob e n e f i tf r o mt h ee x i s t e n c eo fm a n yc o m p u t a t i o n r e s o u r c e st h r o u g ht h es h a r i n g a s p o i n t e do u tb yf o s t e ra n dk e s s e l m a n 【3 】t h es h a r i n gt h a t w ea r ec o n c e r n e dw i t hi sn o tp r i m a r i l yf i l ee x c h a n g eb u tr a t h e rd i r e c ta c c e s st oc o m p u t e r s ， 1 2 2 s c a v e n g i n gg r i d s i nas i m p l ec o m p u t a t i o n a lg r i d ，s u c ha su n i t e dd e v i c e s ，t h ep o l i t i c so fs c a v e n g i n gi sa l - p l i e d t h i sm e a n s ，e a c ht i m ea m a c h i n er e m a i n si d l e ，i tr e p o r t si t ss t a t et ot h eg r i dn o d e r e s p o n s i b l ef o rt h em a n a g e m e n ta n dp l a n n i n go ft h er e s o u r c e s t h e n ，t h i sn o d eu s u a l l y a s s i g n st ot h ei d l em a c h i n et h en e x tp e n d i n gt a s kt h a tc a l lb ee x e c u t e di nt h a tm a c h i n e s c a v e n g i n gn o r m a l l yh i n d e r st h eo w n e ro ft h ea p p l i c a t i o n ，s i n c ei nt h ee v e n tt h a tt h ei d l e m a c h i n ec h a n g e si t ss t a t et ob e b u s yw i t ht a s k sn o tc o m i n gf r o mt h eg r i ds y s t e m ，t h e a p p l i c a t i o ni ss u s p e n d e do rd e l a y e d t h i ss i t u a t i o nw o u l dc r e a t ec o m p l e t i o nt i m e sn