硬件集合通信中聚合樹構建方法

陳淑平 尉紅梅 王 飛 李 祎 何王全 漆鋒濱

（國家并行計算機工程技術研究中心 北京 100190）

目前超級計算機已經邁入E 級計算時代，但隨著摩爾定律接近失效、顛覆性使能技術遲遲不能實現，超級計算機在訪存、通信、能耗等方面仍面臨嚴重的發展瓶頸[1]. 而MPI（message passing interface）集合通信[2]是高性能計算中最重要的通信類型，對整機系統的性能具有重要的影響，提升MPI 集合通信性能是突破通信墻的重要手段. 傳統的MPI 集合通信是基于點到點消息實現的[3-4]，隨著系統規模的不斷擴大，這種實現方式面臨越來越嚴重的性能及可擴展性問題，而硬件集合通信具有性能高、可擴展性好等優點，正受到越來越多的關注[5].

硬件集合通信中，數據沿聚合樹進行規約或廣播操作，聚合樹的高度、負載均衡性等對集合操作的性能具有至關重要的影響. 本文研究了影響硬件集合通信性能的因素，提出了硬件集合通信開銷模型，并以此為基礎提出了構建硬件集合通信聚合樹的方法. 本文主要貢獻包括4 個方面：

1） 提出了硬件集合通信開銷模型，能夠較精確地計算硬件集合通信的時間開銷；

2） 研究了如何根據消息大小確定聚合樹的寬度，從而在網絡傳輸開銷與數據計算開銷之間取得平衡，以降低集合操作的延遲；

3） 針對Ⅰ型聚合樹，提出了最小高度分層k項聚合樹構建方法，相比傳統的Ⅰ型聚合樹，降低了跨組聚合包的個數，減少了網絡擁塞；

4） 針對Ⅱ型聚合樹，提出了最小代價Ⅱ型聚合樹構建方法，減少了聚合樹使用的交換機數量.

1 研究背景

1.1 硬件集合通信簡介

近年來，網絡計算技術發展迅速[6-7]. 網絡計算可將數據規約計算、協議處理、數據加解密等原本由處理器承擔的計算任務卸載到網絡設備中進行，解放了CPU，使CPU 可以專注于其他任務的處理. 在高性能計算領域，可利用網絡計算提升MPI 集合通信性能. 本文將基于網絡計算實現的MPI 集合通信稱為硬件集合通信. MPI 集合通信中，Barrier，Bcast，Reduce，Allreduce 是應用最廣泛的操作，它們均是1對多或多對1 的通信模式，適于以硬件集合通信方式實現. 圖1 顯示了Allreduce 的實現過程，它利用聚合樹完成數據聚合及結果分發操作，該樹中葉節點對應通信進程，根節點及中間節點對應交換機. 進行集合通信時，數據先從葉節點向根節點聚合，并在聚合的過程中計算規約結果；到達根節點后再沿反方向將規約結果廣播給所有葉節點. 其他集合操作的實現方式與此類似.

Fig. 1 Implementation phases of Allreduce operation based on in-network-computing圖1 基于網絡計算的Allreduce 操作實現過程

目前，很多公司推出了面向高性能計算的硬件集合通信技術，如IBM BlueG/Q 中的硬件集合通信原語[8-11]、Mellanox 的SHARP 技術[5,12-14]、神威互連網絡中的硬件集合通信[15]等. 相較于點到點消息實現的集合通信，硬件集合通信的性能有了顯著提升. Zimmer等人[16]在Summit 系統中利用基準程序對SHARP 性能進行了測試，4 096 個節點規模下集合消息性能至少提升了1 倍.

1.2 硬件集合通信使用中存在的問題

硬件集合通信除了需要特殊的硬件支持外，還需要網絡管理軟件的密切配合，以完成聚合樹分配、多播路由配置等操作. 其中，聚合樹分配是其中最為關鍵的操作. 現有的硬件集合通信技術在分配聚合樹時還存在3 個問題：

1） 缺乏精確的集合通信開銷模型，無法更好地指導聚合樹構建. 基于 α- β模型的軟件集合通信開銷模型[3]過于簡化，而針對特定網絡的專用模型又不具備通用性[17]，它們均不適用于硬件集合通信.

2） 構造聚合樹時未考慮相互干擾問題. 當系統中存在大量通信域時，需要為每個通信域分配1 棵獨立的聚合樹，以降低各通信域間的相互干擾，而現有的聚合樹分配方法未充分考慮到該問題. 例如，SHARP 技術中每個作業的所有通信域共享同一棵聚合樹[18]，這會產生嚴重的相互干擾. 現有的聚合樹構建方法也沒有考慮到同一聚合樹內不同消息間的相互干擾問題. 例如，傳統方法構建出的聚合樹會產生較多的跨組通信，使得同一集合操作的不同消息因競爭通信鏈路而相互干擾.

3） 未考慮硬件通信資源不夠用問題. 網絡中用于支持硬件集合通信的資源是有限的，而現有的聚合樹構建方法未考慮該問題，導致出現通信資源不夠用的情況. 例如，BlueG/Q 中每個網絡節點最多支持12 棵聚合樹，在很多情況下，由于聚合樹數量不足，無法使用硬件集合通信[11].

