ѧ
JOURNAL OF SOFTWARE
1999ꡡ1011ڡVol.10No.111999



ʽеĴѡ
»ƽ
ժҪǲзֲΪΪؼ,ҲսԵ֮һ,Ӱ첢зֲִЧʵһؼ.еĻ̬ȼʽȷԡǰʼִʱ̡ΪĿѡִд.ϸ۸ֵȷĻ,ָԸĿѡڵ⼰ȱ,ԡǰֱӺ̾ʼִʱ̡ΪĿѡķ,ӦԼ.
ؼʡзֲ,ʽ,ѡ.
ͼšTP316
Processor Selection Policy in Heuristic Task Scheduling
CHEN Hua-ping HUANG Liu-sheng
(National High Performance Computing Center Hefei 230027)
(Department of Computer Science and Technology University of Science and Technology of China Hefei 230027)
Abstract As one of the most fundmental, critical and challengable problems in PDC (parallel distributed computing), task scheduling has great influence on the execution efficiency of PDC. The existing heuristic task schedulings based on static task priorities always use it as processor selection policy to make the current task have earliest start execution time. On the basis of analysis of the mechanism in priority-based heuristic task scheduling, the authors illustrate the drawbacks of the processor selection policy mentioned above, and propose a new processor selection policy, i.e, to make the successor of the current task have the earliest start time, and give the corresponding restraint.
Key wordsParallel distributed computing, heuristic task scheduling, processor selection.
ȻзֲһNPѶ,ô,ͼһЩϢŵȵĽƽǾõһּ.л̬ȼʽȷ,ȣlist schedulingǲзֲΪõһȼ13.Ҫ˼,ڱʱͼеÿһһȼ,ҰѵǰоȼĴС,һRTQ.Ȼ,ÿδӶѡȼߵ񣨳ƸΪǰ,һѸ䵽ʵĴ,ڸôϵʼִʱ,Ganttͼ1,4ʽʾͼĵȽ.
Ŀǰ,ڱȵʽ㷨ܶ.ǵ˼붼,Ҫڸȼķʽͬ.Щڻ㷨ͨƵȼʽ㷨ִܣ2,5,Щ㷨ԡǰʼִʱ̡ΪĿѡõǰִд.ĵҪڷı㷨Ľ㷨Ļ,ָ㷨еԡǰʼִʱ̡ΪĿѡִдڵ⼰ȱ,ԡǰֱӺ̾ʼִʱ̡ΪĿѡķ,ͬʱӦԼ.
1 ģͼ
ͨ,һгʿ(V,,dij,w(ai))̻,ƫϵһͼG=(V,E)ʾ,V={aii=1,2,...,n},ΪʾnȨ,aiĹw(ai)ΪýȨ;E={(ai,aj)ai,ajV}ΪʾͨŹϵĴȨ,dijΪaiajͨ;IMP(ai)={ak(ak,ai)E)},ʾͼaiֱǰ,IMS(aj)={ak(aj,ak)E)},ʾͼajֱӺ̼.
ͼһʵͼGĿһӳf:V{1,2,...,m}0,),f(ai)=(p,t),ʾaiȵΪpĴ,ʼִʱΪt.һ,ǿGanttͼGC={(p(ai),t(ai))aiV}ʾȽ,кp(ai)ʾaiĴ,t(ai)ʾaiʼִʱ.
1. aiΪͼһ,IMP(ai)=,ƽaiΪڽ;IMS(aj)=,ƽajΪڽ.
2. ͼнaiajһ·ļ㳤Ϊ·ϰʼaiֹajڵнȨ֮.
3. ͼһĳڳΪӸý㵽ڽ㳤.ڳΪڽ㵽ý㳤.
,һ,ڳȴڳСִ.ڳΪȼҪʱ,ôĳڳȾͳΪҪϢ.,ڳȡؼ·ҲǳõһֵϢ.µ㷨,ǾýĳڳΪҪϢ.ĳڳͬʱ,ɽһͨǵֱӺ̽ĿǵȼĴС.
Ѿһȵĳһ,ôǳƸѷ.aiֱǰȫ,ɰѸýΪ뵽RTQ,,RTQǱְ涨ȼС.,һʼֻڽΪ.ھоȼĶҲеǰ,acʾ,ѡִacĴҲеǰ.
ڷֲ洢Ĳмģ,ϸؽ,ڳϢӦðͨӳ.,ͨӳ䴦λй,ͬһȵͬͨӳǲͬ.,aiaj֮ͨΪdij0,aiajȵͬһ,ô֮ͨӳٿԺ,,ͱ뿼ͨӳ.ʵ,Ŀ칹,ôִٶҲͬ,ʱ,ͬһ䵽ͬϵļʱҲǲһ,,ʱͼиȨҲǿɱ,ĳڳȺڳҲǿɱ.ķ,ٶ֮ȫӵ,ͼеȨغͨűȨѻͬһʱ䵥λ,ͨűȨѰϢʱ.
2 㷨Ļ˼
Ϊڷֲ洢Ĳģϲþ̬ʽ㷨,Ҳýĳڼ㳤ΪҪϢ,aiʼִʱʱ,뿼aiֱǰai֮ͨӳٴĿ.ʵ,ڸһai䴦ʱ,ȿǰIMP(ai)Ĵ,ͨϢϴԴĿͬһԼͨӳ.
aiڴp(ai)ϵʼִʱΪest(ai,p(ai)),ִʱΪect(ai,p(ai)),ô,ect(ai,p(ai))=est(ai,p(ai))+w(ai).
4. һauڴPvϵϢʱmrdt(au,Pv)ʾ,ΪauPvִʱ,յȫϢʱ.
һϢʱҪֱǰ,
mrdt(au,Pv)=maxakIMP(au){ect(ak,p(ak))+dku}.
1
һϢʱڵĴй,һ񱻷䵽ĳһǰڴϵĻ,ôֱǰͨӳٿɺ.ʹʽ1ȡֵǰҲauĹؼǰ,auÿֱǰִʱ̲ͬ,,auĹؼǰһauֱͨǰ.
auPvִ,ôҪȵϢʱmrdt(au,Pv)пܿʼִ,ڵʱܷʼִ,ҪPvѷִ.ǰһִѷʱ̳Ϊôľʱ,prdt(Pi)ʾPiľʱ,Ϣʱ̵Ļ,ҲPiִٷʱ.ϵͳ,ǰʱ̵ĴΪȾ.
ķ֪,һau䵽Pvִ,ôauPvϵʼִʱΪ
est(au,Pv)=max{prdt(Pv),mrdt(au,Pv)}.
2
Ŀǰ,зֲлڱȵʽ㷨ǰʽ2ѡʹǰʼִʱ̵Ĵ.
ͼ1һʾͼ,ÿĳڼ㳤Ϊȼ.ͼ2Գڼ㳤ΪϢı㷨LS1ԸͼеõGanttͼ,ȳΪ12.

