ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999



Ѳжȵͼ 
Ž   µ л 

ժҪѲжȵͼȲԳñʱõȫϢ,úϲ,ڵԤ,̬ȺͶ̬ϡʽȺͷֲϵȴʩ,һּ򵥵ġнϸЧʵʵûȷ.õȷܹھѹȳȵ½ԼϵͳԴ.
ؼʡͼ,ͼ,̬,̬,Ѳж.
ͼšTP311
Optimum Degree of Parallelism-based Task Dependence 
Graph Scheduling Scheme
DU Jian-cheng HUANG Hao CHEN Dao-xu XIE Li
(State Key Laboratory for Novel Software Technology Nanjing University Nanjing 210093)
(Department of Computer Science and Technology Nanjing University Nanjing 210093)
Abstract Optimum degree of parallelism-based task dependence graph scheduling scheme fully utilizes the global information collected at compile-time, employs the techniques such as task merging in horizontal and vertical directions, processors pre-allocation, combination of static and dynamic scheduling, and integration of centralized scheduling and layer-scheduling. It is a simple, practical and effective scheduling method which addresses the problem of how to both reduce the execution time of programs and economize on processor resources.
Key words Hierarchical task graph, task dependence graph, static scheduling, dynamic scheduling, optimum degree of parallelism.

дгһ൱Ӻѵ,ԶбĳΪЧøʽĲϵṹṩǿ֧.ڽдгԷʱ,Ҫ򻮷ֳɸģ,ȻЩĶд,жǷڶдͻ,޳ͻ,߿Բִ.ǸģȻ߽Ļ,ֻṩϺõݾֲ.õͼHTG(hierarchical task graph).һĹڲлеִHTGе.ڹ洢ڷֲ洢,ö̬Ⱥ;̬ϵķ.ָ̬ڱʱеĵ,ʱҲΪԤ,ñʱõȫϢеŻ.ָ̬ڳִйеĵ,н϶.ͼ1ǸϵͳĿܽṹ.:(1) /ϵ:иģ֮ϵ,ǲͼHTG;(2) ȺͨŴԤ:Ըִʱͨ,ȷȵUL.

ͼ1ϵͳ
HTGĹһ:ȴULĸϽڵHTGͼǶ뵽ʼHTG,γһһͼTDG(task dependence graph).
TDGķֲ㻯:ȹķTDGзֲ㴦,ʹ֮ͬûϵ,Բִ,ϵĽڵֲڲͬ.γɷֲͼLTG(layout task graph).
ĺϲ:ѲжȺͿõĴڵ,Ϊʵȵľ⻯,ͬһеĳЩкϲ,ͬʱ,ΪҪͨ,ڲͬнϲ.
İװ:ÿӱҪĳɷ,ʹ֮ΪԶеĵλ.
ڵԤ:ÿǰڵڵĴڵ,Աѹͨſ.
ֲ:ڳʱ,ǰϢ,һȼ.
ͼ1пԿ,ǲ˾̬ȺͶ̬ϵķ,̬(Ԥ)ְTDGķֲ㻯ĺϲʹڵԤ,ֲڶ̬.
1ع
һʽŻⶼNP[1],,ʵõĵ㷨Ǿ㷨.[2]һЩ㷨,HLF(high level first),CP(critical path),LPT(largest processing time),Щ㷨ڹ洢ģʽ,ͨŴ,ܺܺõӦڷֲ洢ϵͳ.
[3]һĵ㷨SSS(scalable schedule scheme).SSSһֵ,ڵȳȺͲж֮ȡ.еĴڵ㾺㷨һǰɸڵ,ûпһǰɸ໥.
[4]˹洢ģʽͼĵ.Ϊʹ,
Ȳиߵȼ,Աеƿ,ڷֲ洢ϵͳ,̬Ȳ.
ͼһ:ھѹȳȵ½ԼϵͳԴ.ĸѲжȵĸ,ڵȼͨſ֮ȡ,ͨϲﵽȵľ⻯,ͨ䴦ڵķ㷨ѹͨſ.ʵ,ڴĲС,ĵĵȷʵĿ.
2Ԥ
2.1Լ
(1) TDGLTGԼ
. TDGLTG޻ͼ(directed acirclic graph,DAG).
.ǰ֮Ⱥϵͨ,sendԭΪͨԭ(nonblocking),receiveԭΪͨԭ(blocking).
.Ƿϸ,ǰ֮ǰ,δȫҪϢ,ͨŵȴ״̬.
(2) ִлԼ
ֲ洢ϵͳеĸڵͬ,ڵ֮ͨͬ.
(3) ģ
һ4,ͼ2ʾ.