針對上述3 個問題，本文研究如何建立硬件集合通信開銷模型，以及如何基于該模型高效地構建聚合樹.

2 硬件集合通信開銷模型

2.1 定義及假設

定義1.互連網絡. 互連網絡定義為有向圖I=（N,L），其中N為網絡節點集合，L為通信鏈路集合. 網絡節點包括網卡及交換機. 本文假設網卡在I中均是葉節點.

定義2.聚合樹. 在互連網絡I=（N,L）上目標集合M（M?N）對應的聚合樹是一棵樹A=（NA,LA），M?NA?N，其中M是通信域中各進程所在的網卡集合.A中邊（ μ, υ）的長度定義為I中 μ到 υ的距離，也即I中從 μ到 υ經過的網絡鏈路數.A不必是I的子樹，也即不要求LA?L. 另外，M中允許有重復元素，從而使得每個節點上可同時運行多個通信進程. 聚合樹還需滿足度約束條件，也即每個節點的最大子節點數不能超過硬件閾值.

定義3.聚合樹高度. 設A=（NA,LA）是互連網絡I=（N,L）上目標集合M對應的一棵聚合樹，A中從葉節點出發到達根節點所經過的邊的最大條數，稱為聚合樹的高度. 只有1 個節點的聚合樹高度為0.

定義4.聚合樹半徑. 設A=（NA,LA）是互連網絡I=（N,L）上目標集合M對應的一棵聚合樹，A中從葉節點出發到根節點所經過邊的長度之和的最大值稱為聚合樹半徑. 聚合樹半徑實際上是從各葉節點出發沿該聚合樹依次經過各祖先最終到達根節點時所經過的最大鏈路條數.

現有的硬件集合通信技術中，有的僅支持將集合操作卸載到網卡中進行，有的則還可將集合操作卸載到交換機中進行. 根據不同的卸載位置，本文將聚合樹分為Ⅰ型聚合樹及Ⅱ型聚合樹2 種類型.

定義5.Ⅰ型聚合樹. 設A=（NA,LA）是互連網絡I=（N,L）上目標集合M對應的一棵聚合樹，若M=NA，則稱A為Ⅰ型聚合樹. 該類聚合樹中，集合操作均被卸載到網卡中執行，且僅使用進程所在的那些網卡.

定義6.Ⅱ型聚合樹. 設A=（NA,LA）是互連網絡I=（N,L）上目標集合M對應的一棵聚合樹，T=（NT,LT）是I的一棵子樹，M?NA?NT?N，且T中葉節點均在M中. 若?u∈NA，u在A中的父親p也是u在T中的某個祖先，則稱A為Ⅱ型聚合樹. Ⅱ型聚合樹中的集合操作均被卸載到交換機中進行.

圖2 顯示了Ⅰ型聚合樹和Ⅱ型聚合樹. 假設有8個進程參與集合通信，每個網卡上1 個進程，互連網絡的拓撲結構如圖2（a）所示；圖2（b）是一棵Ⅰ型聚合樹，高度為3，半徑為12；圖2（c）是一棵Ⅱ型聚合樹.

Fig. 2 Aggregate trees of type Ⅰ and type Ⅱ圖2 Ⅰ型聚合樹和Ⅱ型聚合樹

2.2 開銷模型

本文采用式（1）～（4）所示的開銷模型，模型中各變量的含義如表1 所示. 本文關注于如何降低聚合過程的開銷，下面著重對聚合過程開銷進行說明.

Table 1 Symbols Used in the Cost Model of Hardware Supported Collectives表1 硬件集合通信開銷模型中使用的符號

Taggregate是聚合過程的時間，其包括聚合包在網絡鏈路上的傳輸時間，以及在網絡節點內的處理時間. 假設聚合樹是k叉完全樹，聚合樹的半徑為ratree，則聚合包在網絡鏈路中的傳輸總時間為ratree×l. 設每個聚合包的匹配處理時間為 θ、存儲轉發時間為、規約計算時間為S*×γ，則聚合包在網絡節點內的處理總時間為最終得到式（2）所示的聚合時間開銷.

為進一步簡化模型，除了假設聚合樹是k叉完全樹之外，還假設任意2 個進程之間單播路由的路徑長度相等，均需經過 δ條鏈路，則對Ⅰ型聚合樹，hatree≈logkP，ratree≈δ×logkP，從而得到式（3）所示的聚合過程開銷. 而對Ⅱ型聚合樹，hatree≈，ratree≈0.5δ，從而得到式（4）所示的聚合過程開銷.

2.3 模型驗證

本文在新一代神威超級計算機上測試了各類集合消息的延遲，并與開銷模型計算出的結果進行對比. 實驗環境如圖3 所示.

Fig. 3 2-level fat tree used in the test environment圖3 測試環境使用的2 層胖樹

使用1 個超節點進行測試，超節點內共有256 個節點，每個節點安裝1 塊消息處理芯片，每塊消息處理芯片有2 個網絡端口，故整個超節點內共有512 個網絡端口. 這512 個網絡端口通過一棵2 層胖樹進行互連. 該胖樹共有48 臺交換機和其中32 臺葉交換機和16 臺骨干交換機. 每臺交換機的端口數均為40，其中有些端口未被使用. 每臺葉交換機有16 個端口用于連接消息處理芯片的網絡接口，16 個端口用于連接骨干交換機.

