о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.7P.805-812



߻Ⱥϵͳϵľ̬
¾ɽСе
ժҪģд(MPP)ϵͳȣ߻ĻȺ(cluster)ϵͳһֽΪ۵Ĳм㻷.һ߻Ⱥϵͳϵľ̬㷨.㷨3Ҫص㣺(1)ڲ֮ͬͨŶͨߣڵʱ봦һԴԷ䣻(2)ʺڹ㲥ص㣬ڵп˹㲥ĳЩӦöԿԴͨŴ(3)ȷĳϵĿʼִʱԼϢռߵĿʼʱʱѡʱ϶.󣬷ֱGauss-JordanȥLUֽͼȽ.
ؼʣ̬ȣȺ޻ͼȼʱ϶
ţTP301.6
STATIC TASK SCHEDULING FOR CLUSTERS
INTERCONNECTED BY BUS
ZHANG Jun
(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080)
FENG Xiu-Shan
(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080)
HAN Ji-Zhong
(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080)
HAN Cheng-De
(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080)
AbstractCompared with massively parallel processing(MPP) systems, a cluster, which consists of several computers interconnected by a bus, is a very cheap parallel computing environment. This paper proposes a novel scheduling algorithm for clusters interconnected by bus. In general, the algorithm has three main features: (1) Shared bus is treated as a resource being allocated to messages just like processors to tasks (2) Broadcast is considered which can decrease communication times greatly in some cases, and (3) The earliest idle time slot is exploited when determining the start time of a task on a processor and that of a message on the bus. Finally, the schedule results of the Gauss-Jordan elimination method and LU decomposition are given and analyzed.
Key wordsstatic task schedule, cluster, DAG, task priority list, idle time slot
1
΢ԼͨŴߣ߻ĻȺϵͳΪʺĳЩӦõĽΪ۵Ĳм㻷.
ΪʹгڻȺϵͳܵõЧִУúĵȼͬʵʱ̷ȥִ.ھ̬ȶԣڳִ֮ǰɵ.йļ֮ϵͨÿĴԼ֮Ļڱʱٶ֪.⣬һĳֻڸôִУִǷռʽ(nonpreemptive).һ˵̬ȵҪĿСӦóִʱ.
Ⱥ(cluster computing)Ϊ粢моȵ㣬Ҫԭ¼㣺(1)ֻվ(PC)绥γɻȺϵͳͶ.ȺϵͳΪмоṩ۵ļ㻷ּ㻷ǰֻڰĲлϲž߱(2)Ƚ/ɿĻȺ׻ȡMPICHPVMȣ(3)ѾһЩڻĿ磬ATM/Sonet,HiPPi,Token RingFDDI.
ĵĹ˻߻Ⱥϵͳϵľ̬.ݵĽܷ3֣һֽ˵ϵͳģ.ڶ˵㷨еļؼĽȻ˵㷨ֱַGauss-JordanȥLUֽͼȽ.
2ϵͳģ
ϵͳģͰģ봦ģ.ڻڴ˴ģ͵ľ̬ʽ.
2.1ģ
ͨͼǾ򻮷ֺõģͼе޻ͼ(directed acyclic graphDAG)ʾһ޻ͼԪ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ݵĴС.
ͼ1(a)У㣬ļǺűʾýƣֵʾýļС֮ͨŹϵʾϵֵʾͨŵС.⣬ͼеbcst1ʾv1v2,v3,v4,v5㲥ݣbcst2bcst3ĺ.


