
Computer Engineering
1999ꡡ259ڡVol.25 No.9  1999



ʵʵ񹹲мģ
ΰ½δӡ
ժҪͨ϶ִԲмģͣ칹еHBSPģͺͳ㷽ûϢȵģ;ͨſļȷ㷨칹еҿɽԭBSPģͶh-relationƵŵ㣮BSPĸٶͬԭBSP㷨ﵽ(ļͨȫ)ʱ,HBSPģ͵ͬԭģ.
ؼʡ칹㣻BSPģͣмģ
More Practical Heterogeneous Parallel Computing Model
Huang Weimin, Lu Xinda, Zhong Rong
(Dept.of Computer Science of Shanghai Jiaotong Univ., Shanghai200030)
AbstactIn this paper, severtal standing parallel computing models are combined and Heterogeneous Bulk Synchronous Parallel(HBSP) model is proposed. The communication cost prediction is made more precisely based on liner model of message length, and the restriction on h-relation of original BSP model is canceled to make the algorithm and program design in HBSP more flexible. The HSBP model is same as the orignal when processor speed of BSP computer is all the same and the original BSP algorithm is optimized(e.g.the computation load and communication load are totally balanced).
Key wordsHeterogeneous computing;Bulk synchronous parallel model; Parallel computing model
ɶϵͳͨ繹ɵ칹ϵͳȺתһһµġǿĺͽϸܼ۸ȵĲмԴ칹мڸܿѧͨӦܵ㷺о칹УϢݱģͣһгһ໥ЭĽɣÿ̶ִͬʱϢϢݱ̾нǿĹܣƳЧͿֲĲг򣬵ȱָҪԱݺͼֹ䵽ϣԴʽڴ֮ͨŵ̡Ĳнṹͽҹͨţʵ֡ԲҲн̲֮ĴͨʱϢݿ⺯ʹýúѡı̷ȷԼ顢ܷȷȻھ׶Σڳӱģ͵ĽǶҪһָȻͼ򵥵ļģһ⡣½϶ִԼģͣʺ칹㻷ĳƺͿ㷽
1 мģ
мģһ߲صͲԷ뿪Ľ棬ṩϽб̵ضнṹÿʵҪЧִз뿪ṩԺȶԡģṩĲȵײṹṩĲ߼ö࣬ṹƵѡȶƿԻһʱ䱣ȶı׼ӿڣÿǲмṹı仯ͬʱģγÿлʵʱڵĹ̶(תϵͳϵͳ)
1.1 洢ͬģPRAM
PRAMһֹ洢ͬģͣڵλʱڶдڴ棬ͬһȫʱ(Lockstep)ʽʵ֣㷨ƺͷʱͬģ㷨ȷͬ㡣PRAMеĴ󣬽еɸԵľֲ㣬زͬĲд(EREWCREWCRCW)ǰ£д洢ԪȻͬؿʼһֲ㡣PRAM㷨ƺͷȽϼ򵥣ڶԲ㷨࣬Ȼȴʺ첽MIMDͬʱǵ洢ʹ洢ĿٶڴΪλʱҲǲʵģҲʺڶʵʵĲмԤ⡣
1.2 BSPģ
BSPģ(Bulk Synchroneous Parallel)УһϵȫֿͬĳΪLĳɡÿУÿִоֲ㣬ͨպͷhϢ(Ϊh-relation)Ȼͬ飬ȷóǷɡÿʼʱѾЧľֲݽвδ׼ãƳٵһʼʱٽм㡣BSPģҪ3ʾֱǣpΪԪĿgΪϵͳļ紫ϢͨıֵʽһЩϵͳҪghʱ䵥λh-relationBSPһΪmϢmΪ1Ϣ֮䲻ֿ֣ΪmhgLΪ֮ͬʱ
1.3 LogPģ
LogPģҪ4LϢԴĿĵصӳ٣o/һϢĶ⿪gͻϢСPĿLogPģмҲһϵеĳϢһͿɼ㣬صأʽͬÿõ㵽ϢݷʽʵͬLogPĳBSPܽջϢĿƣҳ֮ʽͬ㷨ӦӷʵLogP㷨ƼԺǿҪÿľֲ㲽ϸţͨƷΧڽͨŲͼصҪƷ䴦ԼٶͨŴҪͽԶ̷ʵƵʡͬLogP㷨Ƽ಻ͬ¿ѭ
1.4 LogGPģ
LogGPģ[1]ǶLogPģ͵չֻжϢʱLogP׼ȷԤͨܣԳϢȴܡLogGPģͽLogPģͺһϢģͽһGͳϢʱһЩ㷨(FFT)Ʒʵݱչ׼ȷԤⳤϢͨܡLogGP㷨LogPŻ㷨ȣִٶȺнϴߣģ͵ĽһӻLogGPϵ㷨ƺͷҲΪӡ
1.5 мģС
BSPȣLogPͬ(1)LogPûpairwiseͬϢݷʽ(2)LogPӲoԱʾϢʱ⿪BSPгӦڵϢͨ⣬һԺԣ(3)LogPģеgǴӾֲĽǶġ˵LogP+Barriers-Overhead=BSPȣBSPģ͸нṹԣҲӼ򵥡LogPģƺΪȴҪǿƼɣʹ㷨ͳƵĸڿơо[2]BSPLogPģͿЧ໥ģ⣬ʹø򵥵BSP̷ʽӰ졣ͬʱLogGPо֣ʵֳϢ򵥰취ǽͬһļϢϲһϢBSPģ͵һҪص㲻ıϣһϢȵʱϢϲһη
ڼģ͵ĸѾԽԽͳһһõģӦڱ̡ȷȷԡṹԡģ⡢ɸЧʵ֡ṩĶԡϿԼģ͵оھ˴PRAM->BSP->LogP->LogGPĹ֮»صBSPBSPĸȱ˸̵ʶ˽⡣
BSPģָµĲг[3]б̼򵥡ĿṹִܿԤص㡣BSP䳬ĽṹʹϢݲͬʱȷԡܷͱ̷϶Уʺ칹µϢݱ̡ԴҪͨh-relationgĲ㲻ȷ칹²ʺϵ⣬¸ʺ칹㻷BSPģͺͿ㷽
2 칹еBSPģͺͿ
칹BSPģ(HBSP)мһϵĳɡÿУÿԪʹóʼǰѴڱصݽмʹ Щ(1)Դڱصݽм㣻(2)Ϣݣ(3)Ϣա칹ϵͳP={P1P2Pp}дp=|P|,ٶȲS={S1S2Sp}W={w1w2wp}ͨ伯H={h1h2hp}SjΪPjļٶȣbjΪæжȣs'j=sjbjΪʵʼٶȡwtj=wj/s'ΪPjwjʱ䣬gtΪһֽϢʱ䣬LtΪBarrirerͬʱ䡣
ÿĿɣÿеıش(ֲͻͨſ)ͳʱbarrierͬĿ
(1)
iִʱT(x)=Tlocalproc+Tsync=
(2)
칹BSPģУLǸݽϢȻʵBarrierͬĳġ
ָٶSż͵صͬкܴ仯һֵƽ[s]άA[n][m]B[n][m]mԶԶÿcacheСһάA[i][0]XB[i][0](i=1,n-1)ĿÿμcacheݶͬӶһcache missٶȵ½硣[S]һάA[n]B[n]˵ĿnԶԶÿcacheС󲿷ּcacheɣٶȵ(ɶѭԼ)
еĲмڳϢṩ֧֣ͳϢĴҪԶڷͶϢĴǵЩأȷأ칹BSPģУϢСͨſУһԹʽnֽڳϢõʱ䣺t=t0+tB.nt0ǽһϢĿ괦ͨʱ䣬tBÿֽʱ䡣ʵ(ͼ1ͱ1)չ׼ȷԤϢͨܡ
1(SunE450,SunCreator,SunUltarSparc,SunUltraSparc)ֻͨ100Mb Ethernetɵ칹ϵͳMPIͨԭMPIsendMPI-RecvԲܴͬͨٶȺͨõ²Խʾͼ
ͼ1ͱ1пԿ3ֱֲܴͬ𽻻3ֲͬ͵ϢͨʱͨϢСԺͬͨͬϢͱ仯ʱ(char,integerdouble)ʾͨٶȵбʻϢСһ¡Ҫע⵽ͨĿʱ뷢2500ֽڵϢʱͬҪ¿ͨص칹绷еʵԣصʹмٶȼӱʵʼٱԶСڴˣ󲿷ֲ㷨ļͨӵÿ죬Ƴ㷨ʱӦϲͬϢ

