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



1000Ͼ˻㷨ܷ
лҡ˽ܡ¹
ժҪ˻㷨ڿѧӦʮֹ㷺.и˵;˻㷨1000ϵܱȽϺͷSUMMA㷨о˷ֿߴͨܵӰ죬ָֿߴӰͨܵһҪ.ԭ㷨ûиֿߴľѡȡͨۺʵķһѡȡŷֿߴı׼.ʵʾSUMMA㷨еı׼ѡȡŷֿߴܵõߣɴֵ50.7%.
ؼʣ1000˻ͨţܷ
ţTP302
PERFORMANCE ANALYSIS OF MATRIX MULTIPLICATION
ALGORITHMS ON DAWNING-1000
XIE Xing
(Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027)
GU Nai-Jie
(Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027)
CHEN Guo-Liang
(Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027)
AbstractMatrix multiplication is widely used in scientific computing. The performance of typical matrix multiplication algorithms on Dawning-1000 are compared and analyzed in this paper. The analysis shows that matrix block size is an important factor in the performance of the SUMMA algorithm, but how to choose the best block size is not considered in the original algorithm. A criterion is proposed here for choosing the best block size in the SUMMA algorithm after theoretic and experimental analysis. Higher performance is achieved by improving the SUMMA algorithm using this criterion. Experimental results show that it can reach 50.7% of the peak performance.
Key wordsDawning-1000, matrix multiplication, communication, performance analysis
1
ڿѧ빤̼У˻㷨֮һ.ڷֲ洢лϵľ˻㷨Ҫ1969Cannon1Ķάmeshϵľ˻㷨1987Fox2ݵġ㲥-˻-㷨.1994Choiȣ3PUMMA㷨Fox㷨ƹ㵽άݷֲϣͬ꣬Huss-Ledermanȣ4ֽFox㷨ƹ㵽άݷֲ.1995van de GeijnWatts5һ򵥶Чľ˻㷨ΪSUMMA㷨.
1000лǹܼоƵһֻڷֲ洢ṹϢͻƵĴģмϵͳ6.˵;˻㷨Fox 㷨SUMMA㷨1000Ĵģлϵʵ֣ȽϺͷǵ.
SUMMA㷨˷ֽΪһϵпڴʹģ.SUMMA㷨Уŵķֿߴ类Ϊھһֹķѡ.ǵķŵķֿߴ粻ͻͨأһ봦Ŀ˽ṹй.1000ϵʵ֤ʵǵķ.һѡȡŷֿߴı׼׼SUMMA㷨еķֿߴ˵ʹܵõ˴.
2㻷
1000һϢݻƵɢϵĴģмϵͳ.ͼ1ʾ32Intel's i860XRļ㣨Ƶ40MHzֳ64λ4I/O.ÿڴΪ32MB.1000ķֵٶ2.56GFlops()1.92GFlops(˫).Щͨһ66Ķάmeshӣÿmeshһwormhole·.wormhole·£Ϣ;е·;еĽ.ϢݲжУԴӦ˵֮ɿȫӵ.һһ㷢mֽڵϢʱΪts+mtwtsͨtwͨŴӵ.1000ϵĲԽʾtsֵΪ150stwֵΪ0.026s/byte.