ͼ1 ʾͼ

ͼ2 LS1õGanttͼ
ڶͼ2Լӷ۲֪,ԵȳȾֱӰִ(a1,a3,a4,a5,a6,a7),ҲΪؼ.ͼ2򵥵,a5ƺԵȳӰ첻,ʵ,Ϊa5a6Ҳڽϴͨӳ,ʹa6a4ͬһ,,a5ҲԵȳֱӰ,Ҳڹؼ.a2Ȼнϸߵȼ,Ǵͼ2Կ,ʹһЩִa2,ҲԵȳȲʲôӰ.ȻֱӰȳȵǹؼ,ô㷨ܷȿǸùؼеִ?ʵ,ڻñʾȽGanttͼ֮ǰ,ǲ˽ֱӰȳȵĹؼ,ͨͼ1ͼ2Աȿɷ,(a1,a3,a4,a6,a7)պʾͼĹؼ·.һ,ؼ·ؼвһͬ,ǿùؼ·ΪҪϢ.
ؼ·ϵƫϵȷ.Թؼ·ΪҪϢı㷨LS2ݹؼ·ƫϵѡai,Ϣʱ̵ķѡIMP(ai)еau,ȻauܻʼʱΪĿѡ,ͬʱҲȷִʱ,,涨ȼGĽ,ЩִжԹؼ·ϵûӰ.ͼ3ʾLS2㷨ͼ1ĵȽ,,ȳȱͼ21.