ͼ1 칹ϵͳлͨŽʾͼ
1 칹ϵͳͨŲͬϢб

б
ϢͣcharϢͣintegerϢͣdouble
Sun USparc-Sun Creator0.1143210.4054830.756228
Sun USparc-Sun USparc0.1124040.3995760.746370
Sun E450-Sun USparc0.1184140.4054830.756047

һУ账PiҪ͵ϢΪH={h1,h2,,hk}hiʾϢĳȣһϢĿkģأȻk>>ph0ǽһϢĿ괦ͨgÿֽ(Ҫע⵽gСԭBSPģеg)ÿϢΪh0+hi.gӶPiͨſΪBSPнԺٽдϢݲ˿ɽͬϢϲһϢͨԼٵp-1ΣʹͨſСڵڡ
ʧһԣ账P={P1,P2,,Pp}ͨͬӶһBSPͨٶgͬ账ʵٶȲS'={S'1S'2S'p}ȻBarrierͬʱLtͨٶĴʱLt=L/Smin'
P*=(P1*,P2*,,Pp*)Pi*=Si*/Smin'ó

ͨ(p-1)h0ֻ봦ĿأģʱԺԣΪ򵥺Ӧã
ʹ(3)
칹BSPģͣóдЧ칹BSPĲԣ
(1)ÿеBarrierͬȴḶ̌ҪʹT(x)СӦʹıؼʱʹͨʱ֮;⡣
1BSPִеһ䵽ĳPiļУؼ㿪봦֮ͨſ֮ȳΪüPiϵıˮƽt
2ʹBSPpﵽͬʱWӦڴP1,P2,,Ppϵıˮƽ {12p}Ϊ {Pi} ٽ籾ˮƽ
{ci} 