分別在不同進程數下測試了各種類型、各種長度集合消息的延遲. 測試方法為：每種類型及長度均測試5 000 次，每次測試進程均記錄集合操作的時間開銷，取耗時最長的那個進程的時間開銷作為該次集合通信的時間開銷，再取這5 000 個時間開銷的中位值作為當前類型、當前長度下集合消息的延遲.

限于篇幅，本文僅顯示了Ⅰ型聚合樹的部分測試結果. 不同進程數下，長度為8 B 的廣播操作的理論計算延遲與實際測試延遲如圖4 所示；進程數為512 時不同長度Bcast 消息的理論計算延遲與實際測試延遲如圖5 所示. 可以看出，Ⅰ型聚合樹的理論計算延遲與實際測試延遲最多相差0.5 μs. 這表明本文提出的硬件集合通信開銷模型能夠較準確地擬合實測延遲.

Fig. 4 Measured latency and estimated latency of collectives for different count of processes圖4 不同進程數下集合操作的實測延遲及理論計算延遲

Fig. 5 Measured latency and estimated latency of collectives for different message size when process count is 512圖5 進程數為512 時不同消息大小下集合消息的實測延遲及理論計算延遲

3 Ⅰ型聚合樹的構建

給定任意P個進程，為它們構造一棵開銷最小的Ⅰ型聚合樹是非常困難的，因為不但要考慮聚合樹寬度、聚合樹半徑等因素，還要考慮通信與通信重疊、通信與計算重疊、消息間相互干擾等因素的影響，故目前Ⅰ型聚合樹均是通過啟發式算法進行構造. 本節首先研究如何根據消息類型、消息長度等確定Ⅰ型聚合樹的寬度k，然后研究如何快速構造一棵聚合樹，使得跨組聚合包的個數盡可能地少，盡量降低消息間的相互干擾.

3.1 根據聚合包大小確定聚合樹的寬度

聚合過程的時間開銷包括聚合包的傳輸時間以及處理時間. 聚合樹的寬度k對聚合過程的時間開銷具有重要影響. 直觀上看，如果k很小，則聚合樹很高，相應地聚合包的傳輸開銷就很大；如果k很大，則每個網卡需要處理的聚合包很多，相應地聚合包的處理開銷就很大. 需要研究k對聚合時間開銷的影響.

先看如何選擇k才能使式（3）計算出的聚合開銷F(k)最小. 記定義如式（5）所示的F(k)，其導數函數如式（6）所示.

使F(k)取最小值的k記為k?，此時的F(k)記為F?.根據式（5）（6），要使F(k)取最小值，需F′(k)=0，也即k(lnk?1)=，而函數f(k)=k(lnk?1)是單調遞增的.對不同的集合操作類型及消息長度，取值不同，使F(k)取最小值的k也不同. 在本文的實驗環境中，對同步、廣播操作來說，k= 41 時F(k)取最小值.

很多情況下，選擇其他k值時，F（k）與F?差別不大. 以同步、廣播操作為例，在本文的實驗環境中，設P= 512，a= 1.12 μs，b= 0.01 μs，F(k)的曲線如圖6所示，可以看出，當24 ≤k≤64時，F(k)相差不大，不超過0.1 μs. 對每種類型、每種長度的集合消息，都可以確定區間[kmin,kmax]， 使得?k∈[kmin,kmax]時，|F(k)?F?|≤ε成立（ ε是常數）. 本文測試環境中使用的k如表2 所示（僅顯示了部分結果）. 可以發現，隨著聚合包長度增大，kmin及kmax均逐漸下降. 對該現象的直觀解釋是：當聚合包長度較小時，聚合包在網絡鏈路上的傳輸時間在總聚合時間中占比最大，此時應該采用較大的k，從而使得聚合包在網絡鏈路上的傳輸盡量并行；而當聚合包長度較大時，聚合包在網卡內的處理時間在總聚合時間中占比最大，此時應采用較小的k，以使更多的網卡參與聚合包的處理.

Table 2 Type Ⅰ Aggregate Tree Breadth Used in the Test Environment表2 測試環境中使用的Ⅰ型聚合樹寬度

Fig. 6 Curve of F(k) for Barrier and Bcast operation圖6 同步、廣播操作的F(k)曲線

3.2 傳統的聚合樹構建方法

確定k值后就可以構建聚合樹了. 式（3）假設任意2 個進程間的單播路由經過的鏈路數相等，但實際情況要復雜得多. 使用相同的k值構造的2 棵聚合樹值半徑ratree可能不同，導致聚合包的傳輸開銷不同.帶度約束的最小半徑聚合樹問題是NP 難的[19-21]，尚未有高效的求解辦法. 本文目標不是構造最優聚合樹，而是快速構造出一棵滿足度約束條件、半徑盡可能小、沖突盡可能少的聚合樹. 本節首先介紹2 種傳統的聚合樹構建方法.

3.2.1k叉樹

