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



ȫͬϵͳϵľ̬
¾е
ժҪڷֲʽڴദDMM(distributed memory multiprocessor)ϵͳУͬе֮ͨſȻܴʱ˶ദĺô.ΪʹгDMMϵͳܵԸЧִУúĵȼ.ȷֱϵͳеģ͡ģԼʽȻڴ˻о3Ҫ⣬(1) ˳ѡȵ(2) ѡ·ɣ(3) η.У·ѡǰ洢תѰʴѰֲͬķʽ۵.󣬸3Ľԣһȫͬϵͳϵľ̬㷨.
 ؼʡ̬ȣģͣģͣ洢תѰʴѰ.
ͼšTP338
Static Task Scheduling for Incompletely Interconnected Homogeneous Systems
ZHANG Jun ZHANG Li-sheng HAN Cheng-de
(High Performance Computing Center Institute of Computing TechnologyThe Chinese Academy of Sciences Beijing 100080)
Abstract In the distributed memory multiprocessor (DMM) systems, communication overhead, involved among tasks run on different processors, is still large which even offsets the advantages brought by multiprocessor parallelism. In order to execute a parallel application efficiently, it is necessary to choose an appropriate scheduling technology to allocate processors to tasks. In this paper, formal description of general scheduling system including task model, processor model and schedule problem is presented. Three most important problems, concerning schedule in incompletely interconnected homogeneous systems, are studied, which are: (1) How to choose scheduling tasks in sequence, (2) How to choose a route, (3) How to allocate processors to tasks. In addition, the problem on how to choose a route is studied according to store-and-forward and wormhole routing respectively. In the end, a static scheduling algorithm for incompletely interconnected homogeneous systems is constructed according to the solutions to the above three problems.
Key wordsStatic task scheduling, task model, processor model, storeandforward routing, wormhole routing.
ڷֲʽڴദ(distributed memory multiprocesor,DMM)ϵͳУд绥̨֮ͨŶ뾭.30ʹͨżķչͻͽ봦ٶȣͨſȻܴԼϢϵͳܽһߵƿ.
ΪʹгDMMϵͳܵԸЧִУúĵȼͬʵʱ̷ȥִ.ھ̬ȶԣڳִ֮ǰɵ.йļ֮ϵͨÿĴԼ֮Ļڱʱٶ֪.⣬һĳֻڸôִУִǷռʽ(nonpreemptive).һ˵̬ȵĿСӦõִʱ.
ĿǵҪϵͳͬģԴĸԼ֮Ƿȫ.⣬ʱ.ĵ1ڸϵͳģͣģ봦ģ.2ڸ˵ʽ.3˷ȫͬϵͳе3ҪĽ,Ӧĵ㷨3ֱǣ(1) ˳ѡȵ(2) ѡ·ɣ(3) ν.У·ѡǰ洢תѰʴѰֲͬķʽ۵.
1ϵͳģ͵ʽ
ϵͳģͰģ봦ģ.ֱģ봦ģ͵ʽ.
ͨͼǾ򻮷ֺõģͼе޻ͼ(directed acyclic graphDAG)ʾһ޻ͼ(DAG)ԪTG=(V,E,A,D).:
(1) V=viݱʾͼн(ͼеĽ㼴ָ,ڱʱ)ļϣviʾi,|V|ʾͼнĿ;
(2) E=ei,jݱʾͼб(ͼеı߼ָϢ,ڱʱϢ)ļϣei,jʾviָvjߣ|E|ʾͼбߵĿ;
(3) A=aiݱʾļϣaiʾviļ;
(4) D=di,jݱʾ֮ͨŵϣdi,jʾvi͸vj.
Ϊ˱ʾͼTG֮Ļ(precedence)ϵ:.
1.1. ͼTGϣvivjĸ㣨vjviӽ)vivjvivjȽ(vjvi)vivj.
Ķ֪ϵдԣϵд.ei,jEȼvivj.ͼ1(a)Уv3v6v2v8ϵ.

(a) ޻ͼ(DAG)

(b) ģ

(c) ִн
ͼ1 ϵͳģ
viĸȽ㹹ɵļϷֱΪPARENT(vi)PRED(vi)viӽ㹹ɵļϷֱΪCHILD(vi)SUCC(vi).ͼ1(a)УPARENT(v6)=v1,v3CHILD(v3)=v6,v7,PRED(v8)=v1,v2,v3,v5,v6SUCC(v5)=v8,v9,v10.
1.2. viPARENT(vi)=,viΪ(entry node)CHILD(vi)=,viΪ(exit node).е()㹹ɵļΪENTRY(EXIT).
 ִģֳΪʱĺģ(compile time macro data flow model)13.ڸģУÿֻҪݵ֮󣬲ſԿʼִУĿʼִҪݵĵģִҪݷ͸.ͨݵķǷǶ(nonblocking)ʽģݵĽǶ(blocking) ʽ.