ͼ2ģ
.receive:ǰϢ.
. :,ɱм.
.:Ϣ,ָʾȼ.
.send:Ϣ.
е񶼰4,TDGûн,βûз,LTGеÿһֻһе,ΪһοԽһ񼤻.
(4) ģ
ö̬Ⱥ;̬ӺϵĲ,̬Ȳüʽ,һþ̬ȵĽ,ʱĳһϢ,LTGʵʩ.ÿεLTGһе
,ֱβִ.
2.2TDGķֲ㻯
Ϊ˱ڽĺϲ͵ȵȺ̹,ȽTDGֲ㻯,ʹͬе֮ûϵ,Բִ,ϵĽڵֲڲͬ.ڵpq,qΪpǰڵ,pΪqĺ̽ڵ.ûǰڵĽڵΪ׽ڵ,ûк̽ڵĽڵΪβڵ.㷨1ȹķTDG,ÿڵһ,ñָڵĲ,TDGķֲ㻯,γɷֲͼ.
㷨1. TDGķֲ㻯
procedure LTDG
Q=nil;
l=0;
for I=1 to n
L(ni)=l;
Q=Q{nfirst};
L(nfirst)=l;
while (Q<>nil)
{
l=l+1;
q=a node from Q with indgree equal 0;
Q=Q- {q};
for (all nodes n adjacent to q)
{
L(n)=max(L(n),1);
Q=Q{n};
delete all arcs incident to this node;
}
}
end
2.3ĺϲ
2.3.1 Ѳж
½ṹļTDG,ͼ3ʾ.Ti(1in)T0,T0ִ֮,TiԲִ.Ĵڵڵn+1,T0ִеʱ,Ϣ,ܵϢ,Ti(1in)ȫȼ,ȻT0Ϣ,Ti(1in)ڵλ,T0뷢,Ti(1in)Ϣ,Ti(1in)ܵϢʼִ.T0,Ti(1in)͵ִʱʱϵͼ4ʾ.

ͼ3򵥵TDGͼ4ִʱͼ
T0Ti(1in)֮ͨŴCi=I+S*Di,IΪͨ,SΪ͵λͨŴ,DiΪT0Ti(1 i n)֮ͨ.һƽΪSH,T0Ti(1i n)ִпֱΪt0ti(1 i n).Ϊ,ٶD,tiֱΪD,t,CiΪC=I+S*D,T0Ti(1i n)֮ͨſʼմ,Ti(1i n)ĵȴ򲻶TDGִʱӰ.,ͼ3TDGִʱΪ
 (1)
ȻT0nTi(1in)ȺϲΪmTi(1im),mn,m|n,ʱ,ÿTi(1im)n/mԭ,ÿִʱͬ,Ϊt =t*n/m,Ti(1i m)T0ͨŴC =I+S*D*n/m,ʺϲTDGִʱΪ
   (2)
ʽ(1),(2)ɵ:t/(SH+I)mn,m|nʱ,
CT  CT(3). (3)
ʹCTСmֵ.Ϊ,ȶʽ(2)m:
(CT ) =(SH+I)- t*n/m2
(CT ) =0,(SH+I)- t*n/m2=0ʱ,CT С,ʱ.Ͻ(3),Ǹ¶:t/(SH+I) m n,m|n,ӽmΪѲж,Ϊpm,ͬʱpt=n*t/pm=.ͼ3Ϊ,n=60,,Ϊt=12,ƽȿSH=2,ʱI=1,t0=10,D=1,s=1,ѲжΪ15.ʵ,ͨ1ҲԿ,m t/(SH+I)=4ʱ,CTCT,m=15ʱ,CT С.
1 жTDGִʱ