定義7.k叉樹.k叉樹是一棵完全樹，除最后一個中間節點外，根節點及其他中間節點都有k個子節點，故k叉樹是平衡樹，每個中間節點處理的聚合包個數相等.

在k叉樹中，按廣度優先遍歷方式為進程編號，根進程編號為0. 若進程在通信域內的編號為my_rank，則其父節點編號為（my_rank?1）/k，第i個子節點編號為my_rank×k+i(i≥1).

由于未考慮網絡拓撲結構，在胖樹網絡[22-23]、蜻蜓網絡[24]等具有分組結構的網絡中，k叉樹會產生大量的組間通信，導致網絡擁塞. 16 個進程構建聚合樹，其網絡拓撲如圖7 （a）所示，4 叉樹如圖7（b）所示. 粗線表示該聚合包需要經過最頂層的交換機，圖7（b）中共有8 個聚合包經過最頂層的交換機. 如果最頂層的交換機傳輸能力不足，則很容易在頂層交換機處形成擁塞. 而圖7（c）是另一棵聚合樹，其高度、半徑均與圖7（b）所示聚合樹一樣，但僅有2 個經過頂層交換機的聚合包，因而具有更優的性能.

Fig. 7 k-ary aggregate tree is prone to generate lots of intergroup communication圖7 k 叉樹易產生大量的組間通信

3.2.2k項樹

定義8.k項樹.k項樹[25]是一組遞歸定義的樹Tn，其中T0是1 個單節點的樹；而Tn是由k棵Tn?1連接起來構成的樹，其中k?1 棵Tn?1的根節點直接連接到另外那棵Tn?1的根節點上.k項樹第i層的節點數是(k?1)i×，節點總數是kn，高度為n.

圖8 分別顯示了一棵2 項樹及一棵4 項樹. 2 項樹是特殊的k項樹，在軟件集合通信中已得到了廣泛使用，例如在MPICH 中短的Bcast、Reduce 均是通過2 項樹實現的[3]；而大于2 的k項樹目前使用得較少.

Fig. 8 k-nomial tree （k=2, 4）圖8 k 項樹（k=2, 4）

與k叉樹不同，k項樹中不同深度的節點擁有不同數量的子節點，其中根節點的子節點數最多，為(k?1)×「logkP?；而隨著深度的增加，子節點數越來越少，故k項樹是非平衡樹.

由于k叉樹是平衡樹，k叉樹中上層節點要等待下層節點處理完畢之后才開始處理聚合包，故上層節點會存在空等待現象. 而k項樹是非平衡樹，位于不同層的節點可以并發處理聚合包，不存在空等待現象.

在k項樹中，按深度優先遍歷方式為進程編號.進程編號用k進制表示為kn?1···k2,k1,k0，其中最低位共有i個0（0 ≤i≤n），則第i個位置0 即可得到其父節點編號，從最低的i位中任選一位置為1,2,···,k?1，則得到其子節點的編號最多有i×（k?1)個子節點.

每個進程調用算法1 所示的build_k_nomial_tree函數計算parent_rank及children_cnt. 與k叉樹一樣，k項樹也會產生很多跨組通信.

算法1.build_k_nomial_tree.

3.3 分層k 項樹構建方法

傳統的聚合樹構建方法未考慮網絡拓撲結構，容易產生較多的組間通信，從而造成網絡擁塞. 為解決此問題，本文提出了分層k項樹構建方法.

分層思想是優化集合通信的一種重要策略[26-29]，該策略利用了不同的層具有不同數據傳輸性能的特點，將同一層內的進程組織成組，使盡可能多的通信在組內完成，以降低層間通信、提升集合消息性能.

在構建Ⅰ型聚合樹時，利用分層思想也可以降低聚合過程的時間開銷. Zhao 等人[25]提出了一種簡單方法：先將進程分為不同的組，并為每個組單獨構建一棵k項樹；然后將各組的首進程組成一個新的組，并創建一棵k項樹，從而將所有組連接起來形成一棵更大的k項樹. 進行聚合操作時，同一個組內的進程會先聚合到本組的首進程，首進程再聚合到更高層的首進程，從而大大減少組間通信. 但該方法產生的k項樹可能具有較大的高度. 圖9 舉了一個例子：通信域內共有14 個進程，依圖案分屬4 個不同的組.當k= 2 時，構建的聚合樹如圖9（a）所示，其高度為4.實際上，可以使某個組的首進程連接到另一個組的非首進程下，從而使得聚合樹更加平衡，以降低聚合樹的高度. 圖9（b）即是一棵更優的聚合樹，其高度為3. 本文的目標是在最小化組間通信的同時使聚合樹高度最低.

Fig. 9 Aggregate tree with hierarchical structure圖9 具有分層結構的聚合樹

3.3.1 問題定義

本文將具有相同通信特性的一組進程稱為一個進程組. 例如，位于同一節點內的多個進程，以及位于同一交換機內的多個進程等，均可構成一個進程組. 進程組可以嵌套，從而使得一個進程組可包含多個子進程組，最終構成1 個層次結構.

