ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.4P.507-514




CC-NUMAϵͳͨŻı任
塡ѧ¸
ժҪͨſǲбŻҪĿ֮һ.ԾcacheһԵķһ´洢ʲϵͳ(CC-NUMA)ص,ͨϼ任ݱ任,ͳһĴ¶ԲгͨŻĲԺͷ.ͨʵ,֤˴˲Ժͷ֮Ч.
ؼʡб,ͨŻ,任,ݱ任,CacheһԵķһ´洢.
ͼšTP311
Transformation Methods for Communication Optimization on CC-NUMA Parallel System
CHEN YuLI Chun-jiangYANG Xue-junCHEN Fu-jie
School of ComputerNational University of Defense TechnologyChangsha410073
AbstractReducing communication overhead is one of the goals of parallel compiling optimization. According to the characteristics of CC-NUMA parallel architecture, the authors propose some strategies and methods to optimize the communication of parallel programs by combining computing transformation and data transformation based on unified algebraic representation in this paper. Experimental results of optimization are presented, and the efficiency of the optimization policies and the methods is proved. 
Key wordsParallel compiling, communication optimization, computing transformation, data transformation, CC-NUMA (cache coherent-non uniform memory access).
 cacheһԵķһ´洢CC-NUMA(cache coherent-non uniform memory access)ϵͳ,ȶԳƶദSMP(symmetric multi-process)洢ϵͳŸõĿչ,Ӳṩcacheһάȫֵַռķ,˲б.ЩʹڼǶȺҵǶ϶кܺõķչǰ,𽥳Ϊ֮һ.,ͨбŻ߲гCC-NUMAϵͳеִЧ,Ҫۺʵ.