ͼ1ϵͳģ
Ϊ˱ʾ֮Ļ涨ͼTGϵ(precedence)ϵ
1. ͼTGϣvivjĸ(vjviӽ)vivjvivjȽ(vjvi)vivj.
϶֪ϵдԣϵд.ei,jEȼvivj.ͼ1(a)Уv1v2v1v6ϵ.
УviĸȽ㹹ɵļϷֱΪPARENT(vi)PRED(vi)viӽ㹹ɵļϷֱΪCHILD(vi)SUCC(vi).
2. ͼTGУĳvivj໥(independent)ҽviPRED(vj)viSUCC(vj)vivj໥(dependent).
ͼTGУ໥,ǿԲеִ,,ֻܴеִ.
3. viPARENT(vi)=,vi֮Ϊ(entry node),ǼENTRY=vi| PARENT(vi)=CHILD(vi)=,vi֮Ϊ(exit node), ǼEXIT=vi| CHILD(vi)=.
ͼ1(a)УENTRY=v1,EXIT=v11.
ִģֳ֮Ϊʱĺģ(compile time macro data flow model)12.ڸģУÿֻҪݵ󣬲ſԿʼִУĿʼִҪݵĵģÿִжǷռʽģִҪݷ͸.
2.2ģ
мٶеĴͬ.һ߻ĻȺϵͳУ
(1) P=piݱʾдļϣpiʾi|P|ʾĿ
(2) busΪӶĹ.
ͼ1(b)Уһ3ͨͬһ߻ɵĻȺϵͳ.
ڱУٶÿٶΪsͼTGviļʱ.ڲ(bus contention)£vivjĴСΪdi,jͨӳٿʽ 㣬У·ֱʾͨʱߵݴ.
Уٶǰ˫(half duplex)ϣһֻһͨ(communication transaction)ķ.ңϷͨǿɿ޲.⣬ÿԪרŵӲ֧ͨţĲΪI/O.I/Oͨص(overlapping)ؽУһһϢʱֻӦI/OϢȻʼһļ㹤ȷϢѾպٿʼһļ㣬ϢķI/Oɵ.⣬ʱI/OϢ.
2.3ʽ
߻ĻȺϵͳϣȵĺ棬һǽȥִУһǽ߷Ϣȥʹ.ʽأĳȿúfʾúĶΪVEֵΪP0,)ȣ0,).ĳviVf(vi)=(pj,t)Ǳ֮Ϊviȵpjϣtʱ̿ʼִУĳϢei,j,f(ei,j)=tʾtʱ߿ԷϢei,jʹ.
߻ĻȺϵͳ޵ԴпֲܳͬϢͬʱùߵ.ˣҲΪԴ̬ؼԷ䣬ڳʱ㲻Ҫĳ.
ܵҪָǵȳ(schedule lengthף1ݡ2ֳ֮ΪParallel Time,PT)fĵȳPT(f)=maxt+if(vi)=(pj,t)Ҧi=ai/s.ָ㷨ĸӶȼҪʹõĴĸ.
4. ĿĴɵȫͬϵͳϣͼTGвͬӳ䵽ͬĴϣͼTGеľ̬ؼ·(static gritical path,SCP)Ϊ㵽·(֮ͨʱ).һvxtop level(tlevel)Ϊ㵽ý(ýȨ)·ĳ(tlevel(vx)).һbottom level(blevel)ΪӸý㵽(ýȨ)·ĳ(blevel(vx)).
Уɾ̬ؼ·ϵĽ㹹ɵļϼΪSCPN.ͼ1(a)ڴ11ȫͬϵͳϣͬӳ䵽ͬĴʱs=1,=0,=1,ͼеľ̬ؼ·Ϊv1v4v7v9v11ͼ1(a)еĴֺ,SCPN=v1,v4,v7,v9,v11.
ĿĴɵȫͬϵͳϣͼTGвͬӳ䵽ͬĴϣSCPĳΪmaxvxVtlevel(vx)+blevel(vx)vitlevelblevelļ㷽:

ֱ۵أһtlevelֵԽС˵ýԽпȱȣһblevelֵԽ˵ýԽӦȱ.
3㷨
֪ĿǰΪĻڷȫϵͳϵľ̬£34,ûһƪۻ߻Ⱥϵͳϵľ̬.۵Ļ߻ĻȺϵͳϵľ̬㷨㲻ͬȫϵͳϵľ̬㷨.һʺڹ㲥ڵп˹㲥ۣĳЩӦöԿԴͨŴڶȷϢռߵĿʼʱʱѡʱ϶.
ĸĵ㷨УֱӽʵʵĴ߿ԴϢߣͬʱνԼν߷Ϣ.
߻Ⱥϵͳľ̬Ҫ3˳ѡȵνߵĿʱ϶ϢԼν.潫3Ľ㷨.
(1) ˳ѡȵ
ȵȹؼ·ϵ.ȷؼ·ʱЩ㷨õǾ̬ؼ·Щ㷨õǶ̬ؼ·.ͨһ㷨ĵȳȶǰһ㷨ĵȳȣǰһ㷨ĸӶȵںһ㷨ĸӶ.ڱУΪ˽㷨ĸӶȣõǾ̬ؼ·.ڷǹؼ·ϵȿslevel=blevel-tlevelֵԽ.Уѡǰ˳е.㷨иһȼ㷨.㷨ʵУ㣬ͨһ(㷨еv0)Էе㣬ͨڶԷеĳ.
㷨1. ȼ
 Ӽϣvi|v0viviSCPNѡһveʹ֮Ϊȼеһ.
 ӽveӽѡһλھ̬ؼ·ϵĽΪһѡviжӽ㣬ѡveͨŵӽ.
 ifvi и㶼ȼthen
 viȼıβ.
 else
 ٶvj ǽviЩȼеĸ֮һvjЩоslevelֵ.жĸ㣬ѡviͨŵĽ.vjĸ㶼ȼ,򽫽vjȼıβ.ݹؽvjи뵽ȼ.
 ظڢ޲ֱviи㶼ȼУٽviȼıβ.
 end if
 ӽviӽѡһλھ̬ؼ·ϵĽΪһѡviжӽ㣬ѡviͨŵӽ.
 ظۡᲽֱеĽȼ.