進程組由如圖10 所示的數據結構定義. 每個進程組都對應一棵k項樹，按深度優先方式為k項樹內的節點編號. 進程被映射到k項樹的某個節點上，樹中有些節點可能無映射進程. 該數據結構中，cnt是k項樹的節點數，它必須是k的冪；ranks_id是k項樹內各節點對應的進程號，nodes_id是各進程對應的k項樹節點號；sub_groups定義了屬于該進程組的子進程組，共有sub_grp_cnt個子進程組.

Fig. 10 The data structure of the process group圖10 進程組的數據結構

下面探討最小高度分層k項Ⅰ型聚合樹問題. 給定m個互不相交的進程組g0,g1,···,gm?1，g是滿足2個條件的進程組：1）g包含g0,g1,···,gm?1的所有進程；2）g對應的k項樹中，除首進程外其余進程的父節點均位于gi內；3）g對應的k項樹中，每個節點的兒子數不超過硬件限制. 該問題為從中找出具有最小高度的進程組g，從而為進程組g0,g1,···,gm?1構建一棵高度最小的分層k項Ⅰ型聚合樹. 進程組gi(0 ≤i＜m)內嵌套的子進程組也需滿足條件2.

設是進程組gi首進程的進程號，根據k項樹的性質，條件2 等價于且對gi內每個進程有(gi.cnt)，也即進程被映射到某個編號為gi.cnt倍數的聚合樹節點內，其余進程依次映射到后續節點內.

3.3.2 構建方法

給定m個進程組g0,g1,···,gm?1，且每個gi均已構建好各自的k項樹之后，即完成了ranks的設置，采用算法2 為這些進程組構建一棵更大的k項聚合樹. 算法2 采用貪心策略，每次找出2 個最大的進程組g0和g1，然后在g0的空閑子樹內尋找能夠容納g1的位置.如果找不到這樣的位置，則將g0的聚合樹高度加1，即cnt變為原來的k倍，從而使g0內有足夠的空余位置容納g1. 該過程持續下去，直到最終只剩1 個進程組為止. 算法2 行⑤代碼用于為g[i]尋找可用的位置，僅需檢查分塊的第1 個位置是否可用即可判斷整個分塊是否可用. 行?～?代碼用于將g[i]的ranks映射表拷貝到新的聚合樹中.

算法2.merge_groups.

采用數學歸納法可證明算法2 所產生的k項樹是高度最小的分層k項Ⅰ型聚合樹，限于篇幅，不再贅述證明過程.

算法3 以遞歸方式為每個層次建立進程到聚合樹節點的映射關系. 算法4 根據拓撲信息建立分層的k項樹.build_hierarchical_tree建立的聚合樹中，每個組的進程均位于同一子樹內，從而保證除該組的首進程外其余進程均向本組內的進程發送聚合包，故跨組聚合包的個數相比傳統聚合樹構建方法減少了. 在使用算法4 時，需要選擇合適的k，以保證聚合樹內每個節點的兒子數不超過硬件限制.

算法3.build_rank_mapping.

算法4.build_hierarchical_tree.

4 Ⅱ型聚合樹的構建

本節研究構造Ⅱ型聚合樹的方法. 構造Ⅱ型聚合樹時需要綜合考慮網絡拓撲、進程位置等因素. 另外，在每個交換機內，每棵Ⅱ型聚合樹都占用1 個聚合樹條目，而硬件支持的聚合樹條目是有限的，故創建Ⅱ型聚合樹時，還需要考慮是否有可用的聚合樹條目.

構造Ⅱ型聚合樹時要考慮3 個目標：1）最小化聚合樹的半徑，以降低集合操作延遲；2）盡量讓不同的聚合樹分布到不同鏈路上，以降低聚合樹間的相互干擾；3）使用盡可能少的聚合樹條目，以支持創建更多的Ⅱ型聚合樹.

本文分2 個步驟構造Ⅱ型聚合樹. 1）選擇1 個交換機作為樹根，并構造1 棵生成樹（稱為物理樹）；2）對物理樹進行裁剪，去掉不需要的交換機.

定義9.物理樹. 設M是某通信域內進程所在的網卡集合，T=（NT,LT）是互連網絡I=（N,L）的一棵子樹，若T滿足2 個條件，則稱T是關于M的物理樹：

1）M?NT；

2）T的葉節點除M中網卡之外，不包含任何其他網卡及交換機.

定義10.由物理樹推導出的Ⅱ型聚合樹. 設K是交換機節點的度約束函數，給定互連網絡I=（N,L）上一棵關于M的物理樹T=（NT,LT），由物理樹T導出的Ⅱ型聚合樹是滿足2 個條件的樹A=（NA,LA）：

1）M?NA?NT；

2）若?u∈NA，u在A中的父親p也是u在T中的某個祖先；

3）A中每個交換機sw的子節點數不大于度約束K（sw），其中K（sw）大于sw在T中的子節點數.

實際上，由物理樹T導出的Ⅱ型聚合樹A可看成是將T中某些節點提升位置而得到的（僅能提升為其祖先的兒子）.

定義11.Ⅱ型聚合樹的代價. 設A=（NA,LA）是互連網絡I=（N,L）上目標集合M對應的一棵Ⅱ型聚合樹，A中交換機的個數稱為該Ⅱ型聚合樹的代價，記為cost（A）.

