（计算机系统结构专业论文）一种新的mpi_allgather算法及压缩查询并行算法研究.pdf

种新的m p ! 一a i i g a t h e r 算泣及压缩奄懒并行算法研究 摘要 摘要 消息传输界面m p i 是目前使用最广泛的并行程序设计平台，包括点到点通 f a - , 口集合通信两种模式。作为并行计算的基础，通信的性能对于并行应用程序性 能有着重要的影响。m p ia l l g a t h e r 是m p i 库中使用频率最高的集合通信函数之 ，目前“泛使用的实现算法有j ：q ：( r i n g ) 、递归倍增( r e c u r s i v e d o u b l i n g ) $ nb r u c k 算法( b r u e ka l g o r i t h m ) 。针对以太网上t c p i p 通信的特性，本文提出一种新的 m p i a l l g a t h e r 的算法一一邻居交换算法e i g h b o r e x c h a n g e ) 。本文还提出平均逻 辑通信距离的概念和计算公式，可以有效地衡量通信的局部性。通过分析，发现 在四种算法中，邻居交换和环算法均具有最优的通信局部性。我们在万亿次机群 深腾6 8 0 0 、曙光4 0 0 0 a 和华云神箭h y s j 一1 0 0 0 上对四个m p i a l l g a t h e r 算法进行 了性能测试和分析，测试结果表明，邻居交换算法的长消息通信性能最优，中长 消息通信性能不稳定，短消息通信性能次于递归倍增和b r u c k 算法。本文还将 m p ia l l g a t h e r 近邻通信的思想进行扩展，设计了m p ia l l r e d u c e 邻居交换算法。 本文另一部分研究工作集中在压缩查询并行化算法设计与实现方面。g z i p 是 现今流行的无损数据压缩软件，压缩大文件时需要较长的时间。为提高压缩解 压缩速度，我们开发了一种新的基于o p e n m p 的并行压缩软件o m p g z i p ，与g z i p 完全兼容，能够在稍微损失一点压缩比的情况下大大提高压缩速度，加速比平均 达到4 ，并行解压缩速度也有所提高。本文详细介绍了o m p g z i p 的并行思想、实 现框架、软件实现和优化技术、软件测试效果、在实现中遇到的难题、可能的解 决办法和对未来工作的展望。o m p g z i p 具有良好的应用前景。 压缩查询支持在不解丌压缩文件的情况下对源文件进行查询，是一个较新的 研究领域，目前还没有很成熟的算法。本文研究了压缩查询索引f m i n d e x 的文 件格式和算法原理，针对f m i n d e x 压缩和建立索引过程种内存需求过大的问题， 提出了分块的f m i n d e x 设计，给出了分块设计下压缩、建立索引和查询的方法， 并设计了分块方式下f m i n d e x 的并行化算法，这些设计提高了f m i n d e x 处理 大文件的能力，使它具有良好的应用前景。 关键词：m p i a l l g a t h e r ，算法，集合通信，性能评测，局部性，压缩，并行 软件，压缩查询 种新的m p ia l l g a l h e r 算法及压缩台词并行算法研究a b s 廿a c t a b s t r a c t m e s s a g ep a s s i n gi n t e r f a c e ( m p i ) i so n eo ft h em o s ti m p o r t a n tp a r a l l e l p r o g r a m m i n ge n v i r o n m e n t t h em p il i b r a r yp r o v i d e sp o i n t - t o p o i n ta n dc o l l e c t i v e c o m m u n i c a t i o nf u n c t i o n s ，a m o n gw h i c hm p l a l l g a t h e ri so n eo ft h em o s tf r e q u e n t l y u s e df u n c t i o n s t h r e ek i n d so fa i g o f i t h r na r ei m p l e m e n t e df o rm p ia l l g a t h e ri nt h e l a t e s tv e r s i o n so fm p i c h ，i e ，t h er i n g , t h er e c u r s i v ed o u b l i n ga n dt h eb r u c k a l g o r i t h m s i no r d e rt om i n i m i z et h et c pt r a f f i ca n dc o n g e s t i o no v e rf a s te t h e r n e t ， w ep r o p o s ean e wm p ia l l g a t h e ra l g o r i t h m ，n a m e l yt h en e i g h b o re x c h a n g e i nt h e n e i g h b o re x c h a n g ea i g o r i t h m ，ap r o p e r t yo fp a i r - w i s ec o m m u n i c a t i o ni si n c o r p o r a t e d a n dap r o c e s sa l w a y se x c h a n g e sd a t aw i t hi t sl o g a c a ln e i g h b o rp r o c e s s e s an e w c o n c e p t ，t h ea v e r a g el o 百c a lc o m m u n i c a t i o nd i s t a n c e ( a l c d ) ，i sp r o p o s e dt o m e a s u r et h ea l g o r i t h m i cc o m m u n i c a t i o nl o c m i t y a n a l y s i so nt h ea l c do ft h ef o u r a l g o r i t h m sr e v e a l st h a tt h en e i 曲b o re x c h a n g ea n dt h er i n ga l g o r i t h m sh a v et h eb e s t c o m m u n i c a t i o n l o c a l i t yp r o p e r t ya m o n gt h e f o u rm p i a l l g a t h e ra l g o r i t h m s n u m e r i c a le x p e r i m e n t so nl i n u xc l u s t e r sd e e p c o m p6 8 0 0 ，d a w n i n g4 0 0 0 aa n d h y s j 一1 0 0 0s h o wt h a to u rn e i r g h b o re x c h a n g ea l g o r i t h mp e r f o r m st h eb e s tf o rl o n g m e s s a g e sb u ti ss u b o p t i m a lf o rs h o r ta n dm e d i u ms i z e do n e s f o rm e d i u m - s i z e m e s s a g e s ，t h er i n ga l g o r i t h mp e r f o r m st h eb e s ta n df o rs h o r tm e s s a g e s ，t h er e c u r s i v e d o u b l i n ga l g o r i t h mp e r f o r m st h eb e s t t h i sp a p e ra l s of o c u s e so n p a r a l l e la l g o r i t h md e s i g na n di m p l e m e n t a t i o no f c o m p r e s s i o nt o o la n dc o m p r e s s e di n d e x t h o u 曲g z i pi sav e r yp o p u l a rc o m p r e s s i o n t o o l ，i tt a k e si n s u f f e r a b l et i m et oc o m p r e s sl a r g ef i l e t os p e e d u pt h eg z i p c o m p r e s s i o n ，w ed e s i g nap a r a l l e lv e r s i o no f g z i pb a s eo no p e n m p , n a m e l yo m p g z i p o m p g z i pi sc o m p l e t e l yc o m p i t a b l ew i t hg z i p ，w et e s tt h ep e r f o r m a n c eo fg z i pa n d o m p g z i po nt w os m pn o d e sa n df i n dt h a tt h es p e e d u po f o m p g z i pt og z i pi su pt o 4 i na v e r a g e t h i sp a p e ri n t r o d u c e so m p g z i pw i t hi t sp a r a l l e ld e s i g n ，i m p l e m e n t a t i o n f r a m e w o r k ，i m p l e m e n t a t i o nd e t a i l ，o p t i m i z a t i o nt e c h n i ca n dp e r f o r m a n c er e s u l t t h i sp a p e ra l s om e n t i o n ss o m ed i f f i c u l tp r o b l e m sw ee n c o u n t e rw h i l ed e s i g n i n ga n d g i v e sp o s s i b l es o l u t i o nt ot h e m o m p g z i ph a sg o o dp r o s p e c t c o m p r e s s e di n d e xs u p p o r t si n q u i r i n gt h eo c c u r r e n c e si nt h eo r i g i n a lf i l eo fa p a t t e r ns t r i n gb yl o o k i n ga to n l yas m a l lp o r t i o no ft h ec o m p r e s s e df i l e i ti sa b r a n d n e wr e s e a r c hf i e l da n dt h e r ee x i s t sn om a t u r ea l g o r i t h m t h i sp a p e rs t u d i e sa c o m p r e s s e di n d e xf m i n d e xw i t hi t sf i l ef o r m a ta n da l g o r i t h m t os o l v et h ep r o b l e m t h a tf m i n d e xn e e d st o om u c hm e m o r yw h i l eb u i l d i n gc o m p r e s s e di n d e x ，w ep r o p o s e 种新的m p i a l l g a t h e r 算法及压缩查询并行算法研究 t h a tf m - i n d e xs h o u l dd i v i d et h eo r i g i n a lf i l ei n t os e v e r a lp a r t st ob u i l dt h ei n d e x ，a n d g i v em e t h o d so fi n q u i r i n gu n d e rt h en e wc i r c u m s t a n c e w ea l s od e s i g nap a r a l l e l a l g o r i t h mf o rf m i n d e x t h e s ed e s i g n sb r i n gf m i n d e xt h ea b i l i t yo fd e a l i n gw i t h l a r g ef i l ea n d f a r t h e ro ng o o dp r o s p e c to f r e a la p p l i c a t i o n k e yw o r d s ：m p ia l l g a t h e r , a l g o r i t h m ，c o l l e c t i v ec o m m u n i c a t i o n ，p e r f o r m a n c e e v a l u a t i o n ，l o c a l i t y , c o m p r e s s ，p a r a l l e ls o f t w a r e ，c o m p r e s s e di n d e x 一种新的m p ia l l g a t h e r 算泄汲压缩查询并行算法研究 绪论 图目录 图2 一l ：m p i 算法通信语义7_allgather 图2 2 ：环算法的消息传递方向8 图2 3 ：递归倍增算法9 图2 - 4 ：b r u c k 算法1 0 图2 - 5 ：进程数为偶数的m p i a l l g a t h e r 邻居交换算法1 1 图2 - 6 ：进程数为奇数的邻居交换算法一1 2 图2 7 ：深腾6 8 0 0q s n e t 上a l l g a t h e r 算法的短消息( 8 b ) 通信性能1 6 图2 8 ：深腾6 8 0 0q s n e t 上a l l g a t h e r 算法的中等长度消息( 8 k b ) 通信性 能一17 图2 9 ：深腾6 8 0 0q s n e t 上a l l g a t h e r 算法的长消息( 1 2 0 k b ) 通信性能 1 7 图2 1 0 ：深腾6 8 0 0q s n e t 上a l l g a t h e r 算法的超长消息( 4 m b ) 通信性能 l8 图2 1 1 ：深腾6 8 0 0 以太网上a l l g a t h e r 算法的短消息( 8 b ) 通信性能1 9 图2 1 2 ：曙光4 0 0 0 a 以太网上a l l g a t h e r 算法的短消息( 8 1 3 ) 通信性能2 0 图2 1 3 ：深腾6 8 0 0 以太网上a l l g a t h e r 算法的中等长度消息( 8 k b ) 通信 性能一2 0 图2 1 4 ：曙光4 0 0 0 a 以太网上a l l g a t h e r 算法的中等长度消息( 8 k b ) 通信 生能2l 图2 一1 5 ：深腾6 8 0 0 以太网上a l l g a t h e r 算法的长消息( 1 2 0 k b ) 通信性能 ：1 1 图2 1 6 ：曙光4 0 0 0 a 以太网上a l l g a t h e r 算法的长消息( 1 2 0 k b ) 通信性能 ：! ：! 图2 1 7 ：华云神箭h y s j 一1 0 0 0s c i 网上a l l g a t h e r 算法的超长消息( 4 m b ) 通信性能( 每节点使用1 个c p u ) 2 3 图2 1 8 ：华云神箭h y s j 一1 0 0 0s c i 网上a l l g a t h e r 算法的长消息( 4 m b ) 通 信性能( 每节点使用2 个c p u ) 2 3 图3 - 1 ：m p ia l l r e d u c e 算法通信语义3 0 图3 - 2 ：进程数为偶数的m p ia l l r e d u c e 邻居交换算法3 2 图5 1 ：并行g z i p 压缩解压缩体系结构图4 8 图5 2 ：并行压缩解压缩处理流程4 9 图5 3 ：流水线解压缩流程图5l 图5 - 4 ：l s s c i 机群解压缩测试结果5 4 种新的m p i a l l g a t h e r 算法及压缩查询并行算法研究 绪论 图5 - 5 ：c c s e i 机群解压缩测试结果 表3 - 1 ： 表5 - 1 ： 表5 - 2 ： 表5 3 ： 表格目录 四种m p i a l l g a t h e r 算法的平均逻辑通信距离 l s s c i 机群o m p g z i p 对g z i p 的压缩加速比 c c s e i 机群o m p g z i p 对g z i p 的压缩加速比 o m p g z i p 与g z i p 压缩比 2 8 5 2 5 3 5 3 一种新的m p ia l l g a t h e r 算浊及雎缩盘询并行算法研究绪论 1 1 引言 第1 章绪论 计算机是2 0 世纪人类最伟大发明之一。自从世界第一台数字计算机于1 9 4 6 年问世以来，在之后短短的六十年时间内，计算机以磅礴之势迅猛发展，单机速 度已接近物理极限，计算机工作者开始将并行原理引入计算机体系结构的设计当 中。1 9 7 2 年世界上第一台并行计算机系统研制成功；2 0 吐纪9 0 年代丌始，以通 用部件构建的机群系统获得广泛应用，成为“平民化”的超级计算机；近两年来， 随着双核处理器的推出，并行计算开始融入个人的工作、学习和生活之中。本文 正是基于轰轰烈烈的并行技术发展趋势开展了两方面的工作：一是针对万亿次机 群优化集合通信性能；二是对一些串行应用程序做了并行化设计或实现。 1 2 本文研究背景 下面分别介绍本文研究的两部分内容的研究背景。 1 2 1 集合通信性能优化研究背景 近代并行编程语言环境分为共享存储( 包括虚拟共享存储) 环境和分布存储 编程环境两种情况。共享存储并行编程环境包括p t h r e a d s 和o p e n m p 等，而分布 存储并行编程环境包括m p i 和p v m 。 m p i 和p v m 是基于多地址空间的消息传递编程模型。在消息传递模型中， 各个并行执行的任务之间通过传递消息来交换信息、防调步伐、控制执行，为程 序员提供了灵活的控制手段和表达形式。消息传递模型的基本通信模式简单和清 楚，冈此目前大量并行程序采用的都是消息传递并行编程模型。 m p i 是为丌发基于消息传递模型的并行程序而制定的工业标准，其目的是为 了提高并行程序的可移植性和易用性。参与m p i 标准制定的人员来自欧美4 0 多 个组织，大部分主要的并行计算机制造商、大学研究所、政府实验室、工业组织 等都投入到m p i 标准化工作。有了统一的并行编程语言标准，并行计算环境下 的应用软件及软件工具就都能够实现透明的移植，各个厂商就可以依据标准提供 独具特色和优势的软件实现和软件支持，从而提高了并行处理的能力。 m p i 是一种基于消息传递模型的并行编程接口，目前已经发展成为消息传递 模型的代表和事实上的】业标准，而不是门具体的语言。迄今为止，所有的并 种新的m p i a l l g a t h e r 算法及压缩查咖并行算沾研究 绪论 行计算机制造商都提供对m p i 的支持，因而从理论上说任何一个正确的m p i 程 序可以不加修改地在所有并行计算机上运行。 m p l 只是一个并行编程语言标准，要编写基于m p i 的并行程序，还必须借 助某一m p i 具体实现。m p i c h 是l i n u x 平台下最重要的种m p i 实现，是一个 与m p i 规范同步发展的版本。每当m p l 标准推出新的版本时，m p i c h 就会有相 应的实现版本。 m p i 库包括点到点通信和集合通信等消息传递函数，其中集合通信是基于点 到点通信函数实现的。尽管m p l c h 获得了广泛的应用，其集合通信的实现的低 效性常常遭到程序员的抱怨，而集合通信的性能对m p i 并行应用程序的性能有 着至关重要的影响，因此改善和优化集合通信性能的意义重大，也成为非常活跃 的一个研究课题。 本文提出一种新的m p ia l l g a t h e r 集合通信算法，改善了该集合通信的中等 长度以上的消息通信性能，同时提出的算法通信局部性概念为并行算法提供了新 的评价尺度。 1 2 2 压缩，压缩查询并行化算法研究背景 信息世界里压缩技术无处不在，比如我们的收音机、电视机、d v d 、v c d 等。如果你是一名计算机用户，对数据压缩技术的使用就更直接了，w i n d o w s 上 最常用于压缩文档的w i n z i p 和w i n r a r 软件，l i n u x 上的g z i p ，p c 上几乎所有的 多媒体文件，如w l r l v ，r a m ，m p 3 等结尾的文件，就是压缩后的多媒体文件， 这些文件要用专门的多媒体播放软件或专用的芯片先解压，然后才能播放。 对于某些压缩技术，如图像、视频和音频的压缩，我们只要享受它们带来的 乐趣就好了；而在日常生活中备份文件时，要求从压缩文件中准确重构出原文件， 就要使用到另一些无损压缩技术如g z i p 、b z i p 2 、w i n z i p 和w i n r a r 等。现今流行 的无损压缩软件在进行数据压缩时需要大量的计算，数据量越大，压缩耗时越长， 且压缩时间随着数据量增长而增长的速度远超过线性。做一个大量数据的备份， 压缩会占据大量的c p u 资源并耗费许多时间。 随着双核处理器的推出，并行计算开始开始融入个人的工作、学习和生活之 中。如果能将并行原理融入压缩软件当中，就能在不影响软件兼容性且基本不影 响压缩比的前提下让压缩应用“飞”起来。基于这一背景，本文设计了兼容g z i p f 鲢速度要快上数倍的并行压缩软件o m p g z i p 。 人们对便捷的追求总是不断提高。压缩速度上去了，又发现解压缩所要耗费 的时间也是不容小视，例如1 个释放后2 4 g b 总量的文本文件需要2 5 个小时左 右的时间来用g z i p 解压缩。如果发现解压缩后的文件出现乱码和或不符合要求， 一种新的m p i a i i g a t h e r 算泣及压缩查询并行算法研究 绪论 也会耗费大量的时间和精力。于是人们希望能在进行真正解压缩之前进行简单的 查询，确定压缩文件的正确性和里面的内容是否满足需要，从而避免一i ：述情况的 发生。压缩查询技术就是在这样的需求中应运而生。 压缩查询是一个较新的研究领域，日前还没有存在压缩领域如g z i p ，b z i p 2 这样成熟的软件，压缩查询索引f m i n d e x 是压缩查询领域中比较看好的技术。 但通过对目前公开的最新版本的源代码中的测试发现，f m i n d e x 的现有版本存 在不少缺点，如压缩和建立索引时间太长，压缩一百多兆的文件在普通的机器需 要几分钟的时间；压缩内存需要量大，达到源文本大小的4 5 倍，压缩几百兆 的文件常常由于系统内存不足而无法进行。这些缺陷使得人们对压缩查询技术是 “想说爱你不容易”。在此背景之下，本文设计了模块化的f m i n d e x ，希望能解 决f m i n d e x 内存需求量太大的问题，让f m i n d e x 能在实际中应用起来。 1 3 本文的主要工作 本文提出并实现了一种新的m p ia l l g a t h e r 算法一一邻居交换算法。为验证 所提出新算法的正确性及有效性，在深腾6 8 0 0 上使用q s n e t 和快速以太网，在 曙光4 0 0 0 a 上使用快速以太网，在华云神箭h y s j 一1 0 0 0 使用s c i 网将新算法与 原有广泛使用的m p ia l l g a t h e r 算法进行性能测试，文章给出了测试结果并对结 果进行了分析比较，讨论了不同的m p ia l l g a t h e r 算法各自的优劣及其所适用的 通信环境。 通过对m p ia l l g a t h e r 算法通信性能的分析，我们发现某一些通信模式( 特 别是近邻通信模式) 的通信带宽能够超过别的通信模式带宽，引发了算法通信局 部性方面的讨论。目前衡量通信局部性的参数为平均物理通信距离 1 ，很难从 一个算法的逻辑描述中计算物理通信距离，从而很难确定该算法的通信局部性。 为了便于对算法进行分析，本文提出两个新概念：逻辑通信距离和平均逻辑通信 距离，给出了逻辑通信距离和平均逻辑通信距离的定义及计算公式：通过计算 四个m p i 算法的平均逻辑通信距离分析了它们的通信局部性，从而更_allgather 准确地分析了算法的性能测试结果。以平均逻辑通信距离为基础定义的通信局部 性概念可以为并行算法增加新的评价尺度，更精细地评价算法性能。 通过分析发现邻居交换算法具有近邻通信的性质，非常适合中等长度以上的 消息通信，本文还将近邻通信的思想扩展到m p ia l l r e d u c e 函数，设计了 m p ia l l r e d u c e 邻居交换算法。 本文的另一部分工作就压缩和压缩查询技术的并行化算法设计和实现展开。 对压缩选择了g z i p 压缩软件，在详细分析了g z i p 文件格式和算法厉，本文 探索了两种g z i p 并行压缩算法，并实现了其中一种。所实现的并行g z i p 版本采 种新的m p ia l l g a t h c r 算法及压缩查渤并行算法研究 用基于共享存储编程模型的o p e n m p 标准，因此命名为o m p g z i p 。o m p g z i p 与 g z i p 兼容，使用晒p 压缩的文件，可以用o m p g z i p 进行解压缩；使用o m p g z i p 压缩的文件，可以用g z i p 解压缩。在“大规模科学计算研究”一号机群和北京 大学b e o w u l f 机群c c s e i 中对o m p g z i p 和g z i p 使用2 c p u 的s m p 节点进行测 试，本文给出了测试结果。在o r n p g z i p 软件实现中遇到了一些难题未能解决， 本文描述了这些难题并对如何解决和未来的工作进行了展望。 对压缩查询选择了f m i n d e x 软件。由于压缩查询是一个较新的研究领域， 需要特别设计的压缩算法、格式和数据结构来支持压缩状态下的查询。本文细致 地调研了f m i n d e x 的压缩和查询原理，给出了详细的描述。但原理和实现之间 还是存在差距的，况且实验测试还发现f m i n d e x 的实现存在不少缺陷。阅读了 f m ，i n d e x 源代码之后，在本文给出了f m i n d e x 的文件格式以及详细的压缩和查 询流程，并针对f m i n d e x 内存需求量太大的问题提出了分块压缩和建立索引的 思想，就f m - i n d e x 分块后可能出现的一些问题提出了解决办法，修改了f m i n d e x 的索引方式使之能够适应分块查询。最后，本文还设计了分块方式下f m i n d e x 的并行化算法。 1 4 本文的组织结构 本文因为涉及到本人在读硕士期间两方面的主要工作，因而大体e 分为两大 部分。第一部分为集合通信性能优化，包括第二章和第三章；第二部分为压缩查 询并行化算法设计与实现，包括第四章、第五章和第六章；最后在第七章对全文 的工作做了总结，并展望了未来的工作。 本文安排如下： 第一章为绪言，介绍本文的研究背景、研究内容和组织结构； 第二章为m p i算法研究，提出一种新的算法，实_ a u g a t h e r m p la l l g a t h e r 现了新算法并通过实验测试将之与原有的算法进行分析和比较； 第三章提出逻辑通信距离和平均逻辑通信距离的概念，通过计算 m p l 算法的平均逻辑通信距离分析了它们的通信局部性；将近邻通信_allgather 的思想扩展到m p ia l l r e d u c e 函数，设计了m p ia l l r e d u c e 邻居交换算法； 第四章介绍数据压缩和压缩查询相关知识，详细分析g z i p 压缩技术，探索 了g z i p 压缩的并行化算法，详细介绍了压缩查询软件f m i n d e x 的算法原理； 第五章详细介绍并行g z i p 软件o m p g z i p 的并行思想、实现框架、软件实现 和优化技术、软件测试效果、在实现中遇到的难题、可能的解决办法和对未来工 作的展望； 第六章整理出了f m i n d e x 文件格式以及压缩一查询的处理流程，针对 一种新的m p ia t l g a t h e r 算法及压缩查啕并行算法 i j 究 绪论 f m i n d e x 内存消耗太大的问题提出了分块解决方案，并就分块后会遇到的一些 问题提出了解决的办法，最后设计了分块方式下f m i n d e x 的并行化算法： 第七章为结束语，总结全文的工作并展望进一步的工作。 二型塑些竺! ! ；笪堕! 坐旦塞鲨丝堡筮鱼塑茎堑复鲨丛塑簦鎏盟丝堕旦型丝 第2 章 m p i _ a l l g a t h e r 算法研究 2 1 概述 消息传递是目前并行计算机上广泛使用的一种程序设计模式，m p i ( m e s s a g e p a s s i n g i n t e r f a c e ) 则是其中最受欢迎的设计平台。消息传递作为并行汁算的基础， 其通信性能对于并行应用程序性能有着重要的影响。m p i 库包括点到点通信和集 合通信等消息传递函数。如今，随着l i n u x 机群越来越流行，并行机规模越来越 大，已经可以容纳成千上万个处理器，相应地，并行应用程序规模也越来越大， 所能使用的处理器越来越多，集合通信往往成为性能瓶颈。因为当参与集合通信 的进程非常多时，进程间通信量很大，并需要互相协调以完成语义，相应涉及到 的处理器问的通信量也就非常大，关系错综复杂，大大影响了通信效率，从而影 响应用程序的性能。因此，改善和优化集合通信性能的意义重大，也成为非常活 跃的一个研究课题。 m p ia l l g a t h e r 是m p i 库中使用频率最高的集合通信函数之一，本章内容为 作者对m p ia l l g a t h e r 算法的详细调研，提出一种新的m p la l l g a t h e r 算法，实 现新算法并通过实验测试将之与原有的算法进行分析和比较。本章组织如下：第 二部分简单介绍m p i 库及聚合通信函数m p la l l g a t h e r 的语义；第三部分介绍目 前广泛使用的m p i 算法；第四部分详细描述作者提出的新的_allgather m p ia l l g a t h e r 算法一一邻居交换算法；第五部分介绍测试环境、测试方法并分 析实验结果；第六部分小结。 2 2m p i 及m p i _ a i l g a t h e r 函数 2 2 1m p i 消息传递是目前并行计算机上广泛使用的一种程序设计模式，广泛适用于分 布式存储的可扩展并行计算机和工作站机群，在过程之间的通信采用消息传递已 经是一种共识。m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是基于消息传递编写并行程序的用 户接口，在国际上被公认为消息传递用户界面标准，目前国际上推出的所有并行 计算机都支持m p if 2 1 。 m p i 库包括点到点通信和集合通信等消息传递函数。点到点通信是指两个进 程之间的通信，如m p is e n d ，点到点通信中一个进程发送数据，另一进程接收 二苎垫塑丛! 垒些型! ! ! 塑垄丝里堕查塑2 1 ：堑塑：鲨盟壅 塑：鲨塑堂笪旦型壁 数据，它是m p i 通信c l * q 的基础。集合通信( c o l l e c t i v ec o m m u n i c a t i o n ) 又叫聚 合通信，足指多个进程( 通常大于2 ) 之问的通信，如m p ib c a s t 。集合通信基 于点到点通信，它通过一系列的点到点通信及一些其它的中间语句来完成其通信 语义。 在m p i 集合通信中，所有参与通信的进程构成个通信域( c o m m u n i c a t o r ) ， 通信域中每个进程拥有唯一的一个i d 号。在有p 个进程的通信域中，进程的i d 被依次编号为0 ，1 ，p l 。 2 2 2m p i a g a t h e r 函数 m p i a l l g a t h e r 是m p i 库中使用频率最高的集合通信函数之一，其功能如下： 通信域内每个进程都有一份数据需要散播给其它进程，这些数据块大小相等，并 称来自进程i 的数据块为数据块i 。经过系列的通信步骤，最后每个参与通信 的进程都收集到所有进程的数据( 包括自己的数据) ，且这些数据按序号在接收 缓冲区中排列好。 d a t ad a t a p o p 1 p 2 p 3 p 4 l 2 345 1 234 5 1 2 3 4 5 l2 3 4 5 12 3 4 5 图2 - 1 ：m p ia l l g a t h e r 算法通信语义 图2 1 展示了5 个进程参与的m p ia l l g a t h e r 通信的语义。 用c 语言描述m p ia l l g a t h e r 函数如下： i n tm p i _ a l l g a t h e r ( v o i d 4s e n d b u f , i n ts e n d c o u n t ，m p i _ d a t a t y p e s e n d t y p e ， v o i d 8r e c v b u f , i n t r e c v e o u n t ，m p i _ d a t a t y p er e c v t y p e ， m p i c o m l lc o m m ) 其中参数如下： 1 n s e n d b u e i n s e n d c o u n t i n s e n d t y p e ， o u tr e c v b u f , i n r e c v c o u n t ， 发送缓冲区的首地址。 要发送的元素个数。 发送缓冲区的数据类型。 接收缓冲区的首地址。 接收每个进程中数据元素的个数。 二壁堑堕塑! ：型! g ! 尘坚塑鲨垦堡堕垒塑茎i i 簦鎏型! 塑 望婆堕塑! 亘旦翌丝 i n r e c v t y p e ， i n c o m l t l 接收缓冲区的数据类型。 通信域。 2 3 相关m p i _ a ll g a t h e r 算法 m p i 是基于点到点函数实现的高级通信函数，关于_allgather m p ia l l g a t h e r 算法方面的研究很多：b e n s o n 等在l i n u x 机群上测试了a l l g a t h e r 算法的性能 3 ， 并基于分发式障碍( b a r r i e r ) 算法【4 提出了一个分发式a l l g a t h e r 算法；b r u c k 等 提出了一个针对短消息通信的有效算法 5 ：c h a n 等对已有的集合算法做了一系 列的测试，指出对不同长度的消息应使用不同的算法【6 】；t h a k u r 等致力于优化 集合通信函数的性能【7 】。 最早的m p i 算法非常简单，其中一种方法是某一进程先收集_allgather ( g a t h e r ) 到所有的数据，然后将这些数据广播( b r o a d c a s t ) 给通信域中所有进 程。本节介绍三种m p ia l l g a t h e r 算法：环( r i n g ) 算法，递归倍增( r e c u r s i v e d o u b l i n g ) 算法和b r u c k 算法，它们各有特色，并在m p i c h - - 1 2 6 中应用于不 同长度的消息。 2 3 1 环( r i n g ) 算法 m p i c h 的早期版本使用环算法实现m p i _ a l l g a t h e r 。 文献【7 给出了环算法的具体描述，在环算法中，所有参与通信的进程按序 号形成一个环，消息在环上传递。第一步，进程i 将自己的数据块发送给进程 ( 【f + 1 ) p ) 并从进程( ( f l m p ) 接收数据。从第二步开始，进程i 将前一步从进程 ( ( f 1 ) p ) 接收到的数据转发给进程( ( f + 1 ) p ) 。该算法总共需要( p 1 ) 步数据传输。 0 p - 2 图2 2 ：环算法的消息传递方向 图2 2 展示了环算法的消息传递方式，箭头代表消息传递方向。 二型堑堕坚! 一垒! 也型! 里篁婆丝堕堑垒塑堑塑望堡丛塞 笪鲨塑望堕旦型堂 2 3 2 递归倍增( r e c u r s i v ed o u b l i n g ) 算法 m p i c h 1 2 5 使用了递归倍增算法实现m p ia l l g a t h e r 。 对于递归倍增算法，分进程数为2 的指数次幂及非2 的指数次幂两种情况考 虑。 首先考虑进程数为2 的指数次幂的情况。第一步，编号距离为l 的进程两两 通信并交换数据，如进程0 与进程1 通信，进程2 与进程3 通信。第二步，编号 距离为2 的进程两两通信并交换数据( 包括进程本身的数据以及在前面步骤巾接 收到的数据) ，如进程0 与进程2 通信，进程1 与进程3 通信。在p 为2 的指数 次幂的情况下，每一步中，每一个进程都恰好可以找到一个与之交换数据的进程。 我们称某一步中交换数据的两个进程为该步的同伴进程( p a r t n e r ) 。一般的，在 第i 步( 0 f l o g p ) ，编号距离为2 “的两个进程交换数据，算法共需要l o g p 步 数据传输。 s t c p l s t e p 2 s t y 2 + n c p 3 + 0 1 2 3 4 5 60 l 为4 5 60 1 2 3 4 5 60 1 2 3 4 5 60 1 2 3 4 5 60 1 2 3 4 5 60 1 2 3 4 5 6 图2 3 ：递归倍增算法 对于进程数为非2 的指数次幂的情况，在各步骤中总有一些进程没有同伴进 程，两两交换数据无法顺利进行，必须采取额外的传输步骤保证所有进程都接收 到相应的数据。以图2 - 3 为例，第一步，仍是编号距离为l 的进程两两交换数据， 进程6 本该与期望中的同伴进程7 交换数据，但由于进程7 不存在，进程6 只好 二盟堑堕竺塑：垒些! ! ! 竺簦垄丝垦塑壅型苎堑笪壁盟壅 篁婆塑望笪旦叠壁 不做任何动作。这一步没有进程错失数据。第二步，编号距离为2 的进程两两交 换数据，进程5 期望从进程7 中接收到数据块6 ，但是由于进程7 的缺失，进程 5 也缺失了数据块6 。于是在第2 + 步，进程4 将数据块6 传输给进程5 ，这就是 前面提到的“额外的传输步骤”。第3 + 步做的也是类似的工作。在这种情况下， 总传输步骤上界为2 l l o g p j 。 2 3 3b r u c k 算法 b r u c k 算法 5 1 的提出基于分发式障碍算法【4 】。b r u c k 算法中，第 k ( o t l l o g p j ) 步，进程f 发送2 七个数据块到进程( ( f 一2 七) p ) 并从进程 ( ( f + 2 膏) p ) 接收数据。如果p 不为2 的指数次幂，则增加一步( 也就是第l l o g p j 步， = l l o g p j ) ，进程f 发送( p 一2 8 ) 块数据到进程( ( 卜2 5 ) p ) 并 从进程(