m60302015121054321
CT 262184166163166172229262319436793

 
Ϊ˼򵥡,ٶȺͨſͬ.ʵӦ,,϶,ͨſСִпʱ,ȻԽƵΪͨſͬ,tȡƽ,򵥵ضѲжpm=.֮,Ѳжȸ˵ȡͨſ벢֮һ.
Ҫ˵,ѲжָԲִ¡õġ,ִܾǷһȴк.Ҳpmļ㹫ʽûгͨԭ.
2.3.2 ĺϲ
ضִлеȺͨſĴ,ʹȲ̫С.ԭLTGгڴС,бҪĺϲ.ǵϲ,ͬڽкϲ,Ȼڲͬϲ.
ϲʱ,LTGеÿһ,жòǷѲжpm,,pmĺϲ,뵽ĴڵapСpm,apĺϲ.ϲӦһ,ʹøòеִʱ.ľȺϲһNP,Ǹһ򵥵ľ黯㷨,㷨2ʾ.㷨LTGв,ڵvȨΪcw,ʾvִп,eȨΪ(c,s,d),cʾͨ,sΪϢԴ,dΪϢĿ.
ϲʱ,LTGһڵ,Ϊ1,֮ϵĺ̽ڵΪ1,ڵϲһڵ.
ֺϲм򵥡Ժõŵ,ҲƻԭеLTGṹ.
ϲһ,LTGͼϲһڵ,һ:ȻڴгдŲ,ڿɲ̫С,ʹضִл²ִû,˱ϵͳָʾȻմзʽִ.
ڽϲʱ,Ҫ֪ÿ.ڱʱ̽ȷѳΪĿǰоȵ[5].ǾСһЩڱʱȷ,ֻܽбع.عƵĲȷԱڽһЩʵϵСΪ.һ̶Ӱ˺ϲ.ǲõĲȴʩ:ΪLTGĳһṩɸܵĺϲ,ϵͳҪִиòʱ,ڴ󲿷¹ڸòСϢѾ,ϵͳԽΪ׵ѡӺʵĺϲȥִ.
2.3.3 ڵԤ
LTGڱִʱĴڵĸLTGСȡĲеĲȷ,Ϊpnum,ʹõĴڵļϼΪP.viĳǰvijͬһڵpk(1 kpnum)ʱ,Ϊ(p(vij),vi),p(vij)=pk,ͨſ,ڵʱӦʹÿһǰڵ֮,Ϊ׽.һɸǰ,һǰɸ,ڸLTGĳһ䴦ڵʱ,ʹѡ뾺.ϲķֲͼĵtkv1,v2,...,vk,vi(1i k)λt- 1ǰPS(vi)={vij|1jni},Ϊǰ.㷨3һּ򵥵ķʽtĴڵԤ.LTGиβ㷨3ĴڵԤ.ͼ5ΪLTGһ,a,b,c,d4ڵķ䷽2ʾ.

ͼ5LTGһ
2 ڵԤ