ģͿԪPG=(P,L,S,I,R).
(1) P=piݱʾдļ,|P|ʾĿ.
(2) L=li,jһ|P||P|Ĵ˾.li,jֻȡ01,li,j=0ʾpipj֮ûֱ(link),li,j=1ʾpipjֱ֮.
(3) S=siݱʾٶȼϣsiʾpiٶ.
(4) I=ۦiݱʾͨʱϣiʾpiͨʱӦI/O.
(5) R=ۦi,jݱʾڴ֮ͨݴʼϣi,jʾڴpipj֮ͨݴ.
ͨٶӶȫ˫(full duplex).ÿԪרŵӲֲ֧ͨţĲΪI/OI/Oͨص(overlapping)ؽ.
ͬϵͳ(homogeneous system)ϣдٶ(Ϊs)ͨŵȣΪͨݴʶ(Ϊ)ģͿԪ(P,L).ģͿԸԪTG=(V,E,T,D)V,EDĶͬǰT=ۦiݱʾļʱ伯ϣiʾִviҪʱ䣬Ϊais.vivj䵽ͬĴpmpnȥִʱڲĳ·㷨ȷĳ·,·ϵͨڿ״̬ʱ,ô洢תѰ֮ͨʱΪ ci,j,m,n=pl(m,n)(+di,j/),pl(m,n)Ϊpm봦pn֮·ĳȣóʴѰ֮ͨʱΪci,j,m,n=+di,j/.
2ʽ
ȵDAGͼеԼ֮ͨŵϢԴǾĳ˻Ĵ֮.㷨ǵνӷϢ.
ڷȫϵͳϣʽ(ף4Ҳ˵ʽ,ȴûп֮ͨŵϢ),ĳȿúfʾúĶΪVELֵΪP0,)ȣ0,).ĳvVf(vi)=(pj,t)ǳviȵpjϣtʱ̿ʼִУĳϢei,j,f(ei,j,lm,n)=tʾϢei,jڲĳѰʱҪʹlm,ntʱ,ӿԷϢʹ,Ϣei,jҪʹlm,nt=.
ܵҪָǵȳ(schedule lengthף1,3ֳΪparallel time,ΪPT).fĵȳPT(f)=maxt+i,jf(vi)=(pj,t)Ҧi,j=ai/sj.
2.1. ٶڱ֮ǰӳ䵽ͬĴϣЩ֮ȫķʽӣٶĴϵͳֳΪ⴦ϵͳ.ͼTGеľ̬ؼ·(static critical path,SCP)Ϊ㵽·(֮ͨʱ).
ͼ1(a)=0,=1,s=1ʱ,ͼеľ̬ؼ·Ϊv3v6v8v10.
2.2. ͬϵͳϣڲֵȵͼTGУͼĶ̬ؼ·(dynamic critical path,DCP)ΪTGеĴ㵽·(֮ͨʱ).
2.3. ͬϵͳϣڲֵȵͼTGУһvxtop level(Ϊtlevel)Ϊ㵽ý(ýȨ)·(Ϊtlevel(vx)).һbottom level(Ϊblevel)ΪӸý㵽(ýȨ)·(Ϊblevel(vx)).
ͬϵͳϣδȵͼTGУSCPĳΪmaxvxVtlevel(vx)+blevel(vx)ڲֵȵͼTG䣬ʽͬڼDCPĳ.δȵͼTGvitlevelblevelļ㷽:

ͬϵͳϣ˳ѱȽtlevelΪýĿʼִʱ(ѱȽtlevelֵļ,ΪδȽtlevelֵʱҪõѱȽtlevelֵ)δȽtlevelblevelֵļҲʽ.
3ؼĽԼ㷨
ȸȫͬϵͳϾ̬еļؼĽԣȻ㷨.
Ѿķȫͬϵͳȵ¼.УElRewiniף5˷ȫϵͳȵ㷨㷨ڴ洢תѰͨţҲûȥӵ(ԼĽ綼ԴϱռõһλеĵڦĶʱ϶)ʱ϶(idle time slot).Kwokף6ӵʱ϶ķϸĹˡͬϵĿʱ϶ֲǲһµġһʵ.
ȫͬϵͳϲľ̬Ҫ3(1) ˳ѡȵ(2) ѡ·ɣ(3) ν.
˳ѡȵһΪ,Ӧȵȹؼ·ϵ.ȷؼ·ʱЩ㷨þ̬ؼ·Щ㷨ö̬ؼ·.ڵ㷨ܣö̬ؼ·㷨һڲþ̬ؼ·㷨ڵ㷨ĸӶȣö̬ؼ·㷨ͨڲþ̬ؼ·㷨.
ѡ·ɡڷȫϵͳ֮޵ԴڲгִйУпֲܳͬϢͬһӵ.ˣҲΪԴ̬ؼԷ䣬ڳʱ㲻Ҫ·Լĳ.
ڷȫͬϵͳԴĿĵ·ܺܶ࣬ȷĳ·ɣԴϢ·ʱܾصĿĵ.ĳȷ·ɣĳַܼϢ·ɵĿĴʱ̣е·Ӧʱ̣ϢĿĴʱ̲ѡӦ·.ڴ洢תѰĸϢĳ·ĿĴʱ̵ļ㷽ڳʴѰû˸Ϣĳ·ĿĴʱ̵ļ㷽ĸϢĳ·ĿĴһʱ̵ļ㷽.
ȶõĶԶԪʸȡĲfstscnd
3.1. fstscndڶԪʸ(x1,x2)fst((x1,x2))=x1scnd((x1,x2))=x2.
fٶviѱȣviҪvjϢei,jѡĳ·ʱҪʹlm,n.ֲͬѰʽ洢תѰʴѰѡ·.
(a) ڲô洢תѰʱ
ٶڴ֮ǰЦĸϢҪ˳ʹlm,n.
(1) fst(f(vi))=pmϢմԴ1ʱһЩkʽ

(1)
ΪϢĴС.
ʽ(1)k=ʱǳ.ΪkеСֵϢei,jʹlm,nʱΪ

(2)
(2) fst(f(vi))pm,ٶϢei,jʹlm,nʱովll,mһЩkʽ:

(3)
ʽ(3)ٵk=ʱǳ.ΪkеСֵϢei,jʹlm,nʱΪ

(4)
ݸ·ϵһӣϢ·ĿĴʱ.
3.1. ڲô洢תѰ,ʽ(1)(4)ѡӵĿʱ϶ʱĳȷ·ɣϢصĿĴ.
֤:ڲô洢תͨʱϢھмʱȴ洢Ȼת.ʽ(1)(4)ѡӵĿʱ϶ʱϢؾм.ˣĳȷ·ɣϢضصĿĴ.
(b) ڲóʴѰʱ
ٶϢei,jҪ˳Ϊla,b,lb,c,...,ly,zȻ,fst(f(vi))=pa,fst(f(vj))=pz.һӣlm,nЦm,nϢҪ˳ʹøӣlm,nѱʱ϶TSm,nΪ

TS=TSa,bTSb,c...TSy,z.
TSӦʱϱռõʱ϶Ϊ,Ϊ˱,
TS=ۦ1,1ݡȣۦ2,2ݡ...ȣۦǦ,Ʀģ,
Уۦi,iݱʾڸʱһϢʹla,b,lb,c,...,ly,zеһ,һЩkʽ,

(5)
k{0,...,}0=0Ǧ+1=.
֪,k=㲻ʽ(5)ģٶΪkеСֵϢei,jĿĴĽʱΪ

