о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 5 Vol.36 No.5 1999



ģдϵͳƷо
Cacheȱʧӳ١㷨Ϳɶ
塡ܾ
ժҪʵģдϵͳmassively parallel processing system, MPPʵЧٶ۷ֵٶŽϴ࣬ʱܴﵽֵٶȵ25%.Ŀǰĸܿѧ㶼ҪMPPϵͳΪҪʵֹߣרҵձע.ӰģдϵͳЧٶҪ֮һCacheȱʧ⣬Exemplar SPP1200/XAΪ,ڲ㷨Ϳɶʵ鲢ܽϵͳӦܵɳƷ.
ؼʡģд Cacheȱʧӳ٣Чٶȣ㷨ɶ
ͼšTP311
THE STUDY OF AN MPP SYSTEM AND ITS PROGRAMMING METHODS
WANG Wen-Yi and DONG Shao-Jing
(Department of Computer Science and Technology, Zhengzhou University of Technology,Zhengzhou450002)
(Computing Center, University of Kentucky, Lexington40506)
AbstractPractice shows that in most cases the effective speed of a massively parallel processing system(MPP) is much lower than its peak speed,often reaching only about 25% of the latter.At present MPP is used to perform high-performance scientific computation in many research fields,so the above-mentioned problem has been followed with interest by experts both at home and abroad.Here discussed is the cache missing latency problem,that is one of the main factors influencing MPP systems effective speed. Taking Exemplar SPP1200/XA for example, some programming methods for increasing the systems application properties are tested and summarized in discussing both the hierarchical algorithm and localizability.
Key wordsmassively parallel processing, cache missing latency, effective speed, hierarchical algorithm, localizability
1
ĿǰϻڳRISCļMPPϵͳT3D(152Gflops)CM-5(135.1Gflops) SP2(136Gflops) Paragon XP/S(154Gflops)Exemplar SPPϵеȣȻǶкܸߵ۷ֵٶ,ӦеʵЧٶȴ֮Զ.ǵRISCоƬһ㹤վHPSUNRS/6000ЩڳûҲƵӦЧ⣬ԶMPPϵͳûܽоʹ֮õƣҪʵ.
1.1ɫ̬HP-Convex Exemplar SPP1200/XAϵͳ
㣨quantum chromodynamics QCDоĹؼһܿѧ⣬ΪʹýСĸߴ16324м㣬FermionҲһ500׸ԪصĴϡ󣬽һҪ4Gbڴռ䣬֮ͨ൱߳ļܻýֻʹóмʱյҪ.
HP-Convex Exemplar SPP1200/XASPP1200һ͵ĸܿչдϵͳscalable parallel processing systemSPP÷ֲʽ洢ṹӻϵͳCXPAConvex x-Window performance analysis tool ͼηʽʾû͸ĽӦóҪϢжȡMflopsCPUʱ䡢ʱ䣨wall clockʱ䣬ʱ䣩CacheȱʧԼͨŻӳٵ[1].
иQCDFortran 90[2~4].ƪޣȫԴCXPAͼȥ.
1.2QCDڼMPPϵͳϵв
SPP1200ϵͳߴΪ16324Fermion㣬иQCDٶǺܵ͵ģﵽֵٶȵ25.8%.CXPA1п.
1QCD루棩CXPAԽreal8

ߴ紦CPUʱʱֵٶ/Чٶ/
16324 85322.8835.7120Mflops31Mflops


Ϊ֤ʵⲻǷSPP1200ϵĸMILCmultiple institute lattice collaborationQCDСרMetaCenterMPPϵͳͬȫ򲿷֣QCD뵫òͬߴЧٶʵ飬ȫڱ2֮. 
2MIMD QCDMetaCenter MPPϵЧٶȲݣreal8

͸ߴ硡ֵٶ/㣨MflopsЧٶ/㣨Mflops
Paragon xp/s84
16*323
3241
128
25680 28
23
22
CM-5б
CM-5ȫQCD룩243*12
243*12128
12812840
23
T3D162*322
16*32364
128146.531
30
SP2123*6
122*242
12*243
2441
8
16
32265.636
34
32
30