ͼ3 LS2õGanttͼ
3 Ŀ괦ѡĸĽ
ͨͼ2ͼ3ķ۲Է,ܰa6ŵĸִ,a4a5a6ͨȽϴ,a4a5ַڲͬĴ,a6нʼִʱ.,a4a5䵽ͬһִ,ͼ4ʾ,ʱܻý϶̵ĵȳ,ȳΪ8.ԭԷ,ʽ㷨,ҪÿǰacʼִʱΪĿѡ,ĿľΪʹĺ̽пܾ翪ʼִ,Դ,Ŀʹڽִܾ,ӶʹȳȽС.

ͼ4 ѡԸĽĵȽ
,ֲŵĳacʹʼִʱ˼һʵ,IMS(ac)ѷֱǰacһ,IMS(ac)ʼִʱ໥á໥Ӱ.ʱĳЩ,ֲԵǰacʼִʱѡ,ʹIMS(ac)еĳЩ㲻ִܾ.ͼ2,ڸa5䴦P3ʱ,ٽһa5䵽a4ͬĴʱ,ܷʹǵĹֱͬӺ̽a6ʼִʱǰ.,a5ŵa4ͬĴ,a5䵽P3,Ȼa50.5ʱ䵥λʼִ,ΥԵǰʼִʱΪĿѡĹ,пʹa4,a5a6ͨӳٶΪ㣨ֻҪa6䵽a4,a5ͬĴϼɣ,a6ʼִʱ絽6,ֻҪܻȳ,ʱͲܵa5ʼִʱѡ.
ȻֲԵǰʼִʱΪĿ䴦ܻýСĵȳ,ôʲô,ǲſǰͬΪĳһһЩֱǰ䵽ͬһأͼ2ͼ4Ϊ˵,a4,a5a63ľֲСΧȶ,a5ļʱ,ôͼ4ĵȳȾͻӦ,ͼ2ĵȳȲ,,a5a4䵽ͬһõҲԼС.a5ļʱӵ5ʱ,ͼ4аa5a4䵽ͬһõĵȳҲΪ12,ͼ2ͬ.a5ļʱ5,ʱͼ4аa5a4䵽ͬһõĵȳȽ12.
a5ļʱ䱣ֲ,ϼСa4a6ͨʱ,Ҳʹͼ2ĵȳȲϼС,ͼ4ĵȳȲ.a4a6ͨʱС1ʱ,ͼ2ĵȳҲΪ8,ͼ4ͬ.ͬ,Ǽa5a6ͨʱ,Ҳʹͼ2ĵȳȲϼС.Сa4a6ͨʱͬ,ʱӦa6䵽a4ͬĴ.
һ,ѡʹacʼִʱ̵Ĵp(ac)Ժ,Ҫһacͬaiѷֱǰ,ѡִдΪp(ac)(p(aj)p(ac)),ҵp(ac)Ϣʱ̵aj,ȻǷ:
est(ac,p(aj))+w(ac)ect(aj,p(aj))+dji.
(3)
ʽ,ô,ac䵽p(aj)ʱ,пʹǹֱͬӺ̽aiʼִʱǰ.
1. һauֱǰΪ{au1,au2,...,auk},aurʹmax{(ect(auj,p(auj))+duju0)j=1,2,...,k}ȡֵĽ,u0=u.θy=1,2,...,kyr,duju0w(aur)-(est(auy,p(auy))-est(aur,p(aur))),ôau䵽p(aur),ʹauʼִʱTu,Tu=max{ect(aur,p(aur)),(ect(auj,p(auj))+duju0)j=1,2,...,k,jr}.
֤:ɷ˵.
(1) ʽеTuect(aur,p(aur))ȡ,ô,ect(aur,p(aur))(ect(auj,p(auj))+duju0)j=1,2,...,k,jr),Ҳ˵,aurִǰ,auֱǰϢԴ͵p(aur),,auбect(aur,p(aur))ʼִʱ.
(2) ʽеTumax{(ect(auj,p(auj))+duju0)j=1,2,...,k,jr}ȡ,j=qʱȡֵ,ôͨ;СTu.
(2.1) au䵽p(auq),ʱ,Tu=max{ect(auq,p(auq)),(ect(auj,p(auj))+duju0)j=1,2,...,k,jq}.,ect(aur,p(aur))+duru0ֵ,
ect(aur,p(aur))+duru0ect(auq,p(auq))+duqu0ect(auq,p(auq)).
,ʱ,Tu=ect(aur,p(aur))+duru0,auʼִʱ.
(2.2) auqaurŵͬһ,
duyu0w(aur)-(est(auy,p(auy))-est(aur,p(aur))), y=1,2,...,kyr,
ɵ
est(aur,p(aur))+w(aur)est(auq,p(auq))+duqu0.
ڲʽͬʱw(auq)ɵ
est(aur,p(aur))+w(aur)+w(auq)est(auq,p(auq))+w(auq)+duqu0,