֤㷨ȼ˳ģΪÿֻеĸ󣬲.ͼ1(a),s=1,=0,=1ʱ,ȼΪv1,v4,v2,v7,v3,v6,v9,v5,v8,v10,v11.
(2) νߵĿʱ϶Ϣ
ڱУϢʹ߷ȷŶԭ.ȷϢʹʱѡõʱ϶.
Ϣei,jʹߵʱST(ei,j)ļ㷽.ٶviȵpmִУvjȵpnִpmpnFT(vi,pm)Ϊviڴpmϵʱ.⣬ǰЦĸϢmsg1,msg2,,msgģҪʹߣռõʱ϶ITS(bus)=ۦ1,1ݡȣۦ2,2ݡȡȣۦǦģƦģ.ΪһЩkʽ
(1)
Уk=0,,ģ0=0Ǧ+1=.
֪,k=㲻ʽ(1)ģٶlkʽСֵ
ST(ei,j)maxl,FT(vi,pm)+(2)
Ϣei,jﴦpnʱ
(3) ν
Ҫѡʹ翪ʼִеĴ.
viڴpmϵ翪ʼִʱST(vi,pm)ļ㷽.LDAT(vi,pm)ΪviȵpmʱϢϣex,i|vxviﴦpmϢʱ.ٶvipmʱЦĸvm1,vm2,,vmģҪ˳ʹôpm.ΪһЩkʽ
(3)
Уk=0,,ģST(vm0,pm)=0ST(vm+1,pm)=.
֪,k=㲻ʽ(3)ģٶlkʽСֵ
ST(vi,pm)=maxSTvml,pm+ml,LDAT(vi,pm)(4)
ͼ2Уٶv1,v2,v3,v4ȵpϣv5ȵpʱv5ҪﴦpʱΪ1.3.ڣv5ִʱΪ0.5pϴڵĿʱ϶Ϊ1.7,1.9,2.5,3.1ݼ5.1,ޣݣv5ڴpϵ翪ʼʱΪ2.5.УǴpϵĿʱ϶ΪITS(p)P(vi)ΪviĴ.


ͼ2ռôϵʱ϶
ʵϵʱ϶Ϣ˼뽫ϵʱ϶˼Ƶ.
ڽ3㷨.
㷨2. 㷨
(1) ʼ.
 viV, tlevel(vi), blevel(vi), slevel(vi)
 ͼĴмʱ䣻
 piPITS(pi)Ϊ0,ޣݣ
 ߣITS(bus)Ϊ0,ޣ.
(2) ȼ.
(3) ȼȡһ񣬼ٶΪvjȵpn,viVvivj, ST(ei,j)RT(ei,j).3ǣ
 pn=P(vi)RT(ei,j)=ST(ei,j)=FT(vi,P(vi)).
 ei,jǹ㲥Ϣ.Ϣei,jѱ㲥RT(ei,j),ST(ei,j)ѱ㣻㲥Ϣei,jʽ(1)(2)ST(ei,j)ӶRT(ei,j).
 ֱӸʽ(1)(2)ST(ei,j)ӶRT(ei,j).
(4) еRT(ei,j)LDAT(vj,pn)=maxvivjRT(ei,j)ٸʽ(3)(4)ST(vj,pn).
(5) pnP(3)(4)ST(vj,pn).ST(vj,pc)=minpnPST(vj,pn).жѡһΪpc.
(6) vjڴpcϵʱFT(vj,pc)  FT(vj,pc)˳Ĵʱ䣬еȵһȥִв˳.
(7) ޸ ITS(pc)
 ޸ ITS(bus)
 ȼнvjɾ.