ȻУ{
Wi/Pi*+hi.g=Wj/Pi*+hj.gi,j p
ʽʱWﵽP1,P2,,Ppٽ籾ˮƽT(x)С
(2)ʹĿСΪԼLĴ
(3)ϲͬĶϢʹÿͨΪp-1Ρ
3 
칹㻷еBSPģ(HBSP)ͳ㷽ԭBSPģҪͨh-relationϵHBSPģдƣΪ㷨ͳṩɡڴٶͬ£P*i=1(i=1p)ʱҸļͨȫʱ(1)(3)ʽתΪBSPı׼ģͣ
C(x)=max wi+max hi.g+L=w+h.g+L
Ti=Tcompi+Tcommi+Tsyni=(w+h.g+L)/S
У{pjıؼʱ}{pjĻͨʱ}SΪBSPĵִٶȡ
BSPĸٶͬԭBSP㷨ﵽ(ļͨȫ)ʱ칹BSPģ͵ͬԭģ͡
*ĿȻѧ
߼飺ΰ(1970)УʿҪо򣺲ֲʽ
ߵλϺͨѧѧ빤ϵϺ200030
ο
1 Sunderam V.Heterogeneous Network Computing:The Next Generation.Journal of Parallel Computing,1997,23:121-170
2 Bilardi G.BSP vs LogP.In 8th ACM Symp.on Parallel Algorithms and Architectures,1996:25-32
3 McColl W F.Scalability,Portability and Predictability:The BSP Approach to Parallel Programming.Journal of Future Generation Computer Systems,1996,12(4):265-272
ոڣ1998-11-30