4.1 選擇樹根并構建物理樹

樹根的位置決定了聚合樹的半徑，應該選擇到通信域內各進程最大跳步數最小的交換機作為樹根.

本文采用集中式方法構建物理樹. 在該方法中，由集中式的網絡管理軟件選擇樹根并構建物理樹.網絡管理軟件維護了網絡的狀態信息，包括交換機內空閑的聚合樹條目數、網絡鏈路的負載情況等. 網絡管理軟件可根據這些信息選擇一個交換機作為樹根.該方法具體過程為：先計算出每個交換機到通信域組內各進程的最小跳步數，據此找到所有的備選樹根. 然后根據備選樹根的負載情況對備選樹根進行排序，優先使用負載低的樹根. 選擇好一個樹根后，就可以構造一棵物理樹，使得每個進程到樹根的跳步數最少. 然后檢查該物理樹的每個交換機是否有空閑的聚合樹條目可用. 若每個交換機都有空閑的聚合樹條目，則返回該物理樹；若失敗，則嘗試下一個樹根.

4.2 構建最小代價Ⅱ型聚合樹

由物理樹導出的最小代價Ⅱ型聚合樹問題. 給定互連網絡I=（N,L）上一棵關于M的物理樹T=（NT,LT）及度約束函數K，在由物理樹T導出的Ⅱ型聚合樹中求代價最小的聚合樹A?.

本文利用算法5 所示的函數創建最小代價Ⅱ型聚合樹. 可以證明算法5 產生的聚合樹A?是由物理樹T導出的最小代價Ⅱ型聚合樹. 限于篇幅，證明不再贅述.

算法5.build_minimum_type_Ⅱ_tree.

圖11（a）顯示了一棵物理樹，該樹中共有16 個進程，使用了13 個交換機，每個交換機的度約束均為5；其導出的最小代價Ⅱ型聚合樹如圖11（b）所示，僅使用了4 個交換機.

Fig. 11 A physical tree and its reduced minimum cost type Ⅱaggregate tree圖11 一棵物理樹及其導出的最小代價Ⅱ型聚合樹

5 在2 種聚合樹中進行選擇

在性能方面，Ⅰ型聚合樹與Ⅱ型聚合樹各有優勢. 對長度較小的集合操作，聚合包的傳輸時間占主導，而Ⅱ型聚合樹中聚合包傳輸路徑較短，故延遲比Ⅰ型聚合樹低. 對長度較大的集合操作，規約計算時間占主導，Ⅰ型聚合樹可以將規約計算分布到大量網卡中并發進行，故延遲較小. 創建通信域時，需要綜合考慮各方面因素，選擇使用Ⅰ型聚合樹還是Ⅱ型聚合樹.

為簡化分析，假設Ⅱ型聚合樹是標準的d叉樹，記則Ⅰ型、Ⅱ型聚合樹的時間開銷分別如式（7）（8）所示. 為簡化討論，僅考慮S′=S?=S的情況.

定義如式（9）所示的函數F(d,k,P,S)：

可以根據式（9）～（11）分析F(d,k,P,S)的變化趨勢，并據此構造一張靜態映射表. 給定集合操作類型及消息長度后，通過查表即可快速確定聚合樹類型及寬度. 表3 列出了本文實驗環境中如何根據聚合包長度來選擇使用Ⅰ型聚合樹還是Ⅱ型聚合樹. 當申請不到創建Ⅱ型聚合樹所需的通信資源時，需要回退到Ⅰ型聚合樹.

Table 3 Method to Select Aggregate Tree表3 聚合樹選擇方法

6 性能評估

本節將在新一代神威超級計算機中對聚合樹性能進行測試.

6.1 Ⅰ型聚合樹性能評估

首先測試不同的Ⅰ型聚合樹集合消息的延遲.對同步、廣播、8B 長度的規約操作而言，選擇k= 32可以獲得更好的性能，故分別構造了32 叉樹、32 項樹、分層32 項樹. 使用1 個超節點進行測試，每個節點運行2 個進程，每個進程使用1 個網絡端口，這2個端口間的通信不需要經過網絡鏈路. 分別在2 種場景下進行測試.

6.1.1 2 層標準胖樹中的性能

在2 層標準胖樹中進行測試. 分層32 項樹使用了3 個層次，首先將位于同一節點的2 個進程組成1個組，這2 個進程間的通信不需要經過網絡鏈路；然后將位于同一交換機內的16 個進程組成1 個組，該組內的進程通信時僅需經過2 條鏈路；最后將位于同一超節點內的所有進程組成1 個組，該組內的進程通信時需經過4 條鏈路.

圖12 顯示了Bcast-8B，Bcast-2KB 這2 種集合操作的測試結果. 可以看出：1）大部分情況下32 叉樹、32 項樹幾乎具有相同的延遲；2）大部分情況下，分層32 項樹的延遲低32 叉樹、32 項樹約0.6 μs. 分層32 項樹延遲低的原因是：它先把位于同一節點內的2 個進程組成1 個組，而這2 個進程間通信不需要經過網絡鏈路，故延遲較低. 需要指出的是，進程數較少時分層32 項樹的延遲反而高于另外2 種聚合樹，原因是此時的分層32 項樹的高度大于32 叉樹、32項樹；隨著進程數的增多，這3 種聚合樹將具有相同的樹高.