(8) ظ(3)(8)ֱе񶼵.
ͼ1У(a)ͼͼȵ(b)ͼе߻ĻȺϵͳʱϵ㷨ʵʵȽͼ(c)ڸͼУֱ˴ߵʹ.磬v31ʱ̱ȵp2ִУϢe8,10ʱ5,5.4ʹ.ɵȽ֪ͼĴִʱΪ22֮ͨʱ·ȢΪ11.5㷨ĵȳΪ13.ֵָǣv5嵽v4v7֮䲢v4ִ֮У⣬Ϣe5,8嵽bcst2֮ǰʹ.
㷨УҪʱ仨(3)(7).ÿ񣬶ҪÿϵϢĵʱԼѰӦʱ϶.ʸ㷨ĸӶΪO(VEP).
4ģ
Gauss-JordanȥLUֽֽΪֵ㷽.УٶٶΪ50MflopsӼ˳һʱ.⣬ͨʱΪ0.5msߵݴΪÿ100,000.ǵͼȽ.
4.1Gauss-Jordanȥ
ͼ3(a)ڲѡԪGauss-JordanȥDAGͼ.ٶþСΪ1000010000ֿĴСΪ200200ڸͼй1327.ͼÿļСԼ֮ͨĴСֹóͼĴִʱΪ 18835.06s 㵽в֮ͨʱ·Ϊ768.68s.ͼ3(b)Уvi+1iеvji+1(У0i49,i+1<j51)㲥ͬ.ù㲥ÿ£ʡͨŴΪ1225.ͼ4(a)Уеȳõļٱ봦ĹϵͼмٱȵڴʱԵȳ.ܵ˵˹㲥ʡͨŴŴӣٱȳƲ𽥼.ù㲥ڴΪ2ʱȻõļٱ󣬽Ϊ1.48.˺󣬼ʹӴٱҲӣΪѳΪͨŵƿ.


ͼ3Gauss-Jordanȥͼ(a)LUֽͼ(b)


ͼ4Gauss-JordanȥĵȽ(a)LUֽͼ(b)
4.2LUֽ
ͼ3(b)ڲѡԪLUֽ5ݵDAGͼ.ٶþСΪ1000010000ֿĴСΪ200200ڸͼй1275.ͼÿļСԼ֮ͨĴСֹóͼĴִʱΪ13337.62s㵽в֮ͨʱ·Ϊ606.41s.ͼ3Уviiеvji(У1i49,i+1 j 50)㲥ͬ.ù㲥ÿ£ʡͨŴΪ1176.ͼ4Уеȳõļٱ봦Ĺϵͼ.ܵ˵ŴӣٱȳƲ𽥼.⣬ͼл˲.Ϊڴ϶ʱһʼɢͬĴȥԺȲͨſϴ.ù㲥ڴΪ2ʱȻõļٱ󣬽Ϊ1.64.
5
ǾNP.״θһ߻Ⱥϵͳϵľ̬㷨״п˹㲥.µֱGauss-JordanȥLUֽͼӦĵȽ.ͨģȻڲм׳ΪͨŵƿܳߵĹ㲥ԣGauss-JordnȥLUֽ㷨ȡ.
ͼеĽ㼴ָ񣬹ڱʱ
ͼеı߼ָϢڱʱϢ
ף2ڴɽ׶οǹ㲥⣬ڵȽ׶οǹ㲥.
ǵȵļޣʹŵȳҲСڴֵ.
ĿõȻѧʽ(Ŀ 69896250)롰塱йѧԺԡоشĿ(Ŀ KJ-951-B1-703).
߼飺¾У19713ʿо,ҪоΪм㡢ȡϵṹ.
ɽУ197311˶ʿо,ҪоΪźŴϵṹ.
УУ19727ʿо,ҪоΪźŴ塡ϵṹ.
е, У19404оԱ, ʿʦ,ҪоΪϵᡡдý弼.
ߵλ¾(йѧԺ㼼о100080)
ɽ(йѧԺ㼼о100080)
(йѧԺ㼼о100080)
е(йѧԺ㼼о100080)
οף
1Hwang J J et al. Scheduling precedence graphs in systems with interprocessor communication times, SIAM J Comput, 1989, 18(2): 244257
2Yang T et al. PYRROS: Static scheduling and code generation for message passing multiprocessors. In: Proc 6th ACM Int Conf SC '92, 1992. 428437
3Hesham El-Rewini et al. Scheduling parallel program tasks onto arbitrary target machines. Journal of Parallel and Distributed Computing, 1990, 9: 138153
4Yu-Kwong Kwok et al. Bubble scheduling: A quasi dynamic algorithm for static allocation of tasks to parallel architectures. In: IEEE Symposium on Parallel and Distributed Processing, 1995. http://www.cs.ust.hk
5Dongarra J J, Walker D W. Constructing numerical software libraries for high performance computer environments. In: Albert Y H Zomaya ed. Parallel & Distributed Computing Handbook. New York: McGraw-Hill. 1996: 917954
ոڣ1998-10-27
޸ڣ1999-03-29