ʵѿȻõļMPPϵͳϵṹϿͬParagon xp/sCM-5SP2Ƿֲʽ洢ṹT3DSPP1200Ƿֲʽ洢ṹ[1,5,6]ڴͿѧУǵûЧٶķֵٶȴྶͥȴһͬʵ. 
2Cacheӳ٣Cache latency
MPPϵͳЧٶҪܵCacheȱʧӳ١ϢӳٺǱӳٵصԼ.ԽCacheȱʧӳЧٶԶСڷֵٶȵҪԭռȥûCPUʱ70%ϣ
CacheȱʧĵڸҪȡڴ洢ȻҲйϵRISCĴ͵ˮҪָ꣬洢ĲνṹʹһͣΪֲ㼼ʹ洢Լ٣ٶȽϿСĴ洢޷һӽе.SPP1200ϵͳΪķҪΪ
120*8=960Mb/룩
ʵϴڴ浽CPUݴٶȴֻ88Mb/1.
Ϊɴì.һ棬ҴӲϣ оƬCache.HP˾µPA-8500΢ƬCacheѴ1.5Mb; ö,Ѿﵽ28; һԤȡprefetchingܣӴ.ʵٶȵԶԶϴٶȵʹCacheȱʧĿڳ.һ棬ΪMPPĸԣûΪеĳƺͼ㷽ҲֱӰ쵽ܵĳַ.˵ûǶȳѰµ㷨Լ̼CacheӳʱӶϵͳӦܣͳһеġʵ.
3Cache(cache using ratioCUR)ݿɶ(localizability)
3.1ʹá㷨(hierarchical algorithm)Cache
㷨Ŀǰ㷨Ĺעȵ.Ļ˼ǣܵá顱ȡһĴͳ.ͨ׵˵Ҳһ־ݣ㡱ļ㷽.㷨ѱ㷺ӦһЩ°汾ѧ.
Cacheȱʧ£Чٶ޿ԽƵ(ԽСӳ٣ʾΪ
VeVp1.0-CMR=Vp*CUR
Ve,VpֱʾЧٶȺͷֵٶ,CacheȱʧCMRcache missing ratio=Cacheȱʧӳʱ/CPUʱ䣩*100%.
֪㲿ʱӦCacheУCURɼ򵥵ıΪCacheƽÿݲμĴ
CUR=ִָд/ݸ
ԣѡ١ִָдࡱࣩļģʱͿԼٴڴ浽CPUҪﵽCURҲ߻ЧٶȵĿ.
3.1.1Լ
Լ⣬һɷΪ3ʾ4.CURķ֪ÿһӦCURӦǸͬģԼԽCURҲԽ.3гֶӦϵ.
3ԼCURĹϵƺţ

Լ㹦CUR=ִָд/ݸ
0󣩸ֵ1/2
1-㡡V=B+a*V3/3
2-㡡V=M*V2n2+n/n2+2n2/1
3-㡡M=L*R2n3/2n2n/1


3.1.2QCDSPP1200ϵͳϵĲʵ
SPP1200ϵͳȡ3000*30003000ֱиQCDConvex˾ԴͨóVECLIBеĴ룬ʹCXPAɵõ45ʾӦ. 
4QCDйظԼĲԽreal*8

Լ㹦CMRЧٶ/Mflops
0ֵV=093.6% 7.7
1V=V+const*V180.0%24.0
2V=M*V168.9% 37.3
3M1=M2*M315.8%101.1


5VECLIBиԼĲԽǰ4Ϊreal*83Ϊreal*4

Լ㹦CMRЧٶ/Mflops
0V(i)=V1(ind(i))79.9%24.1
1V=a*V1+V72.1% 33.5
2V=M*V144.8%66.2
3M1=M2*M321.8%93.8
1V=a*V1+V74.5%61.2
2V=M*V143.2% 136.3
3M1=M2*M316.7% 199.9


ͨԲԽķڳҪע3㣺
(1) ʹ23㣬ܵʹá顱.
(2) ͬԼҲͬʹVECLIBɻýϸߵЧٶȣҪΪVECLIBеĴѾŻԵ.һMPPϵͳƵĿ򣬽龡.
(3) 0Լ㣬ЧٶȶǺܵ͵ģûӦܿ. 
3.2ӿɶԣCacheȱʧʱ
3.2.1Ϊָ洢Σ1,2ݣͣٶȽϸߵĴ洢
MPPϵͳô洢νṹδ洢ٶҲͬڳ˹ָ洢ΣMPP FORTRANиùܣٶȲܴӰ.
SPP1200ϵͳĴ洢Ϊ6 ,Ƿֱǣ
 Cache0CPUͬһϵĴ洢
 ߳˽ã1רһ̵ִ߳Ĵ洢
 ˽ã2רһ̵߳Ĵ洢
 CTI Cache3CTI(coherent toroidal interconnect)ݵĴ洢
 4פͬĽϵȫִ洢
 Զ5פ㲻ͬĽϵȫִ洢.ǰ4ھֲ洢ͣΪȫִ洢.
SPP1200ϵͳиQCDеֵʹCXPAɷֱñ6ʾļͬδ洢Cacheȱʧ.Щݲѿ洢ԽͣCMRҲԽС.
6SPP1200ϵͳʹòͬ洢CMR

㹦߳˽ý˽ýԶ
ֵV=048.6%86.9%89.9%91.2%


,ǻڳָ洢ϵͳĳЩҪܵӰ˲ԣóǸQCDеFermion.Խ7ûڳΪָϵͲδ洢CacheӳʱһЧ;.ͬأֲӦھ˺;󣨻ֵУҲյƵЧԣ. 
7ָ洢ζCacheӳٵܵӰ

洢ε˷CPUʱʱٱӳʱCMR
ȱʡ 1094496474.9935.76.925142.679.5%
ָ˽109 4495322.8835.76.373994.975.3%


3.2.2ݿռ䣬ӿɶ
ͿѧݼҲӴģһܾкüֳ.MPPϵͳͨ϶̵Cache߳˽ٶȽϿĴ洢ҲúܴԱ֤㿪ʼʱܹȫȣCacheӳʱ.ΪˣǿͨѲĴֽɾСÿֻ߳вķﵽϵͳЧٶȵĿ.ΪñݵַλCacheٶȽϿĴ洢ϣͬʱҲڷϵͳȡ.
ֱʹøQCDеľ-˳һɳ㷨160160άNavier StokesCFD루嶯ѧ⣬FORTRAN 90򣩣SPP1200ϵͳCXPA߿ɲݷֽԼʱӰЧ.ݼ8. 
8ݷֽԲлʱӰ

㹦δֽCMRֽCMR
-ˡV=M*g42074.9%273.6(4)72.6%
Navier Stokes46.828.8%8.78(8)9.2%


4 
ģдӦܲȡϵͳҲʹߵƷֱ.ĽExemplar SPP1200/XAϵͳΪMPPϵͳڴͿѧձڵЧٶƫ⼰Ҫԭ򣬲ڲ㷨ͿɶԿCacheӳʱӶϵͳӦٶȵķʵ̽.ʹлӦΪеʵֵܴﵽгһ£Ǹ൱ӵ⣬ֻMPPӦüоһС棬ԸЩ̽ܶԲлʹ߻ĳЩվʹ߲һʾ.
߼飺壬У19472ڣоΪ̺㷨.ܾУ19462ڣѧߣҪо.
ߵλ塡֣ݹҵѧѧ뼼ϵ֣ݡ450002
ܾѧġпǶ١40506
ο
1Exemplar SPP 1200/XA Scalable Computing System. Richardson, TX Convex Computer Corporation, 1995. 327, 118143
2Convex Users Group PresentationFortran 90. In: Proc of the 11th Annual Convex User Group Worldwide Conf. Dallas, Texas HP-Convex Technology Center, 1996.144
3Fortran Optimization Guide. Richardson TX: Convex Computer Corporation, 1990
4Hillis W D, Steele G L. Data parallel algorithms.Commun ACM,1986, 29(12):11701179
5Bonniger T, Esser R, Krekel D. CM-5E, KSR2, Paragon XP/S: A comparative description of massively parallel computers. Parallel Computing, 1995,21(2):199232
6Hwang Kai. Advanced Computer ArchitectureParallelism Scalability Programmability. New York:McGraw-Hill Inc1993.2023
ԭյڣ1997-11-18
޸ĸյڣ1998-03-23
