计算机研究与发展 Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ ＩＳＳＮ １０００—１２３９／ＣＮ １ １—１７７７门ｒＰ ５０（８）：１７４４—１７５４，２Ｏ１３ ＭＰＩ Ａｌｌｔｏａｌｌ通信在多核机群中的优化 李 强 孙凝晖 霍志月１ 马 捷 北京 （中国科学院计算技术研究所高性能计算机研究中心（中国科学院计算机系统结构重点实验室 北京 １００１９０） 。（中国科学院大学北京１０００３９） （１ｉｑｉａｎｇ＠ｎｃｉｃ．ａｅ．ｅｎ） Ｏｐｔｉｍｉｚｉｎｇ ＭＰＩ Ａｌｌｔｏａｌｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｉｎ Ｍｕｌｔｉｃｏｒｅ Ｃｌｕｓｔｅｒｓ Ｉ．ｉ Ｑｉａｎｇ ＇ 。Ｓｕｎ Ｎｉｎｇｈｕｉ ，Ｈｕｏ Ｚｈｉｇａｎｇ ，ａｎｄ Ｍａ Ｊｉｅ （Ｈｉｇｈ Ｐｅｒｆｏｒｍａｎｃｅ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ，Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｃｏｍｐｕｔｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ， Ｂｅｉｊｉｎｇ １００１９０） 。（Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏＪ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍ ａｎｄ Ａｒｃｈｉｔｅｃｔｕｒｅ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ １００１９０） 。（Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏＪ’Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ １０００３９） Ａｂｓｔｒａｃｔ ＭＰＩ Ａｌｈｏａｌｌ ｉｓ ａｎ ｉｍｐｏｒｔａｎｔ ｃｏｌｌｅｃｔｉｖｅ ｏｐｅｒａｔｉｏｎ．Ｉｎ ｍｕｈｉｃｏｒｅ ｃｌｕｓｔｅｒｓ，ｍａｎｙ ｐｒｏｃｅｓｓｅｓ ｒｕｎ ｉｎ ａ ｎｏｄｅ．Ｏｎ ｔｈｅ ｏｎｅ ｈａｎｄ，ｓｈａｒｅｄ ｍｅｍｏｒｙ ｃａｎ ｂｅ ａｄｏｐｔｅｄ ｔｏ ｏｐｔｉｍｉｚｅ Ａｌｌｔｏａｌｌ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｓｍａｌｌ ｍｅｓｓａｇｅｓ ｂｙ ｌｅａｄｅｒ—ｂａｓｅｄ ｓｃｈｅｍｅｓ．Ｈｏｗｅｖｅｒ，ａｓ ｔｈｅｓｅ ｓｃｈｅｍｅｓ ａｄｏｐｔ ａ ｆｉｘｅｄ ｎｕｍｂｅｒ ｏｆ ｌｅａｄｅｒ ｐｒｏｃｅｓｓｅｓ。ｔｈｅ ｏｐｔｉｍａｌ ｐｅｒｆｏｒｍａｎｃｅ ｃａｎ’ｔ ｂｅ ｏｂｔａｉｎｅｄ ｆｏｒ ａｌｌ ｓｍａｌｌ ｍｅｓｓａｇｅｓ．Ｏｎ ｔｈｅ ｏｔｈｅｒ ｈａｎｄ， ＤｒＯＣｅｓｓｅｓ ｗｉｔｈｉｎ ａ ｎｏｄｅ ｃｏｎｔｅｎｄ ｆｏｒ ｔｈｅ ｓａｍｅ ｎｅｔｗｏｒｋ ｒｅｓｏｕｒｃｅ．Ｉｎ Ａｌｌｔｏａｌｌ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ １ａｒｇｅ ｍｅｓｓａｇｅｓ，ｍａｎｙ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｍｅｓｓａｇｅｓ ａｒｅ ｕｓｅｄ． Ｎｅｖｅｒｔｈｅｌｅｓｓ，ｔｈｅ ｃｏｎｔｅｎｔｉｏｎ ｍａｋｅｓ ｔｈｅｉｒ ｌａｔｅｎｃｙ ｉｎｃｒｅａｓｅ ｍａｎｙ ｔｉｍｅｓ ａｎｄ ｔｈｅ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｏｖｅｒｈｅａｄ ｃａｎ’ｔ ｂｅ ｉｎｇｏｒｅｄ．Ｔｏ ｓｏｌｖｅ ｔｈｅｓｅ ｐｒｏｂｌｅｍｓ，ｔＷＯ ｏｐｔｉｍｉｚａｔｉｏｎｓ ａｒｅ ｐｒｅｓｅｎｔｅｄ．Ｆｏｒ ｓｍａｌｌ ｍｅｓｓａｇｅｓ，ｔｈｅ ＰＬＰ ｍｅｔｈｏｄ ａｄｏｐｔｓ ｃｈａｎｇｅａｂｌｅ ｎｕｍｂｅｒｓ ｏｆ ｌｅａｄｅｒ ｐｒｏｃｅｓｓｅｓ． Ｆｏｒ ｌａｒｇｅ ｍｅｓｓａｇｅｓ，ｔｈｅ ＬＳＳ ｍｅｔｈｏｄ ｒｅｄｕｃｅｓ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｍｅｓｓａｇｅｓ ｆｒｏｍ ３Ｎ ｔｏ ２ ．Ｔｈｅ ｅｖａｌｕａｔｉｏｎｓ ｐｒｏｖｅ ｔｗｏ ｍｅｔｈｏｄｓ．Ｆｏｒ ｓｍａｌｌ ｍｅｓｓａｇｅｓ，ｔｈｅ ＰＩ Ｐ ｍｅｔｈｏｄ ａｌｗａｙｓ ｏｂｔａｉｎｓ ｏｐｔｉｍａｌ ｐｅｒｆｏｒｍａｎｃｅ．Ｆｏｒ ｌａｒｇｅ ｍｅｓｓａｇｅｓ，ｔｈｅ ＬＳＳ ｍｅｔｈｏｄ ｂｒｉｎｇｓ ａｌｍｏｓｔ ｃｏｎｓｔａｎｔ ｉｍｐｒｏｖｅｍｅｎｔ ｐｅｒｃｅｎｔａｇｅ．Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｉｓ ｉｍｐｒｏｖｅｄ ｂｙ ２５ ｍｅｓｓａｇｅｓ． ｆｏｒ ３２ ＫＢ ａｎｄ ６４ ＫＢ Ｋｅｖ ｗｏｒｄｓ Ａｌｌｔｏａｌｌ； ｓｈａｒｅｄ ｍｅｍｏｒｙ； ｃｏｎｔｅｎｔｉｏｎ；ｌｅａｄｅｒ—ｂａｓｅｄ ｐｒｏｃｅｓｓ ｎｕｍｂｅｒ； ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｏｖｅｒｈｅａｄ 摘要ＭＰＩ Ａｌｈｏａｌｌ是一种重要的集合通信．在多核机群中，一个节点内的多个进程同时参与Ａｌｈｏａｌｌ 通信．一方面，这些进程可以利用共享内存优化通信性能．虽然当前基于首进程的方法利用共享内存提 高了Ａｌｌｔｏａｌｌ小消息通信的性能，但由于采用固定数目的首进程，这些方法不能使所有不同长度的小消 息都获得最优性能．另一方面，这些进程需要竞争节点内有限的网络资源．在Ａｌｌｔｏａｌｌ大消息的通信中 存在许多个同步消息．然而竞争导致同步消息的延迟增大了数十倍，同步开销不可忽略．针对这些问题， 提出了两种不同的优化方法．对于Ａｌｌｔｏａｌｌ小消息通信，ＰＬＰ方法根据小消息的长度采用不同数目的首 进程；对于Ａｌｌｔｏａｌ１大消息通信，ＬＳＳ方法将同步消息的总数从３Ｎ减少到２￣／Ｎ．相关实验结果验证了 收稿日期：２０１１－１２ ３０；修回日期：２０１２ ０５ ０７ 、 基金项目：国家“九七三”重点基础研究发展计划基金项目（２０１２ＣＢ３１６５０２）；国家“ｌｋ？－＜”高技术研究发展计划基金项目（２００９ＡＡ０１Ａ１２９）； 国家杰出青年科学基金项目（６０９２５００９）；国家自然科学基金青年科学基金项目（６１１０００１４）；国家“八六 ”高技术研究发展计划子 课题（２０１０ＡＡ０１２４０４ ６） 李 强等：ＭＰＩ Ａｌｌｔｏａｌｌ通信在多核机群中的优化 这两种方法．对于小消息，ＰＬＰ方法总是可以获得最优的性能．对于大消息，ＬＳＳ方法获得的性能提升 比例几乎为常数，并且与系统的规模无关；其中３２ ＫＢ和６４ ＫＢ消息的性能提高了２５ ． 关键词Ａｌｈｏａｌｌ；共享；竞争；首进程数目；同步开销 中图法分类号ＴＰ３９３ ＭＰＩ Ａｌｌｔｏａｌｌ通信作为一种重要的集合通信， 在ＨＰＣ（ｈｉｇｈ ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐｕｔｉｎｇ）应用如ＦＦＴ ，ＣＰＭＤ［。 和ＮＡＭＤ［３］中广泛使用．在Ａｌｈｏａｌｌ 通信中，每个进程发送不同的消息到其他所有的进 程．随着系统规模的扩大，它需要花费更多的时问， 因此优化其性能变得十分重要． 随着多核技术的发展，高性能计算机广泛采用 多核处理器．在２０１１年６月的Ｔｏｐ ５００中，８２ 的 ＨＰＣ平台是多核机群．在多核机群中，同一节点内 的多个进程同时参与Ａｌｌｔｏａｌｌ通信，这既带来了有 利的方面也带来了不利的方面． 一方面，这些进程可以利用共享内存优化通信 性能．由于大消息的内存拷贝代价很大，利用共享内 存的优化主要针对Ａｌｌｔｏａｌｌ小消息通信，它们采用 基于首进程的方法．在基于首进程的方法中，一个节 点内可以存在一个或者多个首进程．针对所有不同 长度的小消息，当前的基于首进程的方法采用固 定的首进程数目．例如，文献［４７中的Ｏｎｅ—ｌｅａｄｅｒ方 法在每个节点内采用一个首进程，文献［５］中的 Ｍ—ｌｅａｄｅｒ方法在每个节点内采用Ｍ个首进程（Ｍ 等于节点内的进程总数）．然而，首进程数目在很大 程度上影响着基于首进程的方法的性能，固定的首 进程数目并不能使所有不同长度的小消息都获得最 优性能．如在４．１节所提到的，对于５１２ Ｂ的消息， Ｏｎｅ—ｌｅａｄｅｒ方法的性能是Ｍ—ｌｅａｄｅｒ方法的２倍；而 对于３２ Ｂ的消息，Ｍ—ｌｅａｄｅｒ方法的性能是Ｏｎｅ— ｌｅａｄｅｒ方法的１．８倍． 另一方面，这些进程必须竞争节点内有限的网 络资源．在Ａｌｌｔｏａｌｌ通信中，节点内多个进程同时向 网卡提交通信请求，因此网卡需要调度处理多个通 信请求．由于网卡的处理能力有限，每个请求平均需 要等待较长的时间才能获得网卡的服务．同时，在网 卡的调度过程中，由于通信上下文的切换，网卡可能 产生ｃａｃｈｅ失效¨６］．然而，在当前的ＭＰＩ Ａｌｌｔｏａｌｌ大 消息通信中存在许多个同步消息．由于竞争，这些同 步消息的延迟增大了数十倍，如第３节所提到的，在 竞争条件下，６４ Ｂ消息的延迟从１．２６Ｆｓ增加到 ２９ＦＳ．因此，同步开销在很大程度上增加了整个 Ａｌｈｏａｌｌ大消息通信的时间． 本文详细分析了首进程数目和同步开销对 Ａｌｈｏａｌｌ通信性能的影响．相关的分析证明，首进程 的数目在很大程度上决定着Ａｌｈｏａｌｌ小消息通信的 性能，针对不同长度的小消息应该采用不同的首进 程数目．同时，本文推翻了以往对同步开销在大消息 通信中占很小比例的认识，在竞争条件下同步开销 是不可忽略的． 在相关分析的基础上，本文提出了两种不同的 优化方法，对于Ａｌｌｔｏａｌｌ小消息通信，恰当首进程 （ｐｒｏｐｅｒ ｌｅａｄｅｒ ｐｒｏｃｅｓｓｅｓ，ＰＬＰ）方法根据小消息的 长度采用不同的首进程数目．对于Ａｌｌｔｏａｌｌ大消息 通信，减少同步步数（１ｅｓｓ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｓｔｅｐｓ， ＬＳＳ）方法将同步消息的数目从３Ｎ减少到２￣／Ｎ． 在Ｍｖａｐｉｃｈ通信库中，我们实现了这两种优化方 法，并在２４０核的Ｉｎｆｉｎｉｂａｎｄ机群上对它们进行了 评测，相关实验结果证明： １）对于Ａｌｌｔｏａｌｌ小消息通信，ＰＬＰ方法总是可 以获得最优的性能； ２）对于Ａｌｌｔｏａｌｌ大消息通信，ＬＳＳ方法获得的 性能提升比例几乎为常数，其与系统的规模无关，对 于３２ ＫＢ和６４ ＫＢ的消息，它们的性能提高了 ２５ ； ３）对于ＦＦＴ应用，两种方法都获得了很大的 性能提升．当问题规模为４８０×４８０×４８０时，２４０进 程的ＦＦＴ的性能提高了２Ｏ ． １ 背 景 １．１ Ａｌｌｔｏａｌｌ算法 Ａｌｌｔｏａｌｌ通信根据消息的长度采用不同的算法． Ａｌｈｏａｌｌ小消息通信采用Ｂｒｕｃｋ方法［７］，它有利于减 少通信的初始化开销，而Ａｌｈｏａｌｌ大消息通信采用 Ｖｉｒｔｕａｌ Ｒｉｎｇ算法，它有利于减小通信的传输开销． 许多研究 。。 证明，对于相同长度的消息，两种方法 的性能相差很大． １．１．１ Ｂｒｕｃｋ算法 假定Ｎ个进程参与Ａｌｈｏａｌｌ通信，这种算法需要 执行ｌｏｇ Ｎ步．在第ｋ步中，Ｎ／２个长度为ｍ的小消 息首先聚合成长度为Ｎ×ｍ／２的大消息，然后进程ｉ 将聚合消息发往进程（ｉ＋２ ） Ｎ，同时，它接收来 自进程（ｉ一２ ＋Ｎ） Ｎ的聚合消息．该算法所花费 的总时间Ｔｍｕｃｋ如式（１）所示： ＴＢ ｋ—ｌｏｇ Ｎ×ｆ Ｔｓ＋ ×ＴＢ １，（１） 其中，Ｔ 为通信初始化的时间，Ｔ 为传输一个字节 所花费的时间． １．１．２ Ｖｉｒｔｕａｌ Ｒｉｎｇ算法 该算法需要执行Ｎ步．在第ｋ步，进程ｉ发送 一个消息到进程（ｉ＋ｋ）０ ｏ Ｎ，同时，它接收来自进程 （ｉ—ｋ＋Ｎ） Ｎ的消息．图１显示出算法在第２步 的执行过程，其中６个进程参与Ａｌｌｔｏａｌｌ通信．整个 算法所花费的时间Ｔ ． 如式（２）所示： Ｔｍ 一Ｎ×（Ｔｓ＋仇×ＴＢ）． （２） Ｆｉｇ．１ Ｖｉｒｔｕａｌ ｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｏｆ ６ ｐｒｏｃｅｓｓｅｓ 图１ ６进程的Ｖｉｒｔｕａｌ Ｒｉｎｇ算法 １．２ ＭＰＩ点到点通信协议 在ＭＰＩ点到点通信中存在两种不同的通信协 议．Ｅａｇｅｒ协议主要针对小消息，它在通信过程中不 需要同步消息；而Ｒｅｎｄｅｚｖｏｕｓ协议主要针对大消 息，它在通信过程中需要使用同步消息． 图２显示了Ｒｅｎｄｅｚｖｏｕｓ协议基于ＲＤＭＡ操作 的执行流程，其中ＲＤＭＡ操作被大多数高性能网 络所支持，如Ｉｎｆｉｎｉｂａｎｄ网络．如图２所示，在一个 大消息的通信中，协议需要使用３个同步小消息，包 括请求发送消息ＲＴＳ（ｒｅｑｕｅｓｔ—ｔｏ—ｓｅｎｄ）、允许发送 消息ＣＴＳ（ｃｌｅａｒ—ｔｏ－ｓｅｎｄ）和发送完成通知消息ＦＩＮ （ｆｉｎｉｓｈｅｄ）．通过两个握手消息，发送方可以在发送 前确认接收方缓冲区是否可用．由于ＲＤＭＡ操作 需要使用接收缓冲区的物理地址信息，相应的地址 信息也包含在握手消息中．最后，在ＲＤＭＡ操作完 成后，发送方需要发送ＦＩＮ消息来通知接收方通信 的完成． 计算机研究与发展２０１３，５０（８） Ｆｉｇ．２ ＭＰＩ ｒｅｎｄｅｚｖｏｕｓ ｐｒｏｔｏｃｏｌ 图２ ＭＰＩ Ｒｅｎｄｅｚｖｏｕｓ协议 ２ 首进程数目和同步开销对Ａｌｌｔｏａｌｌ通信的 影响 ２．１首进程数目对Ａｌｉｔｏａｌｌ小消息通信的影响 为了更好地分析首进程数目对Ａｌｌｔｏａｌｌ小消息 通信的影响，下面首先介绍当前两种主要的首进程 方法：Ｏｎｅ—ｌｅａｄｅｒ方法和Ｍ—ｌｅａｄｅｒ方法．我们假定 Ｎ个进程参与Ａｌｌｔｏａｌｌ通信，每个节点上运行Ｍ个 进程，消息的长度为 ． 如图３所示，在Ｏｎｅ—ｌｅａｄｅｒ方法中，每个节点内 存在一个首进程．任意节点ｉ（０≤ｉ％Ｎ／Ｍ）内的首进 程是进程Ｐ 方法的执行流程如下．首先，节点内 Ｍ个进程的所有小消息在首进程上聚合为较大的 消息，其中，所有发往相同节点的小消息被聚合成为 一个较大的消息．因此，在首进程上，聚合消息的总 数为Ｎ／Ｍ，大小为Ｍ×Ｍ×ｍ．然后，每个节点内的 首进程使用聚合消息参与节点间的Ａｌｈｏａｌｌ通信． 所有的首进程属于同一个通信域，通信域的大小为 Ｎ／Ｍ．最后，在节点间的Ａｌｌｔｏａｌｌ通信完成后，首进 程将接收到的聚合消息通过共享内存分散给Ｍ个 进程． Ｎｏｄｅ（Ｎ／Ｍ—１） Ｆｉｇ．３ Ｏｎｅ—ｌｅａｄｅｒ ｍｅｔｈｏｄ 图３ Ｏｎｅ—ｌｅａｄｅｒ方法 李强等：ＭＰＩ Ａｌｌｔｏａｌｌ通信在多核机群中的优化 如图４所示，在Ｍ—ｌｅａｄｅｒ方法中，每个节点内 存在Ｍ个首进程．首先，节点内Ｍ个进程的所有小 Ｍ×Ｍ＜ ≤Ｓｉｚｅｃ ｌ／Ｍ时，在０ｎｅ—ｌｅａｄｅｒ方法中， 节点间Ａｌｌｔｏａｌｌ通信的消息长度大于Ｓｉｚｅ 。，它 采用Ｖｉｒｔｕａｌ Ｒｉｎｇ算法，而在Ｍ—ｌｅａｄｅｒ方法中，节 点问Ａｌｌｔｏａｌｌ通信的消息长度小于Ｓｉｚｅ 。，它采 消息在每个首进程上被聚合为较大的消息，其中，所 有发往相同进程的消息被聚合成为一个较大的消 息，每个首进程上聚合消息的总数为Ｎ／Ｍ，大小为 ＭＸｍ．然后，节点间的Ｍ个通信域同时进行Ａｌｌｔｏａｌｌ 用Ｂｒｕｃｋ算法．结合式（１）（２），两种方法的开销如 表１所示．由于ＭＸＭ×ｍ＞Ｓｉｚｅ ｍ 。，这说明通信 传输开销相对于通信初始化开销更加重要，因此 ０ｎｅ—ｌｅａｄｅｒ方法会获得更好的性能． 通信，通信域的大小为Ｎ／Ｍ．最后，在节点间的 Ａｌｌｔｏａｌｌ通信完成后，首进程将接收到的聚合消息通 过共享内存分散给Ｍ个进程． １ｌ ｌ ｌ尸００ ｌｌ 尸１０ Ｉ … Ｊ！（ ＝ ２ ｌ ｌ ｌ ｌ １ Ｉｌ Ｐ１１ ｌ … ｌ Ｐ（Ｎ／Ｍ一１）１ ｐ ｌ ＩＩ；ｌ ｄ ＰＯ（Ｍ一１）ｆ ｌＰ１（Ｍ一１）Ｉ… ｌＰｆＮ／Ｍ一１）（ 一１） Ｉ ｆ ｌ ｌ Ｎｏｄｅ ０ Ｎｏｄｅ １ Ｎｏｄｅ（Ｎ／Ｍ一１） Ｆｉｇ．４ Ｍ—ｌｅａｄｅｒ ｍｅｔｈｏｄ． 图４ Ｍ—ｌｅａｄｅｒ方法 通过对两种方法的介绍可以发现，基于首进程 的方法其开销包括节点内通信和节点间通信两部 分．由于节点内的通信通过共享内存完成，并且内存 的性能远高于网络的性能，因此方法的主要开销取 决于节点间的Ａｌｌｔｏａｌｌ通信．如果用三元组｛通信域 数目，通信域的大小，通信域内消息的长度｝来表示 节点间的Ａｌｌｔｏａｌｌ通信，则Ｏｎｅ—ｌｅａｄｅｒ方法对应的 三元组为｛１，Ｎ／Ｍ，Ｍ×Ｍ×ｍ），而Ｍ—ｌｅａｄｅｒ方法对 应的三元组为｛Ｍ，Ｎ／Ｍ，ＭＸｍ）． 对于节点间的Ａｌｌｔｏａｌｌ通信，存在Ｂｒｕｃｋ和 Ｖｉｒｔｕａｌ Ｒｉｎｇ两种算法．两种算法的性能相差很大， 在实际的ＭＰＩ Ａｌｌｔｏａｌｌ实现中，一个经验性的临界 值通常被用来决定Ａｌｌｔｏａｌｌ通信采用何种算法，假 定这个值为Ｓｉｚｅ 结合Ａｌｌｔｏａｌｌ算法，两种方法 针对不同长度的小消息各有优势． １）当消息的长度ｍ满足Ｍ×Ｍ×ｍ≤Ｓｉｚｅ ｌ 时，即ｍ≤Ｓｉｚｅｃ ｌ／Ｍ×Ｍ时，在Ｏｎｅ—ｌｅａｄｅｒ和 Ｍ—ｌｅａｄｅｒ方法中，节点间Ａｌｈｏａｌｌ通信的消息长度 都小于Ｓｉｚｅ …。，因此节点间的Ａｌｌｔｏａｌｌ通信都采 用Ｂｒｕｃｋ算法．如文献［５］所提到的，由于Ｍ—ｌｅａｄｅｒ 方法能够使一个节点内的多个进程同时进行通信， 它可以更充分地利用网卡，因此它可以获得比Ｏｎｅ— ｌｅａｄｅｒ方法更好的性能． ２）当消息的长度ｍ满足Ｍ×ｍ≤Ｓｉｚｅ 。，并 且Ｍ×Ｍ×ｍ＞Ｓｉｚｅｃ ｌ时，即ｍ满足Ｓｉｚｅｃ ｌ／ Ｔａｂｌｅ １ Ｌａｔｅｎｃｙ ｏｆ Ａｌｌｔｏａｌｌ Ｉｎｔｅｒｎｏｄｅ Ｃｏｍｍｕｎｉｃａｔｉｏｎ 表１节点间Ａｌｌｔｏａｌｌ的通信开销 Ｏｎｅ １ｅａｄｅ 丽Ｎ×Ｔ Ｎ×（Ｍ×Ｍ×丽ｍ×ＴＢ） Ｍ ａ Ｍ×（１。 丽Ｎ×Ｔｓ）Ｍ×（１ｏｇ Ｎ×（Ｎ×等）×丁ｅ） ３）当消息的长度ｍ满足ＭＸｍ￣Ｓｉｚｅ。 。 时，即 ｍ＞Ｓｉｚｅ。 。／Ｍ时，在两种方法中，节点间的Ａｌｌｔｏａｌｌ 通信都采用Ｖｉｒｔｕａｌ Ｒｉｎｇ算法．由于Ｍ—ｌｅａｄｅｒ方法 可以更充分的利用网卡，因此它可以获得更好的 性能． 通过两种方法的比较可以发现，首进程的数目 与节点间的Ａｌｌｔｏａｌｌ通信密切相关，因此它在很大 程度上决定着基于首进程的方法的性能．同时可以 发现，当前采用固定首进程数目的方法不能使所有 的小消息都获得最优的性能．为了获得最优的性能， 需要根据消息的长度选择不同的首进程数目． ２．２ 同步开销对Ａｌｌｔｏａｌｌ大消息通信的影响 在Ａｌｌｔｏａｌｌ通信中，同一个节点内的多个进程 同时向节点内的网卡提交通信请求．由于网卡的处 理能力有限，每个通信请求平均需要等待较长的时 间才能获得网卡的服务，同时由于通信上下文切换， 网卡上可能发生ｃａｃｈｅ失效．在本文中，我们用Ｔ 表示这部分等待时间以及处理ｃａｃｈｅ失效的时间． 由于小消息的长度很小，小消息的传输可以很 快地完成，式（３）给出了竞争条件下小消息的延迟 Ｔ。Ｍ ．由于网络ＭＴＵ的，大消息的传输过程 需要进行分片，并且每个消息分片与其他（Ｍ一１）个 进程的消息分片交替进行传输．因此，Ｍ个进程在 大消息通信过程享网络带宽，每个进程平均获 得１／Ｍ的网络带宽，大消息的传输时间增大了Ｍ 倍，式（４）给出了竞争条件下的大消息的延迟丁Ｉ ．。： Ｔｓ ＭＳ（；－一Ｔｃ＋Ｔｓ＋ｍｓ×ＴＢ； （３） ＴＬ ＭＳＧ—Ｔｃ＋Ｔｓ＋（ Ｉ ×ＴＢ）×Ｍ； （４） 其中，ｍ 为小消息的长度，ｍ 为大消息的长度． 同时，ＭＰＩ Ｒｅｎｄｅｚｖｏｕｓ协议在大消息的通信过 程中会使用３个同步小消息，式（５）给出了竞争条件 下，同步开销在整个大消息通信时间中的比例．在特 定的网络中，Ｔ 和Ｔ 都是确定的．例如Ｉｎｆｉｎｉｂａｎｄ 网络中，Ｔ。接近１ ｓ，而丁 是带宽４ ＧＢｐｓ的倒数， 因此式（５）中，同步开销的比例Ｐ。 在很大程度 上取决于Ｔ 的大小： Ｐ…ｒｈ 一｛３（Ｔｃ ４－Ｔｓ －４ｍｓ×ＴＢ）｝／ ｛３（Ｔｃ －４Ｔｓ －４ｍｓ×ＴＢ）＋ （Ｔｃ ４－Ｔｓ ４－（ Ｉ ×ＴＢ）×Ｍ）｝． （５） 为了获得Ａｌｈｏａｌｌ大消息通信中Ｔ 、的值，我们 创建了一个简单的评测模型．如图５所示，模型包含 ３个节点，每一个节点上存在一块网卡，它们通过网 络连接起来．每个节点的Ｍ个进程同时进行消息长 度为 的单向带宽测试．如图５所示，带宽测试在 每个节点与其邻居节点之间执行．通过这种方式，模 型可以很好地模拟Ａｌｈｏａｌｌ通信在Ｖｉｒｔｕａｌ Ｒｉｎｇ算 法下的竞争．为了获得Ｔ ，的值，在节点０和节点１ 之间，模型执行相应的小消息延迟测试． Ｆｉｇ．５ Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｍｏｄｅ１． 图５评测模型 我们在多核Ｉｎｆｉｎｉｂａｎｄ机群执行了评测模型， 其中Ｍ一８， ｔ 一６４ ＫＢ，机群的具体配置参见第４ 节．图６给出了竞争条件下的小消息的延迟．与没有 竞争条件下的延迟相比，不大于６４Ｂ的小消息的延 迟从１．５ ｓ增大到２９ ｓ，增大了２３倍．从式（３）可 以得出，Ｔ 一２７ ｓ．因此，在竞争的条件下，丁 、在小 消息的延迟中占主导地位．尽管没有在图６显示，６４ ＫＢ的大消息的延迟从２２．８ ｓ增大到１９５．８肚Ｓ，增 大了９倍，这与式（４）一致．结合式（５），３个同步小 消息的开销占６４ ＫＢ消息通信时间的３０ ．这推翻 了传统的认识，它们认为同步开销在Ｒｅｎｄｅｚｖｏｕｓ协 计算机研究与发展２０１３，５０（８） 议占很小比例． ４０ —＿．卜Ｌａｔｅｎｃｙ ｗｉｔｈ Ｃｏｎｔｅｎｔｉｏｎ ＋Ｌａｔｅｎｃｙ Ｗｉｔｈｏｕｔ Ｃｏｎｔｅｎｔｉｏｎ ３０ ．▲ １Ｏ ０ 一 一，一。一 一．一 － —卜＿． ２ ４ ８ １６ ３２ ６４ １２８ ２５６ ５１２ Ｍｅｓｓａｇｅ Ｓｉｚｅ／Ｂ Ｆｉｇ．６ Ｇｒｅａｔｌｙ ｉｎｃｒｅａｓｅｄ ｌａｔｅｎｃｙ ｏｆ ｓｍａｌｌ ｍｅｓｓａｇｅｓ ｗｉｔｈ ｃｏｎｔｅｎｔｉｏｎ． 图６小消息的延迟 当前的ＭＰＩ Ａｌｌｔｏａｌｌ通信基于ＭＰＩ点到点通 信实现．针对大消息，它采用Ｒｅｎｄｅｚｖｏｕｓ协议．同 时，在Ａｌｌｔｏａｌｌ大消息通信的Ｖｉｒｔｕａｌ Ｒｉｎｇ算法中， 共有Ｎ个点到点大消息通信需要执行，因此当前的 Ａｌｌｔｏａｌｌ实现使用３Ｎ个同步消息．通过上面的分析 可知，由于竞争，这些同步消息的延迟增加了数十 倍，同步开销在很大程度上增加了整个Ａｌｈｏａｌｌ大 消息通信的时间． ３优化方法的设计和实现 ３．１ ＰＬＰ方法 针对Ａｌｌｔｏａｌｌ小消息通信，ＰＩ Ｐ方法根据小消 息的长度选择合适的首进程数目．假定Ｍ个进程参 加Ａｌｌｔｏａｌｌ通信，ＰＬＰ方法可以选择的首进程数目 为Ｍ的所有约数．图７给出了ＰＬＰ方法采用首进 程数目为任意约数ｄ的情况，其中Ｍ—ｄ×ｅ． 如图７所示，每个节点内的所有进程分为ｄ组， 每一组包含ｅ个进程，并且每组包含一个首进程．在 方法的执行过程中，首先，节点内的Ｍ个进程的小 消息在ｄ个首进程上聚集成为较大的消息，其中所 有发往相同组的小消息在相应的首进程上聚合成一 个大的消息．例如，节点０上所有发往组Ｇ 的小消 息在相应的首进程Ｐ。 聚合成为大的消息．聚合消 息的大小是Ｍ×ｍ×ｇ，即Ｍ× ×Ｍ／ｄ．然后，在消 息聚合完成后，ｄ个通信域同时进行节点间的Ａｌｌｔｏａｌｌ 通信，因此节点间的Ａｌｈｏａｌｌ通信所对应的三元组 为｛ｄ，Ｎ／Ｍ，Ｍ× ×Ｍ／ｄ｝．最后，在节点间Ａｌｈｏａｌｌ 通信完成后，首进程将获得的聚合消息分散给同一 组的所用进程． 李 强等：ＭＰＩ Ａｌｌｔｏａｌｌ通信在多核机群中的优化 Ｆｉｇ．７ ＰＬＰ ｍｅｔｈｏｄ ｗｉｔｈ ｄ ｌｅａｄｅｒ ｐｒｏｃｅｓｓｅｓ 图７首进程数目为ｄ的ＰＩ Ｐ方法 如２．１节所述，首进程的算法的性能主要取决 于节点问的Ａｌｌｔｏａｌｌ通信．为了使节点间的Ａｌｌｔｏａｌｌ 通信获得最大性能，两方面的因素需要考虑，首先是 Ａｌｌｔｏａｌｌ算法的选择，其次是网卡的利用．如下所述， ＰＬＰ方法根据消息的长度选择不同的首进程数目． 其中，Ｍ的所有约数通过集合｛１，ｄ ，ｄ。，…，Ｍ）来表 示，它们满足１％ｄ ＜ｄ …＜Ｍ． １）当消息长度 满足Ｍ×Ｍｘｍ≤Ｓｉｚｅ 时，即 ≤Ｓｉｚｅ 。／Ｍ×Ｍ时，不管采用Ｍ的哪一 个约数，节点间的Ａｌｌｔｏａｌｌ通信都采用Ｂｒｕｃｋ算法， 此时应该采用更多的首进程来充分利用网卡，因此 首进程的数目为Ｍ． ２）当消息长度 满足Ｍ×Ｍ×ｍ＞Ｓｉｚｅ。 。 Ｉ， 并且Ｍ×Ｍ×ｍｉｄ１≤Ｓｉｚｅｃ ｌ时，即ｍ满足 Ｓｉｚｅ ｌｉｃａ１／Ｍ×Ｍ＜ｍ≤Ｓｉｚｅｃ ， ｌ／Ｍ×Ｍ×ｄｌ，对于首 进程数目１，节点间的Ａｌｌｔｏａｌｌ通信采用Ｖｉｒｔｕａｌ Ｒｉｎｇ算法，而对于其他首进程数目，节点问的 Ａｌｌｔｏａｌｌ通信采用Ｂｒｕｃｋ算法，由２．１节可知，此时 算法因素是主要因素，因此首进程的数目为１． ３）当消息长度ｍ满足Ｍ×Ｍ×ｍｉｄ ＞Ｓｉｚｅｃ ｌ 并且Ｍ×Ｍ×ｍｉｄ ２≤Ｓｉｚｅｃｎｕ 时，即ｍ满足 Ｓｉｚｅ ／Ｍ￣Ｍ×ｄｌ＜ｍ≤Ｓｉｚｅｃ ｌ／Ｍ×Ｍ×ｄ２，对 于首进程数目ｌ和ｄ ，节点问的Ａ［［ｔｏａｌｌ通信都采 用Ｖｉｒｔｕａｌ Ｒｉｎｇ算法．由于较多的首进程可以更充 分利用网卡，因此首进程的数目为ｄ ． 依次类推，ＰＩ Ｐ方法首先考虑算法因素，在算 法因素相同的前提下它会选择较大的约数作为首进 程数目，从而可以更好地利用网卡． ３．２ ＬＳＳ方法 针对Ａｌｌｔｏａｌｌ大消息通信，ＬＳＳ方法减少了同 步消息的总数．在最新的Ｔｏｐ ５００中，４１．２０ 的机 群使用Ｉｎｆｉｎｉｂａｎｄ网络，虽然在本文中，ＬＳＳ方法主 要基于Ｉｎｆｉｎｉｂａｎｄ网络进行阐述，但是它也适用于 其他的支持ＲＤＭＡ操作的网络．如图８所示，它的 实现绕过了ＭＰＩ点到点通信，直接实现在Ｉｎｆｉｎｉｂａｎｄ 的通信协议Ｖｅｒｂｓ上． Ｆｉｇ．８ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＬＳＳ ｍｅｔｈｏｄ 图８基于ＬＳＳ方法的Ａｌｌｔｏａｌｌ实现 ３．２．１缓冲区内存的注册 ＲＤＭＡ操作需要使用缓冲区内存的物理地址 信息，因此，每个进程在发起Ａｌｌｔｏａｌｌ操作后，首先 对缓冲区的内存进行注册．在Ｉｎｆｉｎｉｂａｎｄ网络中，通 过内存注册获得的物理地址信息包括一个６４ Ｂ的 关键字和缓冲区的起始虚拟地址，它可以用二元组 ｛ｋｅｙ，Ｖａｄｄｒ｝表示．对于任意进程Ｐ ，我们用Ｊ 来 表示它的接收缓冲区的物理地址信息．在Ｎ个进程 参与的Ａｌｌｔｏａｌｌ通信中，进程Ｐ 的接收缓冲区包含 Ｎ个长度相同的接收消息．通过Ｉ ，我们可以获得第 Ｊ个接收消息所对应的物理地址消息｛ｋｅｙ，Ｖａｄｄｒ＋ × ），其中ｍ为消息的大小． ３．２．２减少用于握手的同步消息 在内存注册完成之后，ＬＳＳ方法的执行流程集 成在Ｖｉｒｔｕａｌ Ｒｉｎｇ算法中．ＬＳＳ方法通过进程的相 互协作实现进程间的同步以及接收缓冲区物理地址 信息的收集．图９给出了进程Ｐ 前３步的执行流程． １）在第０步，进程Ｐ 将发送缓冲区中发往自 身接收缓冲区中的相应位置，在拷贝完成后，进程 Ｐ 新增物理地址信息的数目为０． ２）在第１步，进程Ｐ 发送消息到进程Ｐ…． 两个进程首先通过握手消息进行同步，握手消息包 含各自的物理地址信息ｆ 和Ｉ ＋ ．在握手完成后， 进程Ｐ 获得Ｊ ．同时，进程Ｐ 需要接收来自进程 Ｐ 的消息．通过它们之间的握手消息，Ｐ 获得 ．因此在第１步完成后，进程Ｐ 新增物理地址 信息 和Ｉ ． ３）在第２步，进程Ｐ 发送消息到进程Ｐ ，两 个进程首先进行握手，握手消息包含ｊ ， 和 ，Ｉ ．在握手完成后，进程Ｐ 获得Ｉ 和 ． 同时，进程Ｐ 需要接收来自进程Ｐ 的消息．通过 它们之间的握手，Ｐ 获得 和ｊ 。．因此在第２步 完成后，进程Ｐ 新增物理地址信息 ， 和 Ｊ ＋２，Ｉ汁 ． ４）在第ｋ步，当０≤是＜￣／Ｎ一１时，进程Ｐ 新 增２愚个物理地址信息． Ｐｉ一２ Ｐｉ一１ Ｐｔ ＰＩ＋１ ＰＩ＋２ ｓｔｅ 。口 亘亘亘 Ｆｉｇ． ９ Ｒｅｄｕｃｉｎｇ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｍｅｓｓａｇｅｓ ｆｏｒ ｈａｎｄｓｈａｋｅｓ． 图９ ＬＳＳ方法减少握手消息的执行流程 在第ｋ步执行完成后，进程Ｐ 获得的物理地址 消息总数如式（６）所示．显然，当 ＞￣／Ｎ时，进程Ｐ 获得了所有Ｎ个进程的物理地址信息．因此，当尼＞ ￣／』＼，时，ＬＳＳ方法不再需要握手消息，它将同步消息 的数目从原来的２Ｎ减小到２￣／Ｎ． １＋２（１＋２＋３＋…＋ｋ）一１＋ｋ（ｋ＋１）．（６） ３．２．３减少用于完成通知的消息 ＲＤＭＡ操作在执行完成后，并不通知接收方 数据的到达．在当前的实现中，发送方需要发送ＦＩＮ 消息来通知接收方ＲＤＭＡ操作的完成，为了减小 完成通知消息的数目，ＬＳＳ方法采取如下的优化 方法． 在Ｖｉｒｔｕａｌ Ｒｉｎｇ算法执行之前，每个进程将Ｎ 个接收消息所对应的接收缓冲区的最后６４ ｂ设置 计算机研究与发展２０１３，５０（８） 为缺省值Ｖ 如Ｏｘｆｆｆｆｆｆｆｆｆｆｆｆｆｆｆｆ．所有进程所设 置的缺省值是相同的．如图１Ｏ所示，在第ｋ步，进程 Ｐ 向进程Ｐ 发送消息．在执行完ＲＤＭＡ操作后， 进程Ｐ 检查发送缓冲区最６４ ｂ的值Ｖ ，看它是 否等于 如果两个值不相等，进程Ｐ 不发送 ＦＩＮ消息，否则，它将发送ＦＩＮ消息．ＲＤＭＡ操作 保证最后发送的数据最后到达接收方，因此通过检 查接收消息最后６４ ｂ的值是否改变或者是否接收 到ＦＩＮ消息，进程Ｐ 可以获知ＲＤＭＡ操作的完成 情况．如果两个条件中任意一个条件成立，则进程 Ｐ 可以得出ＲＤＭＡ操作完成的结论． Ｅ ＲＤＭＡ 目Ｖｄｅｆａｕｌｔ ＼＿ Ｆｉｇ． １ ０ Ｒｅｄｕｃｉｎｇ ｓｙｎｃｈｒ０ｎｉｚａｔｉｏｎ ｍｅｓｓａｇｅｓ ｆｏｒ ｃｏｍｐｌｅｔｉｏｎ ｎｏｔｉｆｉｃａｔｉｏｎ． 图１Ｏ Ｉ ＳＳ方法减少完成通知消息的执行流程 由于两个６４ ｂ值相等的概率非常小，在很多情 况下，并不需要发送ＦＩＮ消息，因此ＬＳＳ方法所使 用的ＦＩＮ消息的数量可以忽略不计．结合减少的握 手消息，与原来的实现相比，ＬＳＳ方法将所有的同步 消息从３Ｎ减小到２￣／Ｎ． ４ 性能评测 我们在Ｍｖａｐｉｃｈ一１．２ｒｃｌ库中实现了两种方法． 实验平台是拥有２０个节点的Ｉｎｆｉｎｉｂａｎｄ网络机群． 每个节点使用２路６核的２ ６６６ ＭＨｚ Ｉｎｔｅｌ￣Ｘｅｏｎ￣ Ｘ５６５Ｏ处理器，并且拥有一块４０ Ｇｂｐｓ的Ｍｅｌｌａｎｏｘ ＣｏｎｎｅｃｔＸ ＭＴ２６４２８ ＨＣＡ网卡．它们通过曙光 ＱＤＲ ＨＳＳＭ ３６端口的交换机连接起来．操作系统 为ｃｅｎｔｏｓ ５．３，内核版本为２．６．１８—１２８．ｅｌ５． ４．１ Ａｌｌｔｏａｌｌ小消息通信的性能 我们通过两种不同的配置来验证ＰＬＰ方法，在 配置Ａ中，１６０个进程参与Ａｌｌｔｏａｌｌ通信，每个节点 李 强等：ＭＰＩ Ａｌｌｔｏａｌｌ通信在多核机群中的优化 上运行８个进程．在配置Ｂ中，２４０个进程参与 Ａｌｈｏａｌｌ通信，每个节点上运行１２进程． 在配置Ａ中，Ｍ＝８，因此可以使用的首进程数 目为｛１，２，４，８｝．在Ｍｖａｐｉｃｈ一１．２ｒｃｌ库中，Ｓｉｚｅｃ Ｉ一 ８ １９２ Ｂ，表２显示了Ｏｎｅ－ｌｅａｄｅｒ，Ｍ—ｌｅａｄｅｒ以及ＰＩ Ｐ ３种不同的方法所采用的首进程数目，其中ＰＬＰ方 法根据消息的长度采用不同的首进程数目．与配置 Ａ类似，在配置Ｂ中，Ｍ一１２，因此可以采用的首进 程数目为｛１，２，３，４，６，１２｝．为了简化起见，在本文中 我们没有罗列配置Ｂ中ＰＩ Ｐ方法所采用的首进程 数目． Ｔａｂｌｅ ２ Ｌｅａｄｅｒ Ｐｒｏｃｅｓｓ Ｎｕｍｂｅｒ ｏｆ Ｄｉｆｆｅｒｅｎｔ Ｍｅｔｈｏｄｓ 表２不同方法的首进程数目 图１１显示了配置Ａ中３种方法的性能（图中 的性能为Ａｌｈｏａｌｌ通信时间的倒数，并且以ＰＬＰ方 法为基准）．与Ｏｎｅ ｌｅａｄｅｒ和Ｍ—Ｌｅａｄｅｒ方法相比， ＰＩ Ｐ方法总是可以获得最优的性能．然而由于Ｏｎｅ— ｌｅａｄｅｒ和Ｍ—ｌｅａｄｅｒ方法采用的固定的首进程数目， 目ＰＬＰ 日０ｎｅ．１ｅａｄｅｒ ＦＪ Ｍ．１ｅａｄｅｒ １．。 。．８ ｌ 邑 塞叫 。・２ ０．Ｏ １６ ３２ ６４ １２８ ２５６ ５１２ １ ０２４ ２ ０４８ ４ ０９６ Ｍｅｓｓａｇｅ Ｓｉｚｅ／Ｂ Ｆｉｇ．１ ｌ Ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｉｎ ｔｈｅ ｃｏｎｆｉｇｕｒａｔｉｏｎ Ａ． 图１１ 配置Ａ中３种方法的性能 对于某些消息，它们的性能与ＰＬＰ方法的性能相差 很大．对于不大于１２８ Ｂ的消息，由于Ｏｎｅ—ｌｅａｄｅｒ方 法在节点内采用一个首进程，它所对应的节点问的 Ａｌｈｏａｌｌ通信不能充分利用网卡，因此其性能远低于 采用８个首进程的ＰＬＰ和Ｍ—ｌｅａｄｅｒ方法．对于６４Ｂ 的消息，ＰＩ Ｐ方法的性能是Ｏｎｅ—ｌｅａｄｅｒ方法的１．８ 倍．对于大于２５６ Ｂ并且小于１ ０２４ Ｂ的消息，由于 Ｍ—ｌｅａｄｅｒ方法采用８个首进程，它所对应的节点间 的Ａｌｈｏａｌｌ通信中采用Ｂｒｕｃｋ算法．然而此时节点 间的Ａｌｌｔｏａｌｌ通信更适宜采用Ｖｉｒｔｕａｌ Ｒｉｎｇ算法， 因此它的性能远低于采用Ｖｉｒｔｕａｌ Ｒｉｎｇ算法的ＰＩ Ｐ 和Ｏｎｅ—ｌｅａｄｅｒ方法的性能．对于１ ０２４ Ｂ的消息， ＰＩ Ｐ方法的性能是Ｍ～ｌｅａｄｅｒ方法的２倍． 图１２显示了配置Ｂ中３种方法的性能．对于 ０ｕ磊基 ０ １ Ｏ ０ Ｏ 配置Ｂ，虽然ＰＩ Ｐ采用的首进程数目集合为｛１，２，Ｏ ８ ６ ４ ３，４，６，１２｝，ＰＩ Ｐ方法仍然可以获得最优的性能．对 于某些消息，ＰＬＰ方法的性能远高于Ｏｎｅ ｌｅａｄｅｒ和 Ｍ—ｌｅａｄｅｒ方法的性能．对于３２ Ｂ的消息，ＰＩ Ｐ方法 的性能是Ｏｎｅ—ｌｅａｄｅｒ方法的１．９倍，而对于５１２ Ｂ 的消息，ＰＩ Ｐ方法是Ｍ—ｌｅａｄｅｒ方法的２．４倍． 目ＰＬＰ 图ｏｎｅ．１ｅａｄｅｒ 目Ｍ－ｌｅａｄｅｒ ｌ６ ３２ ６４ １２８ ２５６ ５１２ １ ０２４ ２０４８ ４ ０９６ Ｍｅｓｓａｇｅ Ｓｉｚｅ／Ｂ Ｆｉｇ．１ ２ Ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｉｎ ｔｈｅ ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｂ． 图１２配置Ｂ中３种方法的性能 ４．２ Ａｌｌｔｏａｌｌ大消息通信的性能 与基于点到点通信的实现相比，图ｌ３给出了不 同进程规模下ＬＳＳ方法所减少的Ａｌｈｏａｌｌ大消息通 信时间，同时图１４给出了相应的性能提高（图中的 性能为Ａｌｈｏａｌｌ通信时间的倒数）．在Ａｌｌｔｏａｌｌ大消 息通信中，竞争极大地增加了同步消息的延迟．由于 ＬＳＳ方法将同步消息的数目从３Ｎ减少到２￣／Ｎ，因 此它在很大程度上减小了Ａｌｌｔｏａｌｌ大消息的通信时 间，这在图１３和图１４中获得了证明．在图１３中，减 少的通信时间十分明显，并且它们在图１４中对应的 Ｏ ２ Ｏ ０ ∞ｉ＼ 口 对 ｑ ｕ３寸 ×Ｐ０＿【 性能提高也是十分显著的．对于相同长度的消息，踮 ∞ 减 ０ 少的通信时间与进程的规模呈线性关系，并且在图 １４中对应的性能提升比例几乎为常数．对于３２ ＫＢ 和６４ ＫＢ的消息，它们的性能提高了２５％． 十３２ ＫＢ －啸 ６４ ＫＢ— １２８ ＫＢ —÷｝～２５６ＫＢ—静～５１２ＫＢ一十～１ ０２４ＫＢ 一 ＾、＼ 一 ／ 一 ／ ： 十一 二 一 撩一 ～ 二．＿一一－叶一－— １２Ｄ １３２ １４４ １５６ １６８ １８０ １９２ ２０４ ２１６ ２２８ ２４０ Ｐｒｏｃｅｓｓ Ｎｕｍｂｅｒ Ｆｉｇ．１ ３ Ｒｅｄｕｃｅｄ ｌａｔｅｎｃｙ ｗｉｔｈ ＬＳＳ ｍｅｔｈｏｄ． 图１３ ＬＳＳ方法减少的通信时间 ∞０是ｌ０ ０ １ １ ０ Ｏ ２ Ｏ ８ ６ —－＿３２ＫＢ— ６４ＫＢ—ｘ＿１２８ＫＢ — 卜２５６ＫＢ—毒～５１２ＫＢ— ～ｌ ０２４ＫＢ 一一一 ．一一一一一 一 ———。——＿一 ■一一 一 一——— 一 孓—旱一；一暑—；～～；一罩～ 一；～—千～ ： １２０ １３２ １４４ １５６ １６８ １８０ １９２ ２０４ ２１６ ２２８ ２４０ Ｐｒｏｃｅｓｓ Ｎｕｍｂｅｒ Ｆｉｇ．１ ４ Ｐｅｒｆｏｒｍａｎｃｅ ｉｍｐｒｏｖｅｍｅｎｔ ｗｉｔｈ ＬＳＳ ｍｅｔｈｏｄ． 图１４ ＬＳＳ方法带来的性能提升 当消息的长度变大时，消息需要更长的网卡服 务时间，消息所面临的竞争压力也随之变大．因此， 在图１３中，当进程规模不变时，长度较大的消息获 得更大的减少时间，这是因为它们所对应的同步开 销更大．当消息长度为６４ ＫＢ时，它所减少的通信时 间是３２ ＫＢ消息的２倍．同时，６４ ＫＢ消息的传输时 间几乎是３２ ＫＢ消息传输时间的２倍，因此３２ ＫＢ 消息和６４ ＫＢ消息所对应的性能提升比例十分接 近．当消息的长度大于６４ＫＢ时，随着消息长度的增 加，消息的传输时间也随之增大，因此在图１４中，相 应的性能提升比例随之下降． ４．３ ＦＦＴ应用性能 为了评估两种方法对应用的性能提高，我们使 用ＦＦＴ测试用例Ｐａｒａｌｌｅｌ ＦＦＴＥ ｌ１ 来评估它们的性 计算机研究与发展＼甚 ＩＩ１０ ０ＪｄＩＩＩＨ ２０１３，５０（８） 能．在ＦＦＴ中，Ａｌ∞ ｌｔｏａｌｌ通信的时间占整体执行时间 加 ｍ ５ ０ 的很大比例． 为了评估ＰＬＰ方法，ＦＦＴ采用的问题规模为 １２０×１２０×１２０．在不同的进程总数１２０，１８０和２４０ 下，Ａｌｈｏａｌｌ通信中的消息的长度分别为１９２０，８４８ 和４８０ Ｂ．图１５显示了ＰＬＰ，０ｎｅ—ｌｅａｄｅｒ和Ｍ—ｌｅａｄｅｒ ３种不同的方法所对应的性能．对于３种不同长度 的小消息的Ａｌｌｔｏａｌｌ通信，ＰＩ Ｐ方法的性能是最高 的，因此当采用ＰＬＰ方法时ＦＦＴ获得最好的性能． 瞄ＰＬＰ 静Ｏｎｅ－ｌｅａｄｅｒ 妇Ｍ．１ｅａｄｅｒ Ｏ Ｏ ０ ４ ２ ０ １２０ １８０ ２４０ Ｐｒｏｃｅｓｓ Ｎｕｍｂｅｒ Ｆｉｇ．１５ Ｐｅｒｆｏｒｍａｎｃｅ ｗｉｔｈ ｓｈａｐｅ ｓｉｚｅ ｏｆ ｌ２０×ｌ２Ｏ×ｌ２０ 图１５ １２Ｏ×１２Ｏ×１２Ｏ规模下的性能 为了评估ＬＳＳ方法，ＦＦＴ采用的问题规模为 ４８０×４８０×４８０．在不同的进程总数１２０，１８Ｏ和２４０ 下，Ａｌｈｏａｌｌ通信中的消息的长度分别为１２３ ＫＢ，６３ ＫＢ 和３１ ＫＢ．如图１６所示，ＬＳＳ方法针对不同的进程 规模都带来了性能提升．如图１４所示，当消息长度 为３２ＫＢ和６４ ＫＢ消息时，Ａｌｈｏａｌｌ通信获得最大比 例的性能提升．因此当进程总数为１８０和２４０时，它 们获得的性能高于进程总数为１２０的情况，它们的 性能提高了２０ ． Ｆｉｇ．１６ Ｐｅｒｆｏｒｍａｎｃｅ ｗｉｔｈ ｓｈａｐｅ ｓｉｚｅ ｏｆ ４８０×４８０×４８０ 图１６ ４８０×４８０×４８０规模下的性能提升 ５ 相关工作 已有的很多工作是关于ＭＰＩ Ａｌｈｏａｌｌ通信优化 李 强等：ＭＰＩ Ａｌｌｔｏａｌｌ通信在多核机群中的优化 的．文献［８－１Ｏ］主要研究如何动态地选择最优的 Ａｌｌｔｏａｌｌ算法，它们表明不同的算法对Ａｌｌｔｏａｌｌ通信 性能影响很大．文献［１１］研究了多核环境下节点内 集合通信的优化．在本文中，我们借鉴了这些研究的 成果，并结合Ａｌｌｔｏａｌｌ算法分析了首进程数目和同 步开销对Ａｌｈｏａｌｌ通信的影响． 为了利用共享内存提高Ａｌｈｏａｌｌ的通信性能， 文献Ｆ４３在早期的ＳＭＰ提出了Ｏｎｅ—ｌｅａｄｅｒ的方法； 文献［５］在多核的体系结构下提出了Ｍ—ｌｅａｄｅｒ方 法，它采用多个首进程来利用网卡，从而获得较好的 性能．然而，这两种方法针对所有不认同长度的消息 采用相同的首进程数目．与这两种方法不同，ＰＬＰ 方法根据消息的长度采用不同数目的进程，相对于 这两种方法它总是可以获得较好的性能． 为了减少Ａｌｌｔｏａｌｌ大消息通信中的同步开销， 文献［１２］采用Ｄｉｒｅｃｔ Ｅａｇｅｒ的方法将同步消息的数 目从３Ｎ减小到２Ｎ，从而提高了Ａｌｌｔｏａｌｌ大消息通 信的性能．文献［１３］采用ＭＰＩ Ａｌｌｇａｔｈｅｒ操作实现 了所有进程的同步以及接收缓冲区物理地址信息的 获取，然而根据文献［１４］，Ａｌｌｇａｔｈｅｒ操作会吸收额 外的系统噪声，从而影响Ａｌｌｔｏａｌｌ通信的性能．在本 文中，ＬＳＳ方法进一步减小了同步消息的数目，它将 同步消息的数目从３Ｎ减小到２￣／Ｎ． ６结论和未来工作 ‘多核机群既为Ａｌｌｔｏａｌｌ通信带来了有利的～面 面也带来了不利的一面．一方面，同一节点内的多个 进程可以利用共享内存优化通信性能．另一方面同 一节点内的进程需要竞争节点内有限的网络资源， 而竞争会导致同步开销变大．在本文中，对于Ａｌｌｔｏａｌｌ 小消息通信，与当前首进程数目固定的方法不同， ＰＬＰ方法针对不同长度的小消息采用不同的首进 程数目，因此它可以使所有不同长度的小消息都获 得最优的性能．对于Ａｌｌｔｏａｌｌ大消息通信，ＬＳＳ方法 将同步消息的数目从３Ｎ减小到２￣／Ｎ，从而减少了 同步开销，并使Ａｌｌｔｏａｌｌ大消息通信获得比例为常 数的性能提升．对于３２ ＫＢ和６４ＫＢ的消息，它们的 性能提高了２５ ． 在下一步工作中，我们将在更大的规模上评测 ＰＩ Ｐ和ＬＳＳ方法，同时，ＭＰＩ包括多种集合通信如 ＭＰＩ Ａｌｌｇａｔｈｅｒ等，我们将在多核机群中对这些集 合通信进行类似的优化． 致谢 感谢张攀勇和张翔在论文撰写过程中所 给予的帮助！ 参 考 文 献