Fig. 12 Messages latency of three types of aggregate trees for different count of processes in standard fat-tree topology圖12 標準胖樹拓撲中不同進程數下3 種聚合樹的消息延遲

不同消息長度時3 種構造方法下的聚合樹的性能如圖13 所示. 測試時使用了512 個進程，每個進程使用1 個網絡端口. 測試結果與圖12 的測試結果一致，即32 叉樹和32 項樹的性能相當，而分層32 項樹的延遲明顯低于32 叉樹和32 項樹.

Fig. 13 Messages latency of three types of aggregate trees for different message sizes in standard fat-tree topology圖13 標準胖樹拓撲中不同消息長度下3 種聚合樹的消息延遲

6.1.2 2 層裁剪胖樹中有噪聲干擾時的性能

使用如圖14 所示的裁剪胖樹進行測試. 該拓撲中，同一交換機內的不同網絡端口向其他交換機內的網絡端口發消息時會共享一條通信鏈路. 測試時還在網絡中加入了網絡噪聲，該噪聲消耗約80%的網絡帶寬.

Fig. 14 Illustration of two-layer pruned fat-tree used in the test圖14 測試使用的2 層裁剪胖樹示意圖

分別測試不同進程數時3 種方法構建的聚合樹的性能，并將之與標準胖樹下的測試結果進行了對比，結果如圖15 所示. 可以看出，加入網絡噪聲后，3種構建方法的集合消息延遲相比標準胖樹下有顯著增大. 其中32 叉樹增幅最大，分層32 項樹增幅最小.

Fig. 15 Collective messages latency in pruned fat-tree topology with inference圖15 裁剪胖樹拓撲下有干擾時集合通信消息延遲

圖16 顯示了進程數為512 時，3 種方法構建的聚合樹中跨組聚合包的數量，其中每條實線上的數字表示該實線所連接的2 個交換機間的聚合包個數.在32 叉樹中，大量聚合包發送到1 號交換機的不同進程內，故每個集合操作中，0 號交換機與1 號交換機間鏈路上需傳輸496 個聚合包，從而產生嚴重的鏈路競爭.

Fig. 16 Inter-group aggregation packets of three types of aggregate trees constructed methods in pruned fat-tree圖16 裁剪胖樹下3 種聚合樹構建方法的跨組聚合包

表4 顯示了不同進程數時3 種聚合樹下Bcast-8 B 的延遲對比，可以看出，在存在噪聲干擾的情況下，分層32 項樹的延遲相比傳統的聚合樹構建方法下降了24%～89%. 這表明，相比另外2 種聚合樹構建方法，分層32 項樹具有更少的跨組聚合包，因而存在帶寬競爭的情況下可以顯著降低集合消息的延遲.

Table 4 Bcast-8B Latency for Different Count of Processes in Pruned Fat-tree Topology with Inference表4 裁剪胖樹拓撲下有干擾時不同進程數下Bcast-8B 延遲

需要注意的是，隨著進程數的增大，32 項樹的延遲增加較緩慢，而分層32 項樹的延遲增加略快（分層32 項樹相比32 項樹的延遲下降比例由進程數為64 時的32%下降為進程數為512 時的24%）. 這是因為，在裁剪胖樹中，隨著進程數的增大，32 項樹中每條鏈路上傳輸的最大聚合包數保持為16，故32 項樹的延遲變化不大；而分層32 項樹中每條鏈路上傳輸的最大聚合包數由1 逐漸增大到31，故分層32 項樹的延遲會緩慢增加. 但可以肯定的是，隨著進程數的進一步增大，分層32 項樹的延遲仍低于32 項樹，這是因為32 項樹中每2 個相鄰交換機間都需要傳輸16 個聚合包，從而更易受網絡噪聲的干擾.

除此之外，本文還在其他場景下測試了3 種聚合樹構建算法的消息延遲. 例如，利用更多超節點進行了測試，其網絡拓撲采用3 層裁剪胖樹，故分層32 項樹可采用更多的層次. 此實驗的測試結論與上述測試結論一致，即分層32 項樹延遲最低，32 項樹次之，32 叉樹延遲最高. 限于篇幅，不再贅述其詳細測試數據.

6.2 Ⅱ型聚合樹性能評估

6.2.1 Ⅱ型聚合樹延遲測試

本節對Ⅰ型聚合樹及Ⅱ型聚合樹的性能進行對比. 測試環境如圖17 所示. 其中Ⅰ型聚合樹采用64叉樹進行構建，Ⅱ型聚合樹的樹根建在最高層的那個交換機上. 分別測試了不同進程數下2 種類型聚合樹的性能，Bcast-8 B 及Bcast-2 KB 的延遲如圖18所示. 可以看出，Ⅱ型聚合樹的延遲比Ⅰ型聚合樹低1 μs 左右.

