（电子科学与技术专业论文）基于kary+ntree的硬件聚合通信技术研究.pdf

国防科学技术大学研究生院博士学位论文 此在单播和组播并存的互连网络中，m s f s 能够与f c f s 进行“无缝”集成。 5 建立了无冲突和有冲突条件下的归约延迟模型，并具体分析了不同类型的冲突 对归约延迟的影响。证明了剩余集中的调度算法能够取得多个归约操作在路由 器上平均延迟的最小值；提出了使用f c f s 策略解决归约报文之间冲突，以减 小后调用操作对先调用操作的性能影响；提出使用归约报文优先的策略解决单 播报文和归约报文之间的冲突，以减小单播对归约性能的影响。 本文基于离散事件模拟平台o m n e t + + 开发了多级互连网模拟器m i n s i m c c 。 模拟结果表明，本文提出的负载平衡策略和报文调度算法都能够有效的提高聚合 通信的性能。 主题词：高性能计算，互连网络，k - a r y 刀一t r e e ，聚合通信，组播，归约， 负载平衡，报文调度 国防科学技术大学研究生院博士学位论文 a b s t r a c t c o l l e c t i v ec o m m u n i c a t i o ni sac o m m u n i c a t i o np a t t e mw h i c hi n v o l v e sag r o u po f p r o c e s s e s ，a n di ti su s e dc o m m o n l yi ns c i e n t i f i ca n de n g i n e e r i n gc o m p u t i n g a c c o r d i n g t ot h ed a t aa n a l y z i n g ，t h ec o s to ft h ec o l l e c t i v ec o m m u n i c a t i o na c c o u n t sf o r8 0 o ft h e c o s to fw h o l ec o m m u n i c a t i o na n d6 0 o ft h ee x e c u t i n gt i m ei ns o m el a r g e - s c a l ep a r a l l e lp r o g r a m s c o l l e c t i v ec o m m u n i c a t i o nh a sb e c o m eap e r f o r m a n c eb o t t l e n e c kf o rh i g h p e r f o r m a n c ec o m p u t i n gs y s t e m t h et r a d i t i o n a ls o f t w a r e b a s e da p p r o a c hi sn o ts u i tf o r t h ep e r f o r m a n c er e q u i r e m e n t h o wt os u p p o r tc o l l e c t i v ec o m m u n i c a t i o na th a r d w a r e l e v e lb e c o m e sa ni m p o r t a n tp r o j e c t t h ei n t e r c o n n e c t i o nn e t w o r kb a s e dc o l l e c t i v ec o m m u n i c a t i o no y c c ) h a sb e e nr e s e a r c h e dw i d e l ya n d d e e p l ys i n c eb e i n gp r o p o s e d m o s to f t h ee x i s t i n gr e s e r c h e sm a i n l y c o n c e r nw i t ht h ei m p l e m e n t a t i o no fl n c c ，s u c ha st h ef u n c t i o ne x t e n do ft h er o u t e r ，t h e a d d r e s s i n ga n dr o u t i n go ft h ep a c k e t ，a n dt h es o l v i n go ft h ed e a d l o c k t h ei n c cp e r - f o r m so n e - t o m a n ya n dm a n y t o o n eo p e r a t i o no nt h er o u t e r ，w h i c hi n c r e a s e st h ep a c k e t c o n f l i c ta n dm a k e st h ep e r f o r m a n c eo fi n c cm o r es e n s i t i v et op a c k e tc o n f l i c tt h a nt h a t o fu n i c a s t t h e r e f o r e ，t of u r t h e ri m p r o v i n gt h ep r a c t i c a lp e r f o r m a n c eo fi n c c ，t w oi s - s u e ss h o u l db ec o n s i d e r e d o n ei sh o wt or e d u c ep a c k e tc o n f l i c t ，a n dt h eo t h e ri sh o wt o s o l v et h ep a c k e tc o n f l i c tt h a th a so c c u r r e d d e t a i l e dr e s e a r c hw o r k sh a v eb e e nd o n eo n t h e s et w oi s s u e sb a s e do nk - a r yn - t r e e t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s ： 1 t h et o p o l o g yc h a r a c t e r i s t i co fk a r yn - t r e ei sr e s e a r c h e dd e e p l y a ne q u i v a l e n c e r e l a t i o no nr o u t e r so fk - a r y 刀- t r e ei sd e f i n e d ，a n dt h er a n g eo fr o u t e r st h a ta r e p a s s e dt h r o u g hb yt h es a m ep a t ho rt h es a m ec o l l e c t i v ec o m m u n i c a t i o nt r e ei s f o r m u l a r l yd e s c r i b e d ，w h i c hl a yt h ef o u n d a t i o nf o rl o a db a l a n c eo nk - a r yn - t r e e 2 ap o l i c yp u r c h a s i n gg l o b a ll o a db a l a n c eo fc o l l e c t i v ec o m m u n i c a t i o ni sp r o p o s e d a tt h eu p w a r d i n gp h a s eo fs p a n n i n gt r e eb u i l d i n ga l g o r i t h m ，t h i sp o l i c yu s e st h e c o l l e c t i v ec o m m u n i c a t i o nl o a do fe a c he q u i v a l e n c ec l a s sa st h ec r i t e r i ao ft h el e a s t l o a dp a r e n ts e l e c t i n g ，w h i c hg u a r a n t e e st h eb a l a n c e dd i s t r i b u t i o no fc o l l e c t i v e c o m m u n i c a t i o nl o a da n dr e d u c e st h ec o n f l i c ta m o n gc o l l e c t i v ec o m m u n i c a t i o n p a c k e t s 3 t h eo c c u r r e n c ea n ds p r e a do fm u l t i c a s t c o n g e s t i o n i s a n a l y s i s e d ， a n dt h e l o o k a h e a da d a p t i v er o u t i n ga l g o r i t h mf o ru n i c a s t 。i sp r o p o s e d a tt h eu p w a r d p h a s eo fu n i c a s tp a c k e tt r a n s m i s s i o n , t h i sa l g o r i t h mf o r e c a s t st h em u l t i c a s tc o n - g e s t i o na c c o r d i n gt ot h em u l t i c a s tl o a do fc u r r e n tr o u t e ra n dc o n t r o l st h eo u t p u t p o r ts e l e c t i n go fu n i c a s tp a c k e tb ym u l t i c a s tc o n g e s t i o nb a s e do nt h ef o r e c a s tr e - s u i t ，w h i c hc a np r e v e n tu n i c a s tp a c k e t sp a s s i n gt h r o u g ht h er o u t e rw h e r em u l t i c a s t c o n g e s t i o ne x i s ta n da l l e v i a t et h ed e g r a d a t i o no fn e t w o r kp e r f o r m a n c ec a u s e db y 第i i i 页 国防科学技术大学研究生院博士学位论文 m u l t i c a s tc o n g e s t i o n 4 b a s e do nt h ef a c tt h a th i g hp e r f o r m a n c ec o m p u t e ri ss e n s i t i v et on e t w o r kl a t e n c y ， am u l t i c a s ts c h e d u l i n ga l g o r i t h mn a m em s f s ( m a x e ds e r v e df i r s ts e r v e d ) i s p r o p o s e d t om i n i m i z et h et r a n s m i t t i n gl a t e n c yo fm u l t i c a s tp a c k e to nt h er o u t e r , m s f sa s s i g n sp r i o r i t yt oam u l t i c a s tp a c k e ta c c o r d i n gt ot h en u m b e ro fo u t p u t p o r t sw h i c hh a v er e c e i v e dt h ep a c k e ta n dt h ew a i t i n gt i m eo ft h ep a c k e ta tt h e h e a do fb u f f e r i n gq u e u e m s f sg i v e sa t t e n t i o nt on e t w o r kt h r o u g h p u ta n dp a c k e t l a t e n c ys i m u l t a n e o u s l y i ft h eu n i c a s tp a c k e ti sr e g a r d e da sm u l t i c a s tp a c k e tw i t h o n ed e s t i n a t i o np o r t ，m s f si s e q u a lt of c f su n i c a s ts c h e d u l i n ga l g o r i t h m t h e r e f o r e ，m s f sc a nb ei n t e g r a t e df c f ss m o o t h l yo nn e t w o r kw h e r eu n i c a s ta n d m u l t i c a s tc o e x i s t s 5 1 r i l er e d u c t i o n - l a t e n c ym o d e l sw i t hc o n f l i c ta n dn o n c o n f l i c ta r em a d e a n dt h e i m p a c to fd i f f e r e n tk i n d so fp a c k e tc o n f l i c to nt h er e d u c t i o nl a t e n c yi sa n a l y z e d i t i sd e m o n s t r a t e dt h a tt h er e s i d u ec o n c e n t r a t i o ns c h e d u l i n ga l g o r i t h mc a na c h i e v e m i n i m u ma v e r a g el a t e n c yo fm u l t i p l er e d u c t i o no p e r a t i o no nt h er o u t e r t h e f c f sp o l i c yi sp r e f e r e dt os o l v et h ec o n f l i c ta m o n gr e d u c t i o np a c k e t st or e d u c e t h ei m p a c to fr e d u c t i o no p e r m i o nb e i n gc a l l e dl a t e ro nt h eo p e r a t i o nb e i n gc a l l e d e a r l i e r 1 1 1 er e d u c t i o np a c k e tf i r s ts e r v e dp o l i c yi sp r e f e r e dt os o l v et h ec o n f l i c t a m o n gu n i c a s tp a c k e t sa n dr e d u c t i o np a c k e t st or e d u c et h ei m p a c to fu n i c a s to n t h er e d u c t i o nl a t e n c y t h es i m u l a t o rf o rm u l t i s t a g ei n t e r c o n n e c t i o nn e t w o r k sn a m e dm i n s i m c ci si m p l e m e n t e db a s e do nt h ed i s c r e t ee v e n t - d r i v e ns i m u l a t i o np l a t f o r m0 n q e l 、斗斗t h es i m u l a t i o nr e s u l t ss h o wt h a ta l lt h ep r o p o s e dl o a db a l a n c ep o l o c i e sa n dp a c k e ts c h e d u l i n g p o l o c i e sc a l la c h i e v et h e i ro w ng o a l se f f e c t i v e l y k e yw o r d s ：h i g h p e r f o r m a n c ec o m p u t i n g ，i n t e r c o n n e c t i o nn e t w o r k s ， k - a r yn - t r e e ，c o l l e c t i v ec o m m u n i c a t i o n ，m u l t i c a s t ，r e d u c t i o n ，l o a db a l a n c e ，p a c k e ts c h e d u l i n g 第i v 页 国防科学技术大学研究生院博士学位论文 图1 1 图1 图1 图2 图2 图2 3 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图5 9 图5 1 0 图5 1 1 图目录 分布式存储多处理机体系结构1 选主元的高斯消去算法4 聚合通信报文在中间节点的处理流程6 多目标地址编码1 2 二维m e s h 中使用x y 路由的组播相关1 5 树型组播中的死锁1 6 o m n e t + + 模型的结构2 5 o m n e t + + 的建模流程2 6 m s i m c c 的顶层结构一2 7 m i n s i m c c 的路由器结构2 7 m 【n s i m c c 的路由器端口模块结构2 8 m i n s i m c c 的执行模型。2 9 4 - a r yn - t r e e 实例( 1 1 - 1 ，2 ，3 ) 3 6 k - a r yn t r e e 上的单播报文路由算法3 8 k - a r yn t r e e 上的单转向组播报文路由算法3 9 目标节点均匀分布时路由器的单播负载一4 2 目标节点局部性分布时路由器的单播负载4 3 目标节点均匀分布时单棵聚合通信树的网络负载4 4 目标节点局部性分布时单棵聚合通信树在s n d 内的网络负载4 5 目标节点局部性分布时单棵聚合通信树在跳外的网络负载4 6 路由表项的结构。4 8 4 a r y2 t r e e 中的路由表配置实例4 8 s a m e e rk u m a r 聚合通信树构建算法4 9 s a m e e rk u m a r 最轻负载父节点选择算法。5 0 l l ps 聊最轻负载父节点选择算法5l 三三尹幽f 最轻负载父节点选择算法5 2 聚合通信树构建实例5 5 目标节点均匀分布时不同父节点选择策略下的组播性能一5 6 目标节点局部性分布时不同父节点选择策略下的组播性能5 7 指定进程组内的处理节点时不同父节点选择策略下的组播性能5 8 目标节点均匀分布时不同父节点选择策略下的归约性能5 9 第v i i 页 国防科学技术大学研究生院博士学位论文 图5 1 2 图5 1 3 图6 1 图6 2 图6 3 图6 4 图6 5 图6 6 图6 7 图6 8 图6 9 图6 1 0 图 图 图 图 1 2 - 3 4 图7 5 图7 6 图7 7 图7 8 图8 1 图8 2 图8 3 图8 4 图8 5 图8 6 图8 7 图8 8 图8 9 图9 1 图9 2 图9 3 图9 4 图9 5 目标节点局部性分布时不同父节点选择策略下的归约性能6 0 指定进程组内的处理节点时不同父节点选择策略下的归约性能6 l 单播报文的反转路径描述符一6 4 报文上升过程中的组播拥塞。6 6 报文下降过程中的组播拥塞6 7 组播拥塞区域预测6 8 前瞻自适应路由器策略的硬件实现7 0 = 6 4 时不同阈值下的单播和组播延迟比较7 3 目标节点均匀分布且= 0 5 时不同单播路由算法的性能7 5 目标节点局部性分布且= 0 5 时不同单播路由算法的性能。7 5 目标节点均匀分布且= 0 2 时不同单播路由算法的性能7 7 目标节点局部性分布且= 0 2 时不同单播路由算法的性能7 7 仲裁器的连接8 3 组播报文的优先级确定。8 6 目标节点均匀分布且= 1 时不同调度算法的性能8 9 目标节点局部性分布且= 1 时不同调度算法的性能8 9 目标节点均匀分布且= 0 5 时不同集成调度算法的性能9 1 目标节点局部性分布且= 0 5 时不同集成调度算法的性能9 1 目标节点均匀分布且= 0 2 时不同集成调度算法的性能。9 3 目标节点局部性分布且= 0 2 时不同集成调度算法的性能9 3 归约计算单元结构9 6 路由器处理归约报文的时空图9 7 4 a r y4 t r e e 中不同归约调度算法的性能1 0 5 目标节点均匀分布时不同归约调度算法的性能1 0 6 目标节点局部性分布时不同归约调度算法的性能1 0 6 目标节点均匀分布且m r = 0 5 时不同集成调度算法的性能1 0 8 目标节点局部性分布且m r = 0 5 时不同集成调度算法的性能1 0 8 目标节点均匀分布且m r = 0 2 时不同集成调度算法的性能1 0 9 目标节点局部性分布且膨= 0 2 时不同集成调度算法的性能1 1 0 路由器的顶层结构1 1 2 l l p 微片结构1 1 3 信用维护示意图1 1 4 单播缓存队列的状态转换1 1 5 组播缓存队列的状态转换1 1 6 第v i i i 页 国防科学技术大学研究生院博士学位论文 图9 6 组播缓存队列的f i f o 结构1 17 图9 7 最大优先级计算逻辑117 图9 8 最大值计算单元118 图9 9 仲裁延迟优化。1 2 0 第页 国防科学技术大学研究生院博士学位论文 表目录 表1 1聚合通信操作的分类与定义4 表5 1聚合通信负载平衡策略模拟时的参数配置5 5 表6 1单播路由算法模拟时的参数配置7 3 表7 1集成调度算法模拟时的参数配置8 8 表8 1归约调度和集成调度需要优化的参数9 9 表8 2 归约调度算法模拟时的参数配置1 0 4 第x i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成栗。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目： 基王垦= 垒! y 垒= 三璺曼数焦往塞佥适焦拉苤盟究 学位论文作者签名：扯全：垂 日期：2 叨宫年月；口日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书 学位论文题目： 基王壁二垒! z 璺= ! 三曼叟煎矍佳塞金通焦拉苤叠究 学位论文作者签名：丕2 = 企望日期：2 鲫9 - 年6 月3 0 日 作者指导教师签名： 距& 丝 日期：p 咕年多月3 矿日 国防科学技术大学研究生院博士学位论文 第一章绪论 聚合通信在科学和工程计算中有着非常广泛的应用，对高性能计算机系统的 性能有着重要影响。基于软件的实现已经不能满足技术发展的需求，如何通过网 络硬件对聚合通信进行支持成为一个重要的研究课题。 1 1 课题背景 现代科学的发展依靠理论研究、科学实验与计算技术三种重要手段，其中计 算技术的发展带来了理论研究的深入、科学实验速度的加快和实验成本的降低， 成为人类科学研究必不可少的方法之一。 随着微电子技术的不断发展，微处理器的运算速度3 0 多年来提高了6 个数量 级。但是，单机的性能仍然满足不了来自科学、工程、商业等应用领域对计算能 力的需求。使用多个处理器的大规模并行处理技术为高性能计算机( h i g hp e r f o r m a n e ec o m p u t e r ，简称h p c ) 的实现提供了解决方案。高性能计算机技术是整 个信息技术的制高点，一直以强大的辐射力带动着信息技术的发展。继“加速战 略计算创新( a s c i ) ”计划【l j 之后，美国国防部高级研究计划局( d a r p a ) 在 科学论证、严密组织下，又提出一项高性能计算机研究计划“高产出率计算 系统( h p c s ) 2 1 ，h p c s 旨在填补起始于8 0 年代的h p c 技术与未来的新概念计算 之间的空隙，以取得新结构、新技术、新器件、新工艺的突破性进展，将高性能 计算机技术的研究推向新的高潮。 高性能计算机由一组处理节点组成，处理节点之间通过互连网络进行通信与 协作。高性能计算机硬件系统的发展也主要体现在处理节点和互连网络的性能提 高。一种典型的高性能计算机体系结构( 分布式存储多处理机) 如图1 1 | 3 1 所示。 图1 1分布式存储多处理机体系结构 第1 页 国防科学技术大学研究生院博士学位论文 1 1 1 互连网络成为h p c 的性能瓶颈 从上世纪8 0 年代以来，微处理器( c p u ) 的性能提高基本上遵循了著名的摩 尔定律每1 8 个月翻一番。这主要来源于三个因素：电路速度、流水线深度和 指令级并行。从现在的情况看，流水线设计已接近每一站8 - 1 6 个f 0 4 ( f a n - o u t o f - f o u r ) 反相器延迟的最低下限【4 j ，流水线级数的增加即将终止。随着 集成电路制造工艺进入深亚微米阶段，受功耗和制造成本的限制，电路速度的增 长也已经放缓。为了保证性能的持续增长，目前的微处理器技术已经开始向单芯 片多核、单芯片多线程以及片上系统等方向发展。i n t e l 在其微处理器发展蓝图中 指出，今后应用于不同领域的c p u 都将采用多核结构。2 0 0 6 年推出的基于c o r e 构架的c o n r o e ( 酷睿2 ) 【5 1 ，处理器核基于p e n t i u mm ，i m e l 的数据表明c o n r o e 比上一代处理器在性能上提高了4 0 ，而功耗降低了4 0 。在2 0 0 5 年国际固态电 路会议( i s s c c ) 上，i b m 、s o n y 和t o s h i b a 首次公开介绍了被称为片上超级计算 机的高性能处理芯片e l l 【6 1 。c e l l 可以在4 g h z 的频率下工作，峰值浮点运算 速度为2 5 6 g f l o p s ，支持完全符合i e e e7 5 4 标准的双精度浮点运算，其速度约是单 精度的十分之一，为2 5 3 0 g f l o p s 。即使这个速度，也达到了当前主流高性能微处 理器的5 - 1 0 倍。由于这些新技术的不断采用，在未来十几年之内，微处理器的 性能提高还会按这种规律持续下去【7 j 。 互连网络是高性能计算机系统中连接处理器、存储器、i o 设备的重要组成部 分，承担不同处理节点间的同步和通信。互连网络是影响整个高性能计算机系统 性能和扩展性的重要因素。根据a s c i 计划对硬件系统的量化指标，要实现百万亿 次以上的计算能力，互连网络的延迟和带宽是必须首先解决的关键问题( 临近节 点访存延迟为3 0 0 5 0 0 个f l o p s 的执行时间、带宽为8 - 6 4 b f l o p s ；远程节点的访存 延迟为1 0 0 0 个f l o p s 的执行时间、带宽为8 b f l o p s ) 【l 】。微处理器技术的发展使得 处理节点的计算能力迅速提高，也对互连网络的性能提出了更高的要求。然而在 实际上，互连网络带宽的提高与微处理器性能的提高有着3 0 多的差距，互连网 络带宽每年以大约2 6 的速度提高，远低于处理器性能每年5 9 的提高速度。预 计到2 0 1 0 年，远程节点的访存延迟将达到9 0 0 0 个f l o p s 的执行时间、带宽只能达 到o 5 b f l o p s ，而到2 0 2 0 年，远程节点的访存延迟将达到惊人的6 7 0 ，0 0 0 个f l o p s 的执行时间、带宽只能达到0 0 5 b f l o p s 【7 1 。因此互连网络的延迟和带宽已成为制约 高性能计算机性能提高的瓶颈之一。 第2 页 国防科学技术大学研究生院博士学位论文 1 1 2 技术发展限制 电互连的发展限制 高性能互连网络的设计与实现主要体现在拓扑结构、切换技术、报文调度和 路由算法几个方面。随着设计与实现技术的逐步成熟，电互连网络性能的进一步 提高主要依靠集成电路技术和高速电信号技术的发展。随着集成电路特征尺寸的 不断缩小和工作频率的不断提高，漏电流、热功耗以及物理尺寸的极限成为路由 器芯片性能进一步提高难以逾越的障碍【9 j 。高速串行链路的使用可以大幅度减少路 由器芯片的引脚数目，使得高维度路由器的实现成为可能【l 们。由高维度路由器构 成的互连网络只需要几个跳步( h o p ) 就可以连接成千上万个处理节点，商用网络 m y r i n e t 的路由器维度为3 2 【l l 】，c r a y 公司推出的b l a c k w i d o w 高性能计算机的路由 器维度高达6 4 ，包含3 2 k 个处理节点的系统中，一个报文最多经过7 个跳步便可 到达目标节点【1 2 1 。但是信号传输过程中的衰减、反射、串扰以及电源噪声等影响 着链路有效带宽的增加和系统的可靠性。由于这些固有的限制，传统的电互连网 络已经不能满足高性能计算技术发展的需求。 光互连的发展限制 从长远来看，全光互连技术成为高性能互连网络的一种发展趋势。在h p c s 计划中，i b m 提出了使用全系统光互连的p e r c s ( p r o d u c t i v i t y ，e a s y t o u s e ，r e l i a b l e c o m p u t i n gs y s t e m ) 计算系统，d a r p a 也在其d o d - n ( d a t ai nt h eo p t i c a ld o m a i n n e t w o r k i n g ) 计划下开展了对全光互连的研究【1 3 】。i b m 与c o m i n g 公司合作研究的 高速光互连网络中，使用具有低切换时间的s o a ( s e m i c o n d u c t o ro p t i c a la m - p l i f i e r s ) 光开关实现电信号控制下的数据光交换，该网络的带宽将达到每个端口 4 0 g b s ，并具有良好的可扩展性【1 4 】。目前，光互连和光交换技术的研究十分广泛， 但就其技术发展水平来说，尚处于初级阶段。要想发挥光互连的潜力，还面临着 光材料、封装工艺、功耗等许多方面的挑战。 综上所述，在现有电互连技术的基础上，通过对路由器各个部件的功能进行 调整、扩展来支持系统需要的新功能，仍然是当前提高互连网络性能的一种重要 手段。 1 1 3 亟待提高的聚合通信性能 高性能计算机系统是由分布在不同处理节点上的多个进程协作完成一个复杂 问题的求解，多个进程之间通过消息传递来进行数据交换和控制任务运行。根据 第3 页 国防科学技术大学研究生院博士学位论文 参与操作的处理节点数的不同，通信操作可以划分为单播通信和聚合通信两大类。 单播通信包含一个源节点和一个目标节点。而聚合通信是由运行在多个处理节点 上的一组进程参与的通信模式，这些进程定义在一个称为“进程组”的上下文中。 聚合通信可以进一步划分为数据迁移、进程控制和全局计算三大类，包括组播 ( m u l t i e a s t ) 、分布( s c a r e r ) 、汇集( g a t h e r ) 、栅栏同步( b a r r i e r ) 、归约( r e d u c t i o n ) 、 并行前缀( p a r a l l e lp r e f i x ) 等基本操作。聚合通信操作的分类与定义如表1 1 所示。 在所有的聚合通信操作中，组播和归约在并行应用中使用最广泛，也可以用来支 持其它聚合通信操作的实现【l 引。 表1 1聚合通信操作的分类与定义 种类操作描述 组播 一个进程给组内所有其它进程发送相同的数据 数据移动 分布一个进程给组内所有其它进程发送不同的数据 汇集一个进程接收组内所有其它进程发来的数据 进程控制栅栏同步组内所有进程都到达一个控制点后才能继续运行 归约分布在组内所有进程上的数据形成一个运算结果 全局计算 并行前缀 每个进程在相关进程上进行部分归约 聚合通信能够简化多处理器系统的编程，在科学和工程计算中有着非常广泛 的应用。以使用高斯消去法求解等式a x = b 为例( 其中彳是n x n 矩阵，x 、b 是以 元向量) ，为了进行高效的数据处理，矩阵彳存储在a 1 ：，z ，1 ：n 】中，向量b 存储在 a 1 ：”，n + i 中，向量x 存储在a o ，l ：n 】中。选主元高斯消去法的伪高级并行语言 描述如图1 2 所示【8 1 。 1 d o i = l ，n 2 m a x ( a i ，i ：n 】，v a t , l o c ) ； 3 e x c h a n g e ( a o ：n ，i 】，a o ：n ，l o c 】) ； 4 a i ，i ：聆+ 1 】= a i ，i ：刀+ 1 】a i ，歹】； 5 d o _ ，= i + 1 ，z 6d o k = f + 1 n + 1 7 a j ，k 】- a j ，后卜a j i i 宰a i ，k 】； 8e n d d o 9e n d d o 1 0e n d d o 图1 2 选主元的高斯消去算法 第4 页 国防科学技术大学研究生院博士学位论文 在图1 2 的算法中，第2 行中的函数m a x 描述了一个求最大值的归约操作， 作用是找到主元的位置；第3 行中的函数e x c h a n g e 将a 的第f 列和主元所在的 列进行置换；使用数据相关性分析发现，第5 行和第6 行中的循环是可以并行的； 第7 行的语句也隐含了将数据复制到多个处理节点上的操作；第8 行和第9 行的 e n d d o 语句隐含了栅栏同步操作。这些数据迁移和进程控制操作都属于聚合通 信。 从应用的角度来看，h p c 的性能主要体现在应用程序的执行时间上。许多并 行程序的执行都是计算阶段和通信阶段交替进行，在计算阶段各个进程在处理节 点上独立的运行，在通信阶段执行进程间的同步和数据交换。高性能计算机存在 的一个突出问题是实际获取性能低，一般的应用程序仅能发挥峰值性能的 5 也0 ，相当数量的并行程序难以获得理想的绝对运算速度和并行效率，有些并 行程序甚至难以获得正向的加速效果。高性能计算机效率低的一个重要原因是随 着处理器性能的提高和数目的不断增加，通信开销在整个执行时间中所占的比例 不断增大。数据分析表明，在许多大规模科学和工程计算中，聚合通信的开销甚 至占到全部通信开销的8 0 t 16 1 、总执行时间的6 0 以上【1 7 】【1 8 】，已经成为高性能计 算机的性能瓶颈。受聚合通信性能影响的应用主要包括：情报处理、原子核建模、 气候建模、天体物理学以及生物系统建模【_ 7 1 。因此如何提高聚合通信的性能是一个 值得深入研究的课题。 1 2 聚合通信的实现方法 根据系统所提供硬件支持程度的不同，聚合通信的实现可以分为基于软件、 基于网络接口、基于专用网络和基于互连网络( 专指数据通信网络) 等多种不同 的方法。本节中，我们将对这些实现方法进行一一的介绍。 1 2 1 基于软件 现有的绝大多数高性能计算机系统的互连网络只支持单播通信，聚合通信操 作必须在单播通信的基础上通过设计合适的算法来实现，这种方法称为基于软件 的实现。聚合通信算法的设计主要是基于加州大学b e r k e l e y 分校的d a v i dc u l l e r 等人提出的l o g p 模型【1 9 1 ，或者是对系统进行更深层次的抽象而形成的l o g p 扩展 模型1 2 0 】【2 1 1 ，通过深入挖掘、利用系统的底层特性( 包括系统规模、报文发送和启 动开销、互连网络延迟等) 来提高性能，这方面的研究已经相当深入【2 2 】【2 3 】【2 4 】【2 5 1 。 基于软件的实现具有良好的适应性，在无需改变通信原语的情况下，可以根据实 际的需要设计不同的聚合通信算法。同时，基于软件的实现也存在如下的缺点： 第5 页 国防科学技术大学研究生院博士学位论文 报文发送和接收开销大。聚合通信报文到达中间节点后的处理要经过中 断、进程切换和报文处理等一系列过程( 如图1 3 所示) j 这些处理过程 ( 尤其是进程切换) 带来了较大的处理器开销，一方面降低了处理器的有 效工作时间，另一方面也增大了聚合通信的延迟。尤其是当报文长度较小 时，处理器接收和发送报文的软件开销占据了聚合通信延迟的主要部分。 切换到内核接 收报文 转发报文到聚合 通信守护进程 切换到聚合通信 i 守护进程 | 发送报文到下一 守护进程，保护现场i 进行报文处理i级处理节点 图1 3 聚合通信报文在中间节点的处理流程 性能受处理节点工作负载的影响。基于软件的聚合通信要获得最佳性能， 要求中间节点能够立即处理到达的聚合通信报文。如果某些处理节点正运 行操作系统守护进程【l 引，聚合通信的性能将受到影响。此外，对于由消息 驱动的聚合通信【2 7 】和异步聚合通信1 2 8 1 ，远程处理节点可能正在处理其它 的任务，从而无法立即对接收到的聚合通信报文进行处理，这也会增大聚 合通信的延迟。 产生链路冲突。基于软件的聚合通信实现中，多个中间节点转发的报文可 能在某些链路上产生冲突，这既带来了聚合通信延迟的增加，也增大了产 生网络拥塞的可能性。一种减少报文之间冲突的方法是使用栅栏同步来对 报文的发送进行同步，但是这带来了栅栏同步的额外开