(6)
ʽ(5)ʽ(6),е·ȷһʹϢصĿĴ·.
ڲóʴѰʱϢ첽ˮʽĿĴģͬ϶Ӧʱ϶ǲһµģ˺ͳһʽѡͬϵĿʱ϶ʹϢصĿĴ.
Լж·ɶʹϢ()صĿĵأѡ·еһ.
νһΪ,Ӧѡʹ翪ʼִеĴ.ĳĳϵ翪ʼִʱļ㷽.
ȶDAT(vx,py)Ϊvx丸յϢﴦpyϢʱ,ּٶvipjʱЦĸvj1,vj2,...,vjģҪ˳ʹôpjһЩkʽ
scnd(f(vjk+1))-max{scnd(f(vjk))+jk,DAT(vi,pj)ݦi
(7)
kʣ0,...,ģscnd(f(vj0))=0scnd(f(vj+1))=,֪,k=㲻ʽ(7).ٶkʽСֵviڴpjϵ翪ʼִʱΪ
maxscnd(f(vj))+j,DAT(vi,pj).
(8)
ʽ(7)ʽ(8)ɴеĴѡʹ翪ʼִеĴ.
棬ṩĲԣһȫͬϵͳϵľ̬㷨.㷨ѡȵʱõǾ̬ؼ·.
㷨1. 㷨
 ݾ̬ؼ·ȼ.
(a) vitlevel(vi)blevel(vi)ȷһ̬ؼ·.
(b) ȼΪգȡ̬ؼ·ϵĵ1Ϊǰvi.
(c) viΪ0򽫸ýΪȼһУѸýӽȼ1ת(d).viȲΪ0ȶеδȼĸvjtlevel(vj)+j+ci,jĴСɴС.Ե1㼰δȼȽΪͼһ޻ͼݹشͼȼͼȼӵҪȼĩβ.Ƶķุ㹹ɵͼ.ٽviӵȼĩβѸýӽȼ1.
(d) ǰΪһ㣬ȼɣȡ̬ؼ·ϵһΪǰ㣬ִ(c).
 ÿĿĸߵͣȼ.
 ȡȼеĵ1ΪǰִТܡ޲Ϊѡ翪ʼִеĴ.
 ȼеĵ1Ϊǰ.
 ǰͼв㣬丸ɵȺ˳ÿ㷢͸ǰϢﵱǰʱ.ֳҲڵǰִУϢ絽ʱΪʱ䣻㲻ڵǰִУӦʽ(1)(4)(5)(6)Ϣ絽ʱ.Ϣʱ䣬Ϣʱ.ǰͼ㣬ϢʱΪ0.
 ʽ(7)ʽ(8)㵱ǰڵǰϵ翪ʼʱ.ǰΪȼеһת;ӴȼȡһΪǰת.
 ǰΪȼеһ;ȡһΪǰִТܡ޲Ϊѡ翪ʼִеĴ.
ٶ֮ͬͨŲóʴѰϵ㷨һνͼ1(a)еDAGͼȵͼ1(b)еĶദϵͳȥ.ͼ1(a)еľ̬ؼ·Ϊv3v6v8v10㷨1ȼΪv3v1v6v2v5v8v4v7v9v10.㷨2ĴȼΪp0p1p2p3.ȵv3Ϊ㣬ʽv3ȵp0ʱִ.Ƶأv1ȵp1ִ.ڵv6ʱΪҪӸv1Ϣe1,6v6p0ϵ翪ʼʱΪ4.0.v6p1,p2,p3ϵ翪ʼʱΪ5.5v6ȵp0ִ.Ƶأv2,v5,v8,v4ֱȵp2,p2,p0,p3.ڵv7ʱԱȵp0ϣ嵽v3v6ִ֮УϢe4,7Բe1,6֮ǰռl1,0.Ƶأv9,v10ֱȵp2,p0.󣬻DAGͼĵȳΪ12.5DAGͼĴִʱΪ24.0,Ƚͼ1(c)ʾ.
ڣһ㷨ĸӶ.㷨ĸӶҪڢ߲ۡÿϢҪԴ|P|-1ĿĴʱ䣻ÿ񣬶Ҫÿϵ翪ʼִʱ.ڲô洢תʱҪϢھÿмʱʱ䣻ڲóʴѰʱĳȷ·ɣҪҳѾռø·һӵϢΪͬռõϢܲͬʿɴһAVL,ͬϵϢռʱ϶ֹʱΪؼֲ뵽УȻΪҪ·ɵϢʱ϶.ڲô洢תʱ㷨ĸӶΪO(|P||V|2+|P||D||R||E|2)ڲóʴѰʱ㷨ĸӶΪO(|P||V|2+|P||D||R||E|2log(|E|)),|D|Ϊֱ|R|Ϊ֮·ֵ.
4
һ£NP-ȫ.Ŀǰ,ĳЩǳ̵»Ž4.ȫձṩĲȥƷȫͬϵͳϵľ̬㷨ǲѵģ㷨ĸӶȿܻԽ.һϵ͸Ӷȣͬʱṩܵ㷨ЩȡһЩչԴ,ǽԺмԽ.
ĿоõȻѧ͹ʵǼƻĿ.
߼飺¾1971ʿ,ҪоΪм㣬ȣϵṹ.
1962оԱ,ҪоΪϵṹ磬д.
е,1940оԱ,ʿʦ,ҪоΪϵṹд.
ߵλйѧԺ㼼оܼоġ100080
ͨѶϵ:е£100080,270425
ο
1Hwang Jing-jang et al. Scheduling precedence graphs in systems with interprocessor communication times. SIAM Journal of Computing, 1989,18(2):244257
2Wu Min-you et al. Hypertool: a programming aid for messagepassing systems. IEEE Transactions on Parallel and Distributed Systems, 1990,1(3):330343
3Yang T et al. PYRROS: static scheduling and code generation for message passing multiprocessors. In: Proceedings of the 6th ACM International Conference of Supercomputing. 1992. 428437
4Hesham ElRewini. Partitioning and scheduling. In: Albert Y H Zomaya ed. Parallel Distributed Computing Handbook. McGraw Hill, Inc., 1996. 239302
5Hesham ElRewini et al. Scheduling parallel program tasks onto arbitrary target machines. Journal of Parallel and Distributed Computing, 1990,9(2):138153
6Kwok YuKwong et al. Bubble scheduling: a quasi dynamic algorithm for static allocation of tasks to parallel architectures. In: Proceedings of the SPDP'95. Available from: http://www.cs.ust.hk
1998-08-28յԭ,1998-11-30յ޸ĸ