SMPϵͳУڴȫͳһַ,һµڴȡʱ,Զڴݷʵ,ṹ,ʹĿչԲ.CC-NUMAϵͳӲ˺ܴĸ,ڽṹͻSMPпչԲȱ.Ӳʵͳһȫֱַ,еڴռԱڵ.ԶؽڵڴݿԱؽڵcache,Ӳ֤cacheһ.
Ŀǰвѧͼͨ任ݵľֲ.,WolfLam1ڶͷݾֲԵĻ,ͨģ(unimodular)任ĲԺͼСͨſ,ȴûпǼ任ľԺݱ任ص.Wei LiPingali2ʹԱ任ݾֲŻ,ͳһ˼任ݱ任,ǵĽǼ򵥵Ա任,ûжԼŤ任Ť任з.Bugnionˣ3page colorSMPϵͳеcache,ڴҳȱcacheеȴ,ԲܾȷطcacheʹԸĽ.
,ѧڼ任о,ݱ任о.,ĿǰݾֲԵоҪSMP洢ϵͳ(ݵķֲ)ͷǹ洢ϵͳ(Զݲܽбcache),CC-NUMAϵͳݾֲԵо.,бҪCC-NUMAԼݱ任о.
ҪCC-NUMAϵͳ,ͨ任ݵľֲ,ٷôͻͨſ,رǣcacheڴҳʳͻͨſ.CC-NUMAϵͳ,cacheڴҳŶͬһڴ浥ԪĶ,ͬʱҲԶڴ.,Ӱ첢гܵҪôͨſcache湲ͻcacheٹͻڴҳļٹͻcacheпҳпԶطô濪4.
ļٷô濪ĳͨгķôģʽ,ͳһĴͼϱʾ°Ѽ任ݱ任,CC-NUMAдڵcacheͻ.ڼԶطô濪ļ,ѧ߶Դ˶˽ΪоCC-NUMAϵͳ,Զڴܱcache洢,õԺ;ֲ,ͨſͿԽϺõصõ.
1任ݱ任Ĵͼϱʾ
Ϊ˱ʾǶѭ,ĶnǶѭĵռIZnһmάݿռAZm.nǶѭеkǲѭ(貢ϵͳʵִֻ1㲢ѭ,ѭִ),ȡֵΧ1Nk,ɶ岢еӿռ伯Ip(Ϊ˼򻯶,ļǶѭֻȡ1ռ)£
1.1. еӿռ伯ϣ
Ip={IpikIpik*,...,ik,...,*)},1ikNk}.
ikǵkѭԪصֵ,*ʾӦԪصпȡֵ.ͬi1,i2,...,ik-1ֵIpikӿռɲִ,ڲִкҪͬ,IpڵǴִе.
1.2. ռݿռķģʽӳh(I)A,
h(I)={a=i*T+c|iI,aA}.
amά,inά,Tn*mάȡ,cmάƫ.
1.3. еӿռ伯Ipķʼϣ
Gp={Gpik=|Gpik={h(Ipik)IpikIp1ikNk}.
GpikĲAһӼ.
1.4. ռ任ıʾI=I*R+r,RǱ任,rƫ.
1.5. ݿռ任ıʾA=A*S+s,SǱ任,sƫ.
1.1. IpеIp1,...,IpNkӦķݼGp1,...,GpNkཻΪ,ôûcache湲ͻ(cacheӰ).
֤:Cache湲ͻڲִеIpiIpjͬһڴ浥Ԫдɵ.֪,IpIpiIpjӦݼGpi,GpjGpiGpj=,򲻴IpiIpjͬһڴ浥Ԫд,cache湲ͻ. 

һ任RӦĵƫr,ͨǶԵռб任cache湲ͻ.ͬʱ,һݱ任SӦƫs,ͨǶݿռб任ɼٻcacheٹͻ.Ϳ԰ǽ,ͬʱб任,Լٻcacheͻ.
,ͨ任ıѭıʾI䣽I*R+r.ʱ,µĴȡģʽΪh(I)=((I-r)*R-1)*T+c,ټͨݱ任µĴȡģʽh(I)=(((I-r)*R-1)*T+c)*S+s.,µĴȡģʽ޸±.Ϳͳһôcacheͻ(ı任FortranΪο).
2ü任cache湲ͻ
2.1мϵͳģ
Ϊ˼,ĿȫͳһַCC-NUMAĶδ洢ṹ,ڴοɷֳ3㣺Զڴռ䡢ڴռͱcache.ԶڴռķʿȱڴҪ.ͬʱ,cacheԱ汾ػԶڴռ,ͨдز֤cacheһ.ֻ湲ĳͻ,ļ豾cache޴ųcache.ͬʱ,ÿcacheֻһ֣ԺԼٹĳͻ.
2.2ģ
ĽѭΪѭǶѭ(ķҲдйϵĶѭ).Ϊ˼,ļԲѭعϵ,ѭ޺1,±ʽΪԺ.Ƕײнṹнһ㲢ѭ,ܰһѭһѭ,ڶ㲢ѭ,ִһ5.
ļ,ص㿼Ƕѭṹһѭ,һѭ,ͬҲһѭ.ʾ:
DO I1=1,N1
...
DOALL I2=1,N2
...
DO I3=1,N3
...
A1(h1(I1,I2,I3))=...
...=A1(h2(I1,I2,I3)) 
...
ENDDO
...
ENDDOALL
...
ENDDO
2.3Ż
Ϊ˸õ˵,ۼ򵥵ĵάA.ڴ沼ȵ,±ʽΪԺ.ڶԺԴΪƹ.һ.
1:REAL A(M,M)
DO I1=1,N
DOALL I2=1,N
DO I3=1,N
A(I2+I3-1,I1+I3-1)=...
...=A(I2+I3-1,I1+I3-1) 
ENDDO
ENDDOALL
ENDDO
1еĵռI=(i1,i2,i3),1i1,i2,i3N,ݿռA=(a1,a2),1a1,a2M,ռ䵽ݿռӳΪh(I),ͨǿԵõȡ

Z.Shen6ݶ12ͿѧӦóͳƽȡTеԪֵСֵ1ֻ2.05%ϵֵΪ2.ˣĵӾһձ.
ݶ1.1ԵõеӿռIpk*,k,*1kNݶ1.3IpkķݼGpkAhiiIpk.ͨGpkķǿԷǵĽΪգҽԪظܴ.
Gp1(I3,I1+I3-1)|1I1,I3N}, Gp2={(I3+1,I1+I3-1)|1I1,I3N},