ect(aur,p(aur))+w(auq)ect(auq,p(auq))+duqu0.
1ʲôʹԡǰʼִʱ̡ΪĿѡִдűȽЧ,ӵͬ̽(3)ʱ,Ӧԡǰĺ̽ʼִʱ̡ΪĿѡִд.
4  
Ŀǰ,̬ȼʽ㷨ԡǰʼִʱ̡ΪĿѡִд,ĳЩ,ⷴ̽ӳִ.ϸ˸ֵȲԵĻ,ָԸĿѡִдڵĲ֮,ԡǰֱӺ̾ʼִʱ̡ΪĿѡĵȷ,ͬʱӦԼ.
Ŀоõ863߿ƼĿͰʡȻѧ.
߼飺»ƽ,1965,ʿ,,ҪоΪзֲ,.
,1957,ڣҪоΪֲ㷨,OODB.
ߵλҸܼ Ϸ 230027
йѧѧѧϵ Ϸ 230027
E-mail: hpchen@ustc.edu.cn
ͨѶϵ:»ƽϷ 230027,Ҹܼ
ο
1 El-Rewini H, Lewis T G, Ali H H. Task Scheduling. New Jersey: PTR Prentice Hall, 1994. 5678
2 »ƽ,ֺ,¹.зֲеʽ.о뷢չ,1997,34:7478
(Chen Hua-ping, Lin Hong, Chen Guo-liang. Heuristic task scheduling in parallel distributed computing. Computer Research and Development, 1997,34(supplement):7478)
3 Sevcik K C. Application scheduling and processor allcation in multiprogrammed parallel processing systems. Performance Evaluation, 1994,19(2/3):107140
4 »ƽ,,¹.зֲе(1).ѧ,1997,242:2327
(Chen Hua-ping, Li Jing, Chen Guo-liang. Task scheduling in parallel distributed computing (Part 1). Computer Science, 1997,24(2):2327)
5 Ahmad I, Kwork Y K. A new approach to scheduling parallel programs using task duplication. In: Proceedings of the International Conference on Parallel Processing. Los Alamitos: IEEE Computer Society Press, 1994. 326333
1998-09-18յԭ,1999-03-01յ޸ĸ