Fig. 17 Network topology used to compare the performance of type Ⅰ and type Ⅱ aggregate trees圖17 使用網絡拓撲對比Ⅰ型聚合樹及Ⅱ型聚合樹性能

Fig. 18 Performance comparison of type Ⅰ and type Ⅱaggregate trees圖18 Ⅰ型聚合樹及Ⅱ型聚合樹的性能對比

6.2.2 Ⅱ型聚合樹資源使用量測試

本節測試最小代價Ⅱ型聚合樹構造算法的有效性以及不同通信模式下聚合樹條目的使用情況.

MPI 集合通信中，一般將進程劃分為2 維或3 維網格通信域，其每個維度中的每行或每列都是一個通信域. 本文測試了5 種典型的通信模式，包括2 種2 維網格結構、2 種3 維網格結構，以及1 種隨機模式. 選擇的2 維網格結構中，256 ×160 通信模式按拓撲結構劃分通信域，模擬拓撲感知的通信模式，即第1 維有160 個通信域，故每個通信域都位于同一個超節點內；而202 ×202 通信模式存在很多跨超節點的通信域，模擬拓撲無感的通信模式. 2 種3 維網格結構也是按類似原則進行劃分的. 隨機模式是指進程隨機加入一個通信域.

下面從2 個方面證明最小代價Ⅱ型聚合樹構造算法的有效性：一方面，最小代價Ⅱ型聚合樹占用的聚合樹條目數相比傳統方法構建的Ⅱ型聚合樹有顯著下降；另一方面，最小代價Ⅱ型聚合樹構建算法創建聚合樹時的失敗率相比傳統的Ⅱ型聚合樹也有顯著下降.

1） 聚合樹占用的總條目數

首先測試每種通信模式下聚合樹占用的總條目數. 假設每個交換機內的聚合樹條目數足夠多. 對于每種通信模式，依次為每個通信域構建Ⅱ型聚合樹，并統計占用的聚合樹條目總數，結果如圖19 所示. 其中，傳統方法構建的Ⅱ型聚合樹是指利用集中式方法構建的物理樹. 可以看出，所有通信模式下，最小代價Ⅱ型聚合樹占用的條目總數明顯低于傳統方法構建的聚合樹所占用的條目數，最少下降了90%. 這表明最小代價Ⅱ型聚合樹算法在降低聚合條目使用量方面具有顯著效果. 有些通信模式下，最小代價Ⅱ型聚合樹的聚合樹條目總數等于通信域個數，這是因為在這些通信模式下，每個通信域的最小代價Ⅱ型聚合樹都僅使用1 個交換機.

Fig. 19 Total count of aggregate tree entries used by type Ⅱaggregate trees for different kinds of communication patterns圖19 不同通信模式下Ⅱ型聚合樹使用的總聚合樹條目數

2）創建聚合樹時的失敗率

將每個交換機的聚合樹條目數設為16，然后在每種通信模式下依次為每個通信域構建Ⅱ型聚合樹，并記錄創建失敗的次數. 定義創建聚合樹時的失敗率為：結果如圖20 所示. 可以看出，最小代價Ⅱ型聚合樹算法均能為每個通信域成功構建聚合樹；而傳統的Ⅱ型聚合樹構建方法失敗率很高，最高可達74.51%.

Fig. 20 Failure rate of creating type Ⅱ aggregate trees in different communication patterns圖20 不同通信模式下創建Ⅱ型聚合樹的失敗率

需要指出的是，將交換機的聚合樹條目數設為更小的值后，某些通信模式下也存在不能創建最小代價Ⅱ型聚合樹的情況，但其失敗率仍低于傳統的Ⅱ型聚合樹構建方法，結果不再贅述.

綜上所述，最小代價Ⅱ型聚合樹算法可以顯著減少對交換機內聚合樹條目資源的占用，從而可以支持創建更多的Ⅱ型聚合樹.

7 結 論

硬件集合通信中，聚合樹對集合操作的性能具有重要影響. 構建聚合樹時，需要綜合考慮聚合樹半徑、寬度、負載均衡、網絡噪聲等的影響. 本文提出了硬件集合通信開銷模型，并據此提出了3 種構建聚合樹的方法，包括：1）根據聚合包大小確定Ⅰ型聚合樹的寬度；2）最小高度分層Ⅰ型聚合樹構建方法；3）最小代價Ⅱ型聚合樹構建方法. 然后在神威互連網絡中對聚合樹構建方法進行了全面測試，在存在網絡噪聲的情況下，分層Ⅰ型聚合樹的消息延遲相比傳統構建方法下降了24%～89%；最小代價Ⅱ型聚合樹使用的交換機聚合條目數相比傳統構建方法下降了約90%.

下一步，我們將利用真實的應用程序對聚合樹構建方法的性能進行更全面的測試. 另外，我們還將研究如何利用硬件集合通信提升長度較大的規約、廣播等集合操作的性能，擴大硬件集合通信的適用范圍.

作者貢獻聲明：陳淑平提出研究思路，設計算法、實驗，分析實驗數據并撰寫論文；尉紅梅指導算法及完善實驗方案；王飛、李祎負責算法實現、測試數據的整理與分析；何王全、漆鋒濱提出研究課題，把握論文創新性，并對論文進行修改.