Gp1Gp2I3I1I322I1,I3N}.
ΪʹGpk֮ĽΪգҪѭ飬ʹIpk֮ķݼཻ.
2.1. Ipkеĵӿռ{(k1,k,*)},һеӿռIpjУֻҪ֤ͬϵͬ͵˳عIpӿռ䲢ִвӰִе׼ȷ.֤.
1пԵؿ,ÿִI1һѭҪһͬ.һȷI1I2NѭֲPִ(費Ǹƽ).ͨIpеĵӿռ·ֲʹIpӿռ֮㶨1.1ôͿcache湲ͻ.Ϊˣĸ¶Ͷ.
2.1. IеӿռI1{(e1,k1,*)}͵ӿռI2{(e2,k2,*)},(e1,k1)(e2,k2),ǵݷʼֱΪG1G2.G1G2٦,ΪI1Ħ2.
2.2. IеӿռI1{(e1,k1,*)}IеӿռI2{(e2,k2,*)},e1e2,I1I2ҽj1j2(1j1,j2N),㣺(e1,k1,j1)*T=(e2,k2,j2)*T.
֤:I1I2,ݶ2.1ӦG1G2٦,ݶ1.2i1=(e1,k1,j1),i2=(e2,k2,j2),ʹa=i1*T=i2*T;֮Ȼ.

2.2. IеӿռI1{(e1,k1,*)}͵ӿռI2{(e2,k2,*)},e1e2,I1I2,I1I2Ipk.
ι㶨2.2Ip䲢еӿռ.1ΪͨԶ2.2Ľһ㣬I1I2ɼΪʽ

i1=(e1,k1,j1), i2=(e2,k2,j2), i=i1-i2=(e1-e2,k1-k2,j1-j2),
2.2ɼΪ
i*T=0.(1)
e=e1-e2,k=k1-k2,j=j1-j2,ʽ(1)Եõ
e=j, k=j, e=k, 0ܦjN-1.
ڵӿռI1={(e,k,*)}ӿռI2={(e2,k2,*)},ֻҪ
r=e2-e=k2-k, 0rN-1,
ǾͬһIpi.ĶڲеӿռIpiУʾΪ
Ipi={(e+r,k+r,*)|rZ,1e+rN,1k+rN},
ZΪ.
õ任͵ƫʾ任Ipk={(N-k+r,r,*),1rN1+k-Nrk},1k2N-1,

Ȼ,еIpɲִУ໥֮䲻湲ͻ.CC-NUMAϵͳУIpܲԶݷʺαͻ.ˣһݱ任cacheٹͻͼԶݷ.
3ݱ任cacheٹͻ
ȡ˵2жϵͳģ͵Ĳּ裬Ϊcacheа֣cacheٹͻʵʵCCNUMAϵͳ.CCNUMAϵͳУĲӦ߲гľֲԣгݾڱڴ.1УIpеĵӿռIijĴȡģʽŶԽ߷ʵģ˲ñ׼Block,CyclicBlock(n)ʽ飬cacheαͻ.ǣͨݱ任ȴԽ.ȽܶάԵַĴʾݱ任Ĵʾ.
3.1Եַʾ
Ϊ˷ӳάڴʵʷ,ҪԱʾ7.һnά,һ(n+1)άλP,һ(n+1)άm,ԶάA(n,n)Ϊ,ԪA(i,j)mΪ(i,j,1),ĶλPΪ(1,n,-(n+1)).ʼַΪ0,A(i,j)ԵַɱʾΪ
(2)
,mPһԪʾַƫ,mһԪֵΪ1.Ϊ˸رʾӿռķģʽ,Ķ˵Եַģʽ
Addr(I)=P*(h(I))T.(3)
ڼʾԵַƫ޹,,ɰѶλPһʾƫԪȥ,Pʾ.Pʵϱʾ±ڱ仯Եַеļ.ͬʱ,Ϊ˷ӳӿռԪضԵַķʾ,Ķ˼iv(interval vector)
ivT=T*PT.(4)
ivʵϷӳ˳ݷʵļ.nǶѭ,Եõһnά,еiԪصľֵʾӦĵiѭݷʵļ.رһԪصľֵʾڲѭݷʵļ.
3.1. һcache lineĳΪm,һnάiv(v1,v2,...,vn),еkԪ|vk|ǿɲִеѭݷʵĲ,ivĿռֲ,
(1) |vk|>m;
(2) |v(j+1)||vj|,1jn-1jk; 
(3) |vn|<m.
3.1. һcache lineĳΪm,nάiv1(v11,v12,...,v1n)iv2(v21,v22,...,v2n),еkԪv1k,v2kǿɲִеѭݷʵĲ,iv1Ŀռֲiv2,
(1) 
(2) niv1=(|v1n|,...,|v1(k+1)|),niv2=(|v2n|,...,|v2(k+1)|),ʾֵС).
3.2ݱ任Ĵʾ
FortranC,ԶάڴеԵֱַӵĹ涨.ĳЩ,Ƕѭеݷģʽص,ʹֲܴܵʧ,Ҫͨݱ任ݷʵľֲ.Ŀǰ,ݱ任ͣ1Ҫ3:ת(permutation)任ά(extension dimension)任Ť(skew)任.Ȼ͵ݱ任,3ݱ任ͨԺʵ.
3.2.1 תñ任
һnάתñ任SԸıһnάԵַռ,ınάиάȴ.ԶάΪ,תñ任ֻһ֣

