给出一个新的MPI Allgather算法--邻居交换算法(neighbor exchange).提出的平均逻辑通信距离的概念和计算公式,可以有效地衡量通信的局部性.通过分析,发现在4种MPI Allgather算法中,邻居交换和环算法均具有最优的通信局部性.在万亿次机群深腾6800和曙光4000A上对4个MPI Allgather算法进行的性能测试和分析结果表明,邻居交换算法的长消息通信性能最优,中长消息通信性能不稳定,短

] 维普资讯 http://www.77cn.com.cn

}

}

;第2 9卷第 5期 20 0 6年 5月

计

算

机

学

报

CHI NES 0URNAL 0F C0M PUTE EJ RS

2 N. 9 o5M a 06 y 20

}

一

种新的 MP l ah r法及其在万亿次机群 I l te算 A g系统上的实现与性能分析陈靖”张云泉

张林波合肥北京

”(国科学技术大学计算机科学与技术系中。(国科学院软件研究所并行计算实验室中

(国科学院计算机科学国家重点实验室北京中”(国科学院数学与系统科学研究院北京 1 0 8 )中 0 0 0 (国科学院科学与工程计算国家重点实验室中北京 108) 0 0 0

摘

要给出一个新的 MP l ah r IA l te算法——邻居交换算法 ( e h o x hn e.出的平均逻辑通信距离的 g n i b r ca g )提 g e

概念和计算公式，以有效地衡量通信的局部性 .过分析，现在 4种 MP lahr法中，居交换和环算法可通发 I gte算 Al邻

均具有最优的通信局部性 .在万亿次机群深腾 60 8 0和曙光 4 0 A上对 4 MP lah r 00个 I g te算法进行的性能测试和 Al分析结果表明，邻居交换算法的长消息通信性能最优，中长消息通信性能不稳定，消息通信性能次于递归倍增和短B uk算法 . rc

关键词

MP lah r I g te算法； Al集合通信 I性能评测；机群

中圈法分类号 TP 0 31

I pl m e t to n r o m a c m e n a i n a d Pe f r n e Ana y i fa Ne M PI Alg t e l s s o w la h r

Al o ihm n Te a c l nu u t r g rt o r s a e Li x Cl s e sCHEN ig。 Z Jn’ HANG n Qu n。 Z’ Yu— a。 ’ HANG i— o LnB YUAN e。 W i’

”( p rme t f C mp trS in e U i e s y o ce c n c n lg f C ia,He e 2 0 2 ) De a t n o u e ce c, n v r i f S i ea d Teh oo y o h n o t n f i 3 0 6

。( a oao y

o a al o uig,Isi t fS i w r,C iee a e f S i cs ejn 1 0 8 ) L b rtr f P rl lC mp tn e nt ue o t a e hnsAc d myo ce e,B iig 0 0 0 t o n。( tt y L b r t r f C mp trS in e h n s Ac d my o ce c s Be i g 1 0 8 ) S a eKe a o a o y o o u e ce c,C i ee a e f S in e, i n 0 0 0 j ( a e f Mah ma i n y tmsS i c s h n s a e f S in e,B ii g 1 0 8 ) Ac d myo t e t sa d S s c e ce e,C i ee n Ac d my o c cs e n 0 0 0 e j ( tt e a o a o y o ce t i a d En n e ig C mp tn S a eK y L b r t r f S i i c n gie r o u i g.C i ee a e f S in e。B iig 1 0 8 ) n f n h n s Ac d my o ce c s ejn 0 0 0

Ab ta t M e s g a sn n ef c M PI i o e o h s mp ra tp r l lp o r mmi g sr c sa eP s ig I tra e( ) s n ft e mo ti o t n a al r g a e ne v r n n . Th PI l r r r v d s p i t t— o n n o lc i e c mmu ia i n f n to s n io me t e M i a y p o i e o n—o p i t a d c l t o b e v nc t u cin, o

a o g wh c P la h ri n ft e mo tfe u n l s d f n t n . Th e i d fag— m n ih M IAl t e so eo h s r q e ty u e u ci s g o r e kn s o l or h a e i l me t d f r PIAl a h ri h a e t e so so PI i m r mp e n e o t M l t e n t e l t s r i n fM g v CH,i e,t ern . . h i g,t er— h e c r i e d u l g a d t e B u k a g rt m s I r e o mi i z h u sv o b i n h r c l o ih . n o

d r t n mi e t e TCP t a fc a d c n e t n n r fi n o g s i o

o e a tEt e n t t e a t o s p o o e a n w M PIAl ah rag rt m,n mey t e n i h o v rF s h r e, h u h r r p s e l t e lo ih g a l h eg b re c a g .I h e g b re c a g l o ih, r p r y o a r wi ec mmu i a in i i c r o x h n e n t e n i h o x h n e ag rt m a p o e t f i— s o p n c t s n o p— o r t d a d a p o e s a wa s e c a g s d t t t o ia eg b r p o e s s A e c n e t a e n r c s l y x h n e a a wih is l g c ln i h o r c s e . n w o c p,

t e Av rg gc lC mm u ia in Dit n e( h e a e Lo ia o n c t sa c AL o CD),i r p s d t a u e t e ag rt mi s p o o e o me s r h lo ih cc m mu ia i n l c l y An l s so h CD o h o r ag r h s r v a s t a h eg b r o n c t o a i . o t a y i n t e AL f rt e f u l o i m e e l h tt e n i h o t收稿日期 z0 5i-3修改稿收到日期：0 60一O本课题得到国家自然基金重点项目 (0 30 0、家自然科学基金 (0 0 0 0、 0一2i; 2 2 0— l2 . 6 5 32 )国 63 3 2 )国

家“九七三”重点基础研究发展规划项目基金( 9 9 3 8 5 2 0 C 3 1 0 )国家“ GI 9 0 2 0,0 5 B 2 7 2、八六三”高技术研究发展计划项目“高性能计算机及其核心软件”大专项课题“性能计算机性能测试技术及方法研究” 2 0 AA14 2 )中国科学院软件研究所培育项目基金 ( XK26 8重高 (04 000、 C 52)和北京邮电大学网络与交换技术国家重点实验室开放课题( 0 50 ) 2 0—5资助.陈靖，, 9 1年生，士研究生，女 18硕主要研究方向为并行程序设计和性能评价.— i j g

hn E mal i e e@ma.d p. cc .:n i rcsa.n张云泉。 17 l男， 9 3年生，博士，副研究员，士生导师，硕主要研究领域为大型并行数值软件、并行程序设计和性能评价、行计算模型和非数值并行计算 .林波，,9 2年生，士，究员。究领域为计算数学、行并张男 16博研研并计算.寰伟，,9 9年生，士，程师，要研究方向为并行数据挖掘、行程序设计和性能评价 .男 17硕工主并