ͼ11000ϵṹ
1000ṩһŻѧKmathԴӳBLASFFTȳÿѧӳ.ڵϵĴм㾡KmathɣԳϵͳԴ.
3㷨ͷ
ǿǵǼ˻C=ABABCֱmkknmn׾.ΪpӳΪrcάmeshp=rcmycolmyrowֱΪڵкźкţ0myrowr-10mycolc-1.ڲǰ£ҲA,BCʾϵӾ飬A䣬Bʾͨʱʹõĸռ.
3.1Fox㷨2
m=k=nr=c=Fox㷨ABCΪͬСķ󣬶ӦڡĶάmesh.㷨̿ԷΪ㲥˻3֣㷨1ʾ.
㷨1. άmeshϵFox㷨
C=0
for i=0 to  -1 do
curcoll = myrow+i mod 
if mycol = curcol й㲥AA
C=C+AB
if i-1 Bڱѭƶһ
end for
Fox㷨ļΪ(n3/p).㷨оA㲥˴ΣBƶ-1ΣǵĴСΪn2/p㷨ͨſΪҲ.ÿҪABCӾټϽϢռ䣬ܹҪĿռΪ(4n2/p).
3.2SUMMA㷨5
SUMMA㷨Fox㷨һABCΪͬСľ󣬶Ӧrcάmesh.SUMMA㷨˷ֽΪһϵеnbеABֱ𱻷ֽΪnbСппˣnbmin(k/r,k/c)ǰ˵ķֿߴָnbĴС.㷨У㲥ʵΪ߼ллϵˮߴͣﵽ˼ͨŵص.㷨2ʾ.
㷨2. άmeshϵSUMMA㷨
C=0
for i=0 to k-1 step nbdo
curcol = ic/n
currow = ir/m
if mycol = currol й㲥Ai mod (k/c)пʼnbУA
if myrow = currow й㲥Bi mod (k/r)пʼnbУB
C=C+AB
end for
SUMMA㷨ļΪ(n3/p).㷨ͨŲֲˮ߹㲥ļͨſӦΪ(k/nb+2c-3)(ts+mnbtw/r)+(k/nb+2r-3)(ts+nnbtw/c)m=k=nr=c=ʱͨſΪ2(n/nb+2p-3)(ts+nnbtw/).ÿҪABCӾټϽϢռ䣬ܹҪĿռΪ(3n2/p+2nbn/).
SUMMA㷨ļ㸴ӶȺFox㷨൱ĸռСFox㷨ڴĿͬʱSUMMA㷨ģ.SUMMA㷨ˮ߹㲥ļͨſвlogPӣSUMMA㷨иõĿԣڴģлSUMMA㷨ҪFox㷨.
4nbSUMMA㷨ͨܵӰ
SUMMA㷨УŷֿߴnbΪھһʹֹķѡȡ.һоnbSUMMA㷨ͨܵӰ죬Ѱѡnbķ.
4.1۷
Ϊ˼ۣǼm=k=nA,B,CΪʱSUMMA㷨ͨſΪ
2nts/nb+nnbtw((2c-3)/r+(2r-3)/c)+n2tw(1/r+1/c)+(2c+2r-6)ts
ֿߴnbʱʽӵ1٣2ӣֵ.1ļٴٵĽͣ2Ӵ˼ͨصļ.
ͨԵóʱͨſnbӶСʱﵽСֵrc(2c-3)/2r+(2r-3)/2c>0.
صĴСȫȡڻͨܣھһǳΪͨӣΪǻͨܵһԽСʱԽСͨŴԽϴҲͨԽϺ.֮ͨԽϲʱصֵҲԽϴ.
,׵ֵȡڶάĴС״ǳΪṹ.r=c=ʱҲ£p3.ŴĿӣ׵ֵӲ.
ǽŷֿߴnbmaxķԵó
nbmax=/
ǽΪŷֿߴѡȡҪ׼.
ǿԷ֣nbmaxĴСȡڻͨӦأȡڻṹӦףлͨӶԸһṹôĴС״ͬ.ֻͬʱ;Сṹnbmaxֵһֵ.
nbmaxĴСڦأͨܺʱnbmaxԽСͨܲʱnbmaxԽϴ㷨ĸռҲӦ.nbmaxĴСͦ׳ɷȹϵĿʱnbmaxСһ.
1000ǿԼͨӣĿʱ.£ŷֿߴnbmax봦Ĺϵͼ2ʾ.ͼпԿnbmaxһǴ4ʱ107𽥼С54Сȴﵽ50%.


ͼ21000r=cʱŷֿߴ봦Ĺϵ
mnkȵΣͨƵķóŷֿߴѡȡı׼ʱŷֿߴĴСڻͨӺͻṹӣmnk໥֮ıй.
Ϸ֮⣬nbmaxѡȡҪܵ洢С.ʵ㷨УnbmaxѡȡϸۺϿ.
4.2ʵ
Ƿֱ1000416ϲ800׷˷ͨʱͼʱ䣬ʵ黷ڵ2˽ܣͼ3ʾ.m=n=k=800r=c=,Tcommͨʱ䣬TcompǼʱ.ľԪؾΪ˫ȸ.