ʵǰȵĶάȵĶά.ͨԷ,һnά,ת÷ʽn!-1,n!-1תþ,Щunimodula.ΪͨӦг5ά,󲿷ֶ2ά3ά,תñ任Ŀܴ.
3.2.2ά任
һ,ά任ֻnάĳһά.n*(n+1)n*(n+2)άά任ɸıһnά,ʹ֮һ(n+1)(n+2)ά,ıĿռ䲼,ͨݷֲ,ͿԸıԵַռ.CC-NUMAϵͳ,ݵķڴҳΪλ,ݵķֲСһҳ,ô֧ҳƵCC-NUMAϵͳоͻҳһαԶ̴ȡ.ͬ,ݵķֲСһcache,ͻcacheһα.ˣͨά任,ʹݵķֲһҳһcache.һάA(N)Ϊ,ڲͬķֲ,вͬά任8ݣ

PǴbN/pkblock(k)ֲĿС.Ȼڱ任дȡģļ,ʵʵı任пͨŻּ.
3.2.3Ť任
һnάŤ任ʵƫһnάĳά.ԶάΪ,Ҫһάƫ,Ť任

ȻľкܴĿռ䱻˷ѵ,ʵҪõŤ任,һǴ״(banded matrix)Ŀѧ.״龭Ť任,ӵֻռһС.
ڳ,ĲȡһŤ任.ѭƫƱ֤˱任ľ󲻻ڴ濪,ĳ֮ΪѭŤ任.ԶάA(N,M)Ϊ,Ҫһάѭƫ,ĴʾΪA(i,j)=A(i,(j-i) mod (M)+1),Ť任ɱʾΪ

,±ԪֵʾӦάҪģ.
ʵӦ,ֻͨԶάĳһάŤ任.ÿһάŤ任ֿɷΪ4,ԶάΪ,Ť,ֱƫơƫơѭƫơѭƫ.nά,һ4nŤ任ʽ.潫1˵ͨݱ任ƳĿռֲ,cacheαͻ.
3.3Ż
ֻŤ任з.Ȼ1ͨ任ʹعIp֮ȡݼĽΪգͨIpеĵӿռĴȡģʽзͻᷢ.ͨԵõعķģʽΪ

ʽ(4),ɵõ
ivT=T*PT=(M+1,1,M+1)T.
ļiv㶨3.1,ɵ´αͻԶڴ.ͨǷ,ݱ任Ժܺõؽ.Ϊ˲Ӷݿռ,ĲѭתŤ任,Ť任Ϊ

ع±(i,j)=(i,j)*S+s.ֱSivдʾȽ,ͨعĴ±,ȡģôʽ±ʾ£

(1) (i,j)=(i,j)*S+(0,1),ji;
(2) (I,j)=(i,j)*S+(0,M+1),j<i.
Է,ʵ,ѭתƱ任ı任ڸ¶Ϊͬ,ֻڲͬԼ,ƫǲһ.ͿSʾ任ĶλP壺

ivɱʾΪ

Կ,任ļ㶨3.1,Ŀռֲ,Ҳڴ濪.ʵʵݱ任,Ϊ˽ʡݱ任ʱ,ͨŻ,ȡģ,ʹ任ĿС.
ͨ,ǿԷ,ʹü任ݱ任,ԲгŻһľ.ͨͳһĴ,ǿԽֱ任ܺõؽ,򻯲гı任,ͱĿ,һ߲гCC-NUMAϵͳеִЧ.
4
,޷CC-NUMAмϵͳ½в.ǵĲ4CPUSGI Power ChallengeϽе,128MB,ÿCPU1MBĶcache.Ǿһ¹Ľϲмϵͳ,CC-NUMAϵͳһͳһĹַռ,еڴ浥Ԫܱcache.,һ̶ϿCC-NUMAڴϵͳ.ʹ˱ṩĲб,ʽб.ͬʱΪ˸õضԸֱ任бȽ,ûиŻ.Ƕ4˲,ǷֱǱе1,Banded SYR2K,MatrixTranspose,Vpenta.BandedSYR2K״ԳƾRank-2K (update)ļMatrixTransposeάתõļVpentaǲԳNASA-kernelеһԳ.Խ1.
Table 1Speedup of transformation
1ͬ任ļٱ