PS(d)={d }PS(a)={a ,b}PS(c)={a ,b ,c}PS(b)={b ,c ,d }
(p(d),d)PS(a)={a ,b}PS(c)={a ,b ,c}PS(b)={b ,c }
PS(a)={a ,b}PS(b)={b ,c}PS(c)={a ,b ,c}
(p(b),a)PS(b)={c}PS(c)={a ,c}
(p(c),b)PS(c)={a}
(p(a),c)

 
3ֲ
ֲȲֿڱ,ǰ,ǽƳٵʱ,¼ԭ:(1) һʼִòȵڵȥ,˷ѴĴ洢ռ;(2) ڳִй,Щ񱻼ʱ,ִòCPUռ,̼ķлݺ,ܶ;(3) ںܶϢԤȲּ,˷ֲȱĿС.
㷨2. LTGĺϲ
Procedure LTGmerge
{
for i=1 to m
{
t=iִп֮ac/itn;
pm=;
rp=min(ap,pm);
at=ac/rp;
if (tn>rp) {
Q=iִпcĽ;
Q =Qĩβtn- rpԪ;
Q=Q- Q;
do {q=QԪ;
if (wqat) Q=Q- {q}
else break; }
while(Q<>nil);
while(Q <>nil)
{q =QԪ;
Q =Q - {q }
lq=QβԪ;
lq=merge(lq,q );
if (wlq<at)
lqQ,ʹQִпcĽ;}
}
}
}
Function merge(v,v )
{ 
for (ÿһָv ıe(c,s,v ))
{eָv;
 ޸eȨΪe(c,s,v);}
for (v ıe(c,v ,d))
{ev;
 ޸eȨΪe(c,v,d);}
޸vȨΪv(cv+cv );
LTGɾv ;
return(v);
}
ǵĵģͲüʽģʽ,ΪʽƽΪ,ÿεLTGһе,ʱһȽ(2.1ᵽ,ǵǷϸ,һǰǰõ.)ǼʽȻǷֲʽ,ƿ,ǿͨϸƿ.ϲͷֲȵĽϿԽϺõƿ,ϲʵ˸ƽ,ֲȴѹLTGͨŴ,ʵ,LTGm,LTGֻm-1ε.
㷨3. ͬڵԤ
Procedure proallocate(t)
{
Q=v1,v2,...,vk,ǰĿĶ;
P=P- {t- 1ʹõдڵ};
while(Q<>nil){
v=QԪ;
Q=Q- {v};
If (PS(v)<>nil){
If (vjPS(v)&&vvj֮ͨſ)
(P(vj),v);}
else {p=Pеһдڵ;
P=P- {p};
(p,v);}
for (QÿԪv )
{if (vjPS(v )
PS(v )= PS(v )- {vj};}
QԪذǰĿŶ;
}
4ʵо
Ϊ˲ϵ㷨,Ҫ϶Ĵڵ,,Ҫģķ.һ̨RS6000վ21ģ21ڵ,ÿ̾ͬȼ,ΪʹֵܹͬʱƬ,һ̡Сʱ,δʱ,Ҳ䴦ڼ״̬,PVMɽڵ֮ͨ,ַͨʽģһͬļ㻷.ڸû,һƽΪ30112m s,ͨʱΪ239m s.ʵ,1ѲжȽв,2㷨ܽ.
ʵ1. N*NĸAB(float matrix multiply,FMM),ִʱͼͼ6ʾ.36ֱ60*60,80*80,100*100,120*120ľ˽,ʱԦsΪλ,ȡ10ִнƽֵ,¾ͬ.

ͼ6FMMͼ
3 60*60FMM

1()235610
ִʱ955 703597 312382 280227 547220 543455 095
ٱ11.62.54.24.32.1
pm5
ʵpm6

 
4 80*80 FMM

1()246810
ִʱ2 262 9601 432 227685 733435 176348 141452 584
ٱ11.63.35.26.55.0
pm8
ʵpm8

 
5 100*100 FMM

1()2451020
ִʱ4 428 9802 952 6541 342 1151 029 995560 630820 188
ٱ11.53.34.37.95.4
pm12
ʵpm10

 
6 120*120 FMM

1()4610121520
ִʱ7 229 9852 259 3701 390 380860 712777 418860 822881 705
ٱ13.25.28.49.38.48.2
pm15
ʵpm12

 
ϼʵԿ,pmʵpmǺϵýϺ,˵Ѳжܹӳȼͨſ,һͼ7ؿ.

ͼ7ٱȵĹϵ
ʵ2. Ϊ˶㷨ܽ,ͼ,ͼ8ʾ.ͼÿһһ,γһȫͼ,ȿ5*10421*104m s֮,ͨ15k byte֮,ͼ6,36.Ըͼһּ򵥵ȷ(SS):ÿԵõԴ,Ϊÿһִеһڵ,ڴڵ21(һڵ㱻ռ)11,ʸܹõ.Ըͼ20ʵ,73ʵ,ÿʵ齫Ѳжȵĵȷ(optimum degree parallelism-based scheduling,OPBS)ļ򵥵ȷ(SS)˱Ƚ.пpʾʹõĴڵ,ʵpʾʵʹõĴڵ,Ƚڵ.Ĵִʱڸͼ֮.ӱпԿ,OPBSҪSSЧʸ,ҿԾܵؽԼԴ.˵һ,ֵ㷨ļٱ洦ڵ߲,ҪΪȲ,ĳһʱ̳ʱԼ.ʵ1,Ϊ,һΧ,ٱ洦ڵߺܿ.

ͼ8ͼǰ3㣩
7 ͼĵȽ

ʵִвִ
pʵpִʱٱ
OPBSSSOPBSSSOPBSSS
148429364441 992 3252 466 7852.431.96
48429366661 971 0232 337 8022.452.17
48429368781 968 5992 308 8422.462.09
4842936117111 967 9432 084 3552.462.32
261245334442 662 8403 310 5582.301.85
61245336662 617 3212 958 7112.342.07
61245338782 171 8202 902 6222.722.11
6124533117112 164 5452 551 8892.832.39
354072654442 128 8442 457 8472.512.20
54072656662 032 8062 340 8072.662.31
54072658781 945 0572 207 0432.782.45
5407265117111 952 0812 216 0922.772.44

 
5
ĻѲжȵͼ㷨,ȷѲж,ͨϲ㷨ﵽͬȵľ⻯,ͨڵԤѹͨſ,ʵھѹȳȵ,ԼϵͳԴĿ.ʵ,ڴڴĲС,ĵĵȷʵԤĿ.
עͣоõ863߿ƼĿ
߼飺Žɣ1971ʿҪоΪб
𩣺1957ڣҪоΪ
µ1949ڣҪоΪм㣬ֲʽ
л1942꣬ڣʿʦҪоΪм㣬ֲʽ
ߵλ:Ͼѧ¼صʵ Ͼ 210093
Ͼѧѧ뼼ϵ Ͼ 210093
ο
Graham R L, Lawler E L, Rinnooy Kan A H G. Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Annals Discrete Mathematics. Amsterdam, Netherlands: North-Holland Publishing Company, 1979. 
287326 
Wang Q, Cheng K H. List scheduling and parallel tasks. Information Processing Letters, 1991,37(5):7887 
Pande S, Agrawal D R, Mauney J. A scalable scheduling scheme for functional parallelism on distributed memory multiprocessor systems. IEEE Transactions on Parallel and Distributed Systems, 1995,6(4):388398 
Polychronopodlos C D. Parallel Programming and Compilers. Boston: Kluwer Academic Publishers Group, 1988. 83111 
Liu Y A, Gomez G. Automatic accurate time-bound analysis for high-level languages. Technical Report, TR508, Indiana University, 1998 
ոڣ1998-06-30޸ڣ1998-10-14