ͼ3nbSUMMA㷨ܵӰ
nbӣͨſ½Ⱥܴ󣬶½ٶnbӶڴﵽһֵŴﵽȶ͵㣬㿪ȶ.ǰһڵ۷ԼӦp=4p=16ŷֿߴnbmaxӦΪ10768ʵǻǺϵ.
4.3ܲ
ͼ3ԿȻnbڴһֵ(1000Ϊ20)Ժ󣬼ܾͻԴﵽһȶֵͨȴԶδﵽ.ͨſռ㷨ܿ൱ıأӦڴ洢ǰ°ǰı׼nbʹ㷨ܴﵽ.
Ƿֱ416϶Fox㷨SUMMA㷨(ȡnb=20)͵nbSUMMA㷨(SUMMA)ܱȽϣʵͼ4ʾ.ͼ4ʾͬ£SUMMA㷨ԱFox㷨ģ⣬ĽSUMMA㷨ӣ4ʱFox㷨ӽ16ʱFox㷨.


ͼ4Fox, SUMMA͸ĽSUMMA㷨ıȽ
ʹøĽSUMMA㷨ȫ32ϼ6000׷˻ʱٶȿԴﵽ973.30 Mflops1000625.6%1000˫ֵ50.7%ȡr=4c=8.
5
SUMMA㷨ͨſFox㷨Ժãʺڴģֲʽл.ͨnbSUMMA㷨ͨܵӰ죬ָֿߴSUMMA㷨вɺӵһҪ.ָŵķֿߴͨܺ˽ṹйأڸĻŵķֿߴ粢һֵôĿ˽ṹ仯.ͨnbֵĽSUMMA㷨˴ߣɴﵽֵһ.
ڴģֲʽлϣͨſռִʱ൱ıأ㷨ʱҪǷֿߴԼ㿪Ӱ죬ҪͨſӰ.ĶSUMMA㷨ŷֿߴķо㷨ܷͨܵķͿԵķһĲο.
߼飺лңУ19778ʿоҪоΪзֲ.
˽ܣУ19618ڣҪоΪֲ.
¹У19386ڣʿʦҪоΪм.
ߵλлңйѧѧѧϵϷʡ230027
˽ܣйѧѧѧϵϷʡ230027
¹йѧѧѧϵϷʡ230027
οף
1Cannon L E. A cellular computer to implement the Kalman filter algorithm Ph D Dissertation. Montana State University, 1969
2Fox G C, Otto S W, Hey A J G. Matrix algorithms on a hypercube I: Matrix multiplication.Parallel Computing, 1987, 4:1731
3Choi J, Dongarra J J, Walker D W. PUMMA: Parallel universal matrix multiplication algorithms on distributed memory concurrent computers. Concurrency: Practice and Experience, 1994, 6(7):543570.
4Huss-Lederman S,Jacobson E M, Tsao A et al. Matrix multiplication on the Intel touchstone delta. Concurrency: Practice and Experience, 1994, 6(7):571594
5van de Geijn R, Watts J. SUMMA: Scalable universal matrix multiplication algorithm. The University of Texas at Austin, Tech Rep: UTEXAS.CS//CS-TR-95-13, 1995
61000ģмϵͳ.ܼо, 1995
(Certifying Material of Dawning-1000 Massively Parallel Processing System(in Chinese).National Research Center for Intelligent Computing Systems.1995)
7ƣֲѧ.粢мֲʽ̻.: ѧ.1996
(Sun JiachangZhang LinboChi Xuebin et al. Network Parallel Computing and Distributed Programming Environment(in Chinese). Beijing: Science Press 1996)
8Gu Naijie, Chen Xiaoqing, Chen Guoliang et al. Performance of matrix multiplication on AP1000. In:Proc of 1997 Int'l Workshop on Computational Science and Engineering, 1997. 104107
9⽨ƽѧ. ֲʽϵͳϲо˷. йѧԺо1997걨, 19981827
(Wu Jianping, Chi Xuebin. Parallel matrix multiplication on distributed systems. 1997 Annual Report of Research and Development Center for Parallel Software(in Chinese), 1998. 1827)
ոڣ1998-09-14
޸ڣ1999-03-02