ProgramNumber of
processors Base
speedupBase+Comp
transform speedupBase+Comp+Data
transform speedup
Example 1 2
41.53
2.561.73
2.752.37
4.71
Banded SYR2K2
41.59
2.802.51
4.816.41
13.83
Matrix Transpose2
41.82
3.101.89
3.101.88
3.03
Vpenta 2
41.55
2.671.79
2.971.82
3.25

ٳ,ڴ,һ㲢мٱ,һ㲢У任ٱ,
һ㲢У任ݱ任ٱ,1.
1ݴȡģʽǴӶάϽǵ½ضԽ߷е,ͨ任,湲ͻͨݱ任ٹͻ,.Ϊٹͻ1ռͨſҪ,˵õ˳Լٱ.BandedSYR2KĶݴȡģʽǴӶάϽǵ½ضԽ߷е,Ȼûcacheαͻ,ȴɴTLB,Ӱ˳.ͨݱ任ݷʵľֲ,ҳһĿ,ҲõԼٱ.ͨ任תñ任ܽMatrixTranspose෴Եַ,ͨά任,Լҳһαͻ,ͬʱcache.ǽļSMPϵͳ,ʲҳһαͻ,ͨά任ֻܸcache.ͨ任תñ任ʹVpentaеĶάάķģʽз,ݵľֲ.кMatrix-transposeһ,ˣͨݵά任Ըcache.
5 
CC-NUMAֲȫֹ,cacheеĹڴ浥Ԫ.,ڴҳһcacheһٹͻǵľֲ,ܹЧ߲г.νϼ任ݱ任ٳͨſ.ʵ,߽ܵõõЧ.һ,ǻԼ任ݱ任ۻ任ݱ任о.ͬʱ׼ڼɵDSMģϽиȷʵ.
壨ѧѧѧԺɳ410073
ѧѧѧԺɳ410073
ѧѧѧѧԺɳ410073
¸ӣѧѧѧԺɳ410073
ο
1Wolf M E, Lam M. A data locality optimizing algorithm. In: Proceedings of the SIGPLAN'91 Conference on Programming Language Design and Implementation. Toronto, Canada, ACM SIGPLAN Notice, 1991,26(6):3044
2Li Wei. Compiler cache optimizations for banded matrix problems. Technical Report, Department of Computer Science, University of Rochester, 1995
3Bugnion E, Anderson J M, Mowry T C et al. Compiler-Directed page coloring for multi-processors. In: Proceedings of the 7th International Conference on Architecture Support for Programming Languages and Operating Systems. Boston, MA: ACM SIGPLAN Notice, 1996,31(9):244255
4Chen Yu, Yang Xuejun, Chen Fujie. Communication optimization for NUMA parallel system. In: Li Xiaoming ed. Workshop on the Frontier of Supercompiler and Parallel Computing Environment. Beijing: Beijing University Press, 1998. 1829
(,ѧ,¸.NUMAṹͨѶŻ..бͲм㻷ǰؼֻ.ѧ, 1998.1829)
5Jin Guohua. Program parallelizing techniques and tools Ph.D. Thesis. Changsha: National University of Defense Technology, 1993
(.л乤ߵо۲ʿѧλģ.ɳ:ѧѧ,1993)
6Shen Z, Li Z, Yew P. An empirical study of Fortran programs for paralleling compilers. IEEE Transactions on Parallel and Distributed Systems, 1990,1(3):4553
7Cierniak M, Li Wei. Unifying data and control transformations for distributed shared-memory machines. In: Proceedings of SIGPLAN'95 Conference on Programming Language Design and Implementation. ACM SIGPLAN Notice, 1995,30(6):205217
8Chandra R, Chen D K, Cox R et al. Data distribution support on distributed shared memory multiprocessors. In: Proceedings of the SIGPLAN'97 Conference on Programming Language Design and Implementation. ACM SIGPLAN Notice,1997,32(5):334345


