基于天河互連MPI聚合通信歸約操作卸載優化 *

王 浩，張 偉，謝 旻，董 勇

(國防科技大學計算機學院，湖南 長沙 410073)

1 引言

在高性能計算領域，聚合通信在并行科學計算應用中扮演著非常重要的角色，許多并行應用程序使用聚合通信來滿足一系列的通信請求，例如迭代數值求解器中剩余向量的大小、執行分布式數據歸約、傅里葉變換。在許多基于MPI(Message Passing Interface)消息傳遞編程模型的并行科學計算應用中聚合通信占據大部分的通信時間消耗，對應用的運行性能和可擴展性有重要影響，并且影響程度隨著應用規模的增加而增大[1]。MPI聚合通信接口中的歸約操作MPI_Reduce和MPI_Allreduce被廣泛應用于科學計算應用中，迭代求解器(如共軛梯度等)是許多科學模擬應用的重要組成部分，在每一次迭代過程中均使用多次歸約來計算點積或范數[2]。Reduce操作是將所有進程提供的值進行歸約計算后將計算結果發送到一個目的進程，Allreduce操作則是將歸約計算結果發回所有進程。有研究表明，在一些MPI并行應用中，有超過40%的時間消耗在歸約操作上[3]。一些科學應用程序和基準測試例如大規模原子分子并行模擬器[4]、Fluent[5]、OpenFOAM[6]在MPI_Allreduce操作上消耗的時間占比總的通信時間超過50%[7]。在當前軟件層聚合通信實現中，Reduce操作的算法使用基于樹形結構的歸約算法實現，Allreduce操作的算法則是通過基于樹形結構的歸約/廣播算法，或者是遞歸倍增算法實現[8]。Reduce和Allreduce操作的算法通常基于點對點通信操作實現，使用網絡接口來執行結點間的消息通信，以及結點上的CPU來進行歸約計算，可能受到操作系統噪聲的影響[9,10]；而且當系統規模增大時，通信的計算步驟、計算量、進程距離將會相應增大，消息傳輸延遲帶來很大的時間開銷，且隨著系統規模增加，這種時間開銷增加是迅速的，使得軟件實現的聚合通信可擴展性較差。

天河互連網絡是國防科技大學自主研制的高性能計算機互連通信網絡，由網絡接口和互連交換2種專用芯片構成。網絡接口在結點之間提供數據通信服務，互連交換芯片用于構造多種互連拓撲的交換網絡架構。網絡接口芯片支持PCIe 3.0x16接口，支持用戶級通信來減少軟件層開銷，提供無連接模式的RDMA和短報文傳輸操作，并通過非阻塞通信模式來實現計算通信重疊執行[11 - 13]。互連交換芯片采用高階路由結構降低互連網絡跳步數，從而提高互連拓撲網絡的帶寬、可靠性和靈活性。面向聚合通信操作的性能優化和可擴展性問題，天河互連網絡接口中設計了一種基于觸發的通信卸載機制，其核心思想是將一些聚合通信操作卸載到互連網絡中自主觸發執行，減少主機處理器對聚合通信中數據通信過程的介入，實現計算與通信重疊執行，優化聚合通信的延遲和帶寬。并且互連網絡接口中還實現了計算邏輯部件，可以支持歸約操作中的各種計算操作，從而消除聚合通信過程中將數據傳輸到主機處理器進行運算的過程，優化聚合通信的延遲。

目前已有一些針對聚合通信操作優化的研究工作，例如IBM的BG/L[14]集成有專門用來支持聚合通信操作的專用網絡硬件，其功能專有，硬件復雜度高。Myrinet[15]網絡接口包含嵌入處理器，支持特定聚合通信操作的卸載，但更新集合操作時需要更改網絡接口上運行的控制程序。Mellanox開發的SHArP協議[16]在物理拓撲的基礎上建立邏輯聚合通信樹形結構，其設計的網絡接口芯片與互連交換芯片硬件都具備數據聚合處理能力，共同構成邏輯樹中的聚合結點，消息通信效率高，延遲低，但網絡接口芯片與互連交換芯片硬件復雜度高，且要求構建的邏輯通信樹與物理拓撲基本對應；類似的基于觸發的通信卸載機制有可編程的網絡接口API——Portals 4.0[17]，在網絡接口加入Portals單元和DMA引擎來卸載聚合通信，但其加入的部件較多，增加了網絡接口的硬件復雜性，且網絡接口控制這些部件運行的程序存在額外開銷；Fujistu設計的片上系統互連結構Tofu-2[18]，處理器芯片上集成了Tofu網絡接口和Tofu同步接口，結點間采用會話模式的控制報文觸發進行聚合通信操作的卸載，與天河互連網絡通信卸載實現機制較為相似。不同的是天河互連網絡僅在獨立的網絡接口芯片加入簡單的硬件觸發邏輯就能實現卸載功能，構造的通信卸載樹形結構與物理拓撲獨立，可靈活實現于多種拓撲結構中。

本文利用天河互連網絡的觸發操作特性，設計實現了歸約操作的聚合通信卸載算法，并通過實驗評估了基于不同樹形結構的Allreduce和Reduce通信卸載算法的性能。

2 天河互連網絡通信卸載技術

天河互連網絡在網絡接口中實現了虛擬端口(Virtual Port)的機制，這種機制支持硬件資源的虛擬化來靈活實現用戶級通信，它為每個進程提供了獨占使用通信硬件的編程視角[13]。當多個進程并發運行時，來自不同進程的通信操作相互獨立，彼此不會產生干擾。每個虛擬端口是一組內存映射寄存器和一組相關的內存數據結構的組合，不同虛擬端口中的寄存器地址范圍的間隔至少與物理頁的長度相同。所有這些地址范圍都可以映射到用戶空間，這樣就可以在用戶空間中進行受保護的并發訪問，過程如圖1所示。

Figure 1 Process diagram of virtual ports realize user level communication圖1 虛擬端口實現用戶通信過程

內存數據結構包括：(1)通信請求描述符隊列DQ(Descriptor Queue)，是物理地址連續的內存緩沖區。用戶可以在DQ中構建一個通信請求，互連網絡接口通過DQ來接受用戶提交的通信操作請求，然后通知網絡接口用DMA(Direct Memory Access)方式讀取描述符到網絡接口中并執行通信操作。用戶還可以通過PIO(Programming Input/Output model)方式直接提交通信請求到網絡接口的內部描述符隊列中，但網絡接口中的DQ的容量是有限的。(2)MP報文接收隊列MPQ(Mini-Packet Queue)，一種用于雙向通信的短報文機制。Mini-Packet以下簡稱MP報文，每個MP報文是128 B，其中前8 B是報文頭，其余則是有效負載。網絡接口向MPQ中順序存儲其它虛擬端口發送到本端口的MP報文，但MPQ的容量是有限的，如果MPQ滿了，新到達的MP報文將被丟棄，因此必須有一個軟件層協議來防止MPQ溢出。通常，MPQ也是在物理地址連續的內存中分配的，但也可以使用虛擬地址方式，利用網絡接口中的地址轉換表映射到用戶空間。(3)事件狀態隊列EQ(Event Queue)，互連網絡接口在其中記錄用戶提交的RDMA通信請求的執行狀態，事件內容可以由用戶控制。用戶在初始化時可以對這些資源大小進行配置，對這些資源的訪問操作是直接在用戶地址空間上進行的。

為了加速聚合通信的執行，互連網絡接口芯片基于現有的通信機制，設計實現了一種軟硬件結合的觸發機制，來進行聚合通信的通信卸載處理。在網絡接口中加入一種特殊的硬件觸發邏輯部件，該部件在滿足觸發條件時自動執行數據的復制、替換、接收或發送，不需要處理器的參與。用戶設置一組通信請求描述符序列，在描述符序列頭部定義對通信請求的控制操作，比如觸發控制條件值、報文數據復制或替換的選項等。描述符序列被提交到虛擬端口中后，并不會立即執行，需要等待觸發條件。在進行聚合通信操作時，當從網絡接口接收到的數據報文設定了描述符序列的觸發條件時，觸發邏輯部件將會自動執行描述符序列，并根據描述符序列的設置選項完成復制、替換或轉發等操作。這種觸發機制由控制報文CP(Control Packet)處理，互連端口中有控制報文的計數器(CP Counter)，當網絡接口接收到新的CP時，CP Counter計數加一，當達到計數閾值時，就立即觸發描述符序列的執行，結點的觸發原理如圖2所示。

Figure 2 Schematic diagram of node trigger principle圖2 結點觸發原理示意圖

該機制有多種優勢：邏輯設計簡單；可以構造多種樹形拓撲結構的通信卸載算法，算法構造的拓撲與物理拓撲不一定完全對應，靈活性好；處理器不參與數據傳輸，受到系統噪聲影響較小；數據傳輸由硬件自動完成，在結點規模增加時延遲增幅較小，可擴展性好；消息在網絡接口中自行復制，減少跨PCIe的數據傳輸。為了支持歸約操作，網絡接口還加入了計算邏輯單元ALU，硬件支持最多同時對7個歸約數據進行歸約計算，可供支持的歸約操作有浮點/整型求和、最大值、最小值，邏輯/位與、或、異或操作，通過計算卸載操作來進一步提高歸約操作的通信性能。

3 基于觸發機制的Reduce/Allreduce通信卸載算法

3.1 K-nomial與K-ary樹形結構

Figure 3 2-nomial tree and 4-nomial tree for 16 nodes圖3 16結點的2-nomial樹和4-nomial樹

Figure 4 2-ary tree and 4-ary tree for 16 nodes圖4 16結點的2-ary樹和4-ary樹

以上構造樹中的結點分為根結點(Root Node)、葉結點(Leaf Node)和中間結點(Inner Node) 3類，根結點最上層的1個結點；葉結點每條分支中最下層的結點；其余結點是中間結點。樹中的邊表示為父子關系，隸屬于同一父結點的同一層子結點互為兄弟關系。結點間的通信只在父子結點之間進行，但每個結點上的通信操作則根據結點類型和子結點個數，而有所不同。

3.2 基于觸發機制的Allreduce通信卸載算法

基于樹形結構通信，不同類型的結點執行不同的通信原語操作。Allreduce的通信卸載算法如算法1所示。

算法1基于觸發機制的Allreduce通信卸載算法

(1)根結點：①準備1個待觸發的MP歸約數據報文，目的地址為本結點，觸發計數器值為子結點數目，觸發條件為接收到所有子結點帶有觸發標志的歸約數據報文；并將歸約計算結果替換為報文數據發送到本結點的報文接收隊列。

②準備1個待觸發的MP歸約結果數據報文序列，目的地址為所有子結點，觸發計數器值為1，觸發條件為接收到發送給本結點的歸約計算結果報文；等待接收歸約計算結果，并將接收到的數據替換為報文序列中的數據，發送到所有子結點的報文接收隊列。

(2)中間結點：①準備1個待觸發的MP歸約數據報文，目的地址為父結點，觸發計數器值為子結點數目，觸發條件為接收到所有子結點帶有觸發標志的歸約數據報文；并將歸約計算結果替換為報文數據發送給父結點。

②準備1個待觸發的MP歸約結果數據報文序列，目的地址為所有子結點，觸發計數器值為1，觸發條件為接收到來自父結點的歸約計算結果報文；等待接收歸約計算結果，并將接收到的數據替換為報文序列中的數據，發送到所有子結點的報文接收隊列。

(3)葉結點：準備1個MP歸約數據報文，目的地址為父結點，立即發送給父結點；等待接收歸約計算結果。

根結點和中間結點都準備2個描述符序列，一個是參與歸約計算的數據報文，一個是將歸約計算結果發給通信域中所有子節點的廣播數據報文，葉結點只準備參與歸約計算的數據報文。所有結點準備并提交報文到描述符隊列后，先由葉結點啟動通信序列發送報文并向上觸發父結點的通信序列。根結點接收到所有子結點的報文后進行歸約計算，并觸發計算結果向下廣播發送到所有子結點，直到所有的結點都接收到歸約計算結果。算法執行的具體過程如下所示：根結點將待歸約的數據打包為MP歸約報文，等待接收到所有子結點的MP歸約報文觸發執行歸約計算操作；并將歸約計算結果廣播報文發送給所有子結點，此報文的數據由自身的歸約計算結果替換，由自身MP歸約報文執行后觸發執行。中間結點承擔“向上歸約”和“向下廣播”的任務，準備2類MP交換報文，第1類是打包本結點待歸約的數據為MP歸約報文，等待接收子結點的歸約數據報文，當接收到來自所有子結點的歸約數據時，觸發執行歸約計算操作，并將歸約計算結果向上發送給父結點參與下一輪歸約計算；第2類的MP廣播數據報文是用等待接收來自父結點的計算結果報文替換報文數據，并廣播報文給所有子結點，由接收到父結點的計算結果報文觸發執行。葉結點將本結點待歸約的數據打包為MP歸約報文，準備好后立即發送給父結點參與歸約計算。所有結點準備好參與通信的報文，按照預定設置自動執行，結點各自提交所有報文的發送操作后，等待接收歸約的計算結果，接收完畢后解析歸約結果報文，將歸約計算結果存入緩沖區。

3.3 基于觸發機制的Reduce通信卸載算法

樹形結構的Reduce通信卸載算法實現過程相比Allreduce的實現，減少了向下廣播歸約計算結果的過程，最終的歸約計算結果只存在于根結點。基于觸發機制的Reduce通信卸載算法如算法2所示。

算法2基于觸發機制的Reduce通信卸載算法

(1)根結點：①準備1個待觸發的MP歸約數據報文，目的地址為本結點，觸發計數器值為子結點數目，觸發條件為接收到所有子結點帶有觸發標志的歸約數據報文；并將歸約計算結果替換為報文數據發送到本結點的報文接收隊列。

②準備1個待觸發的MP歸約結果數據報文，目的地址為本結點，觸發計數器值為1，觸發條件為接收到發給本結點帶觸發標志的歸約計算結果報文；等待接收歸約計算結果，并將接收到的數據替換為歸約結果報文中的數據，發送到本結點的報文接收隊列。

(2)中間結點：準備1個待觸發的MP歸約數據報文，目的地址為父結點，觸發計數器值為子結點數目，觸發條件為接收所有子結點帶有觸發標志的歸約數據報文，并將歸約計算結果替換為報文數據發送給父結點。

(3)葉結點：準備1個MP歸約數據報文，目的地址為父結點，立即發送給父結點。

根結點準備2個描述符，一個是參與歸約計算的報文，一個是發送歸約計算結果的報文，中間結點和葉結點只準備一個參與計算的報文。所有結點準備并提交報文到描述符隊列后，先由葉結點執行發送報文并向上觸發父結點的報文發送處理，待根結點接收到所有子結點的數據報文進行歸約計算后，觸發歸約計算結果發送到本結點的報文接收隊列。算法執行的具體過程如下：根結點準備好本結點參與歸約計算的數據報文，等待接收所有子結點參與計算的歸約MP報文，當接收到所有子結點的歸約MP報文后觸發歸約操作，執行完畢后將觸發歸約計算結果發送到本結點的報文接收隊列；中間結點準備本結點參與歸約計算的MP數據報文，等待接收來自所有子結點的歸約數據報文，接收完畢后觸發歸約計算執行，并將計算結果的數據報文向上發送給父結點；葉結點準備各自的歸約數據MP報文發送給父結點，不需要觸發立即執行。中間結點和葉結點提交完通信描述請求后即完成本結點任務，根結點提交完通信請求后，等待接收歸約結果，待完成歸約計算后，接收歸約計算結果并解析報文數據。

4 性能測試與分析

4.1 實驗測試環境

實驗測試環境為搭載天河互連網絡的超算系統，每個結點搭載1個FT-1500A/16核處理器，結點內存大小為32 GB，操作系統為Linux 4.19內核版本。

4.2 實驗過程

將實現的Allreduce和Reduce通信卸載算法部署在天河互連網絡中，參與歸約的實驗結點數量從8個增加到256個(2的冪次倍增)，每個結點上運行一個進程，每種問題規模下測試5 000次歸約操作的迭代完成時間，然后計算平均時間。單個消息大小為48 B(歸約計算同時支持6個浮點數);如果分叉度設置更大，雖通信步驟較少，但結點的通信負載較為不平衡，會影響算法性能，樹形結構分叉度K設置為2,4,8。在同等結點規模下，對基于觸發機制的Allreduce和Reduce通信卸載算法與MPICH-3.3.2版本中基于點對點實現的MPI_Allreduce和MPI_Reduce接口進行了對比測試，并對測試結果進行了詳細分析。

4.3 實驗結果與分析

4.3.1 Allreduce測試結果

Figure 5 Results comparison diagram of Allreduce offloading algorithm and MPICH implementation圖5 Allreduce通信卸載算法與MPICH對比圖

圖5所示為采用不同樹形結構的Allreduce通信卸載算法與MPICH系統中的MPI_Allreduce實現的對比測試結果，圖中橫軸為結點數量，縱軸為歸約操作的延遲，其中mpich表示MPICH的MPI_Allreduce實現算法，K-nomial和K-ary表示基于不同分叉度的K-nomial樹和K-ary樹Allreduce通信卸載算法的性能數據。從測試結果可以看出，相比于MPICH的實現，基于觸發操作實現的2種樹形結構Allreduce通信卸載算法減少了歸約操作的延遲，并且隨著結點數增加，性能提升效果越明顯。對于P(2的冪次)個結點的短消息通信，MPICH實現的通信步驟為log2P步，樹形結構Allreduce通信卸載算法的通信步驟為2 logKP步。當分叉度K=4時，兩者的通信步驟數相等。在結點數為64,128,256時，4-nomial樹形結構的Allreduce通信卸載算法的延遲時間分別為24.94 μs,31.21 μs,38.42 μs，MPICH實現的延遲時間分別為34.22 μs, 45.23 μs, 58.73 μs。為進一步探究Allreduce通信卸載算法的性能優化參數，本文對比了2種樹形結構和不同分叉度設置的測試結果。改變分叉度大小能改變通信步驟數，當K-nomial樹的的分叉度改變為2和8，結點數為16,32,64時，2-nomial樹的Allreduce通信卸載算法性能較另2種分叉度(K=4，8)更好。當結點數增加到128,256時，4-nomial樹形結構的Allreduce通信卸載算法性能更優。當結點數量較小時，分叉度較大的樹形結構 Allreduce通信卸載算法的實現性能優勢不明顯，這是因為結點數較少時通信時間較短，且通信卸載算法中父結點為多個子結點構造通信請求描述符序列時存在一定的開銷。改變樹形結構，將K-nomial樹改為K-ary樹，則K-ary樹形結構的整體性能相對于于K-nomial樹形結構有較好提升，原因在于觸發機制下的通信卸載算法中各層結點間的通信負載不同。K-ary樹形結構較對稱，各層結點的通信負載差異較小，K-nomial樹形結構各層結點間的通信負載差異較大。在文獻[11]中提到的基于SHArP的Allreduce通信卸載算法測試結果，64 B在32,64,128結點下的延遲時間分別為2.89 μs, 2.92 μs, 3.04 μs，具有更好的延遲特性，但其測試用的主機CPU和互連平臺有所不同，并且其通過專用的互連交換結點來實現數據的處理計算，硬件設計復雜度高，而天河互連僅對網絡接口芯片進行簡單的硬件擴展就能實現通信卸載的功能。

4.3.2 Reduce測試結果

圖6中比較了不同結點規模下Reduce操作的性能，同樣圖中mpich表示MPICH系統中MPI_Reduce的實現算法，K-nomial和K-ary是基于不同分叉度的K-nomial樹和K-ary樹Reduce通信卸載算法的測試結果。對于短消息通信和P(2的冪次)個結點，MPICH的MPI_Reduce接口是基于2-nomial樹形算法實現，通信步驟為log2P步，與同等通信步驟的2-nomial樹形結構Reduce通信卸載算法相比較，可以看出基于觸發操作的通信卸載算法明顯減少了歸約操作的延遲，主機處理器參與接收消息和執行歸約計算操作的軟件層開銷被消除，使得整個歸約過程中受到系統噪聲干擾的影響很少。通過改變nomial樹形結構的分叉度為4和8，來進一步探究樹形結構Reduce通信卸載算法的性能優化參數，分叉度的大小對2種樹形結構的Reduce通信卸載算法有著顯著影響，且隨著分叉度增大，通信卸載算法的優化效果更明顯。這是因為在Reduce的通信卸載實現中，通過增加分叉度降低了樹的層數，有效減少了數據的傳輸步驟。將K-nomial樹形結構改變為K-ary樹形結構，在各個結點規模下，2種樹形結構對Reduce通信卸載實現的延遲差異不大，測試結果中當結點數為128時，8-nomial樹的通信卸載實現延遲為5.61 μs，8-ary樹的通信卸載實現延遲為4.79 μs，此時延遲差最大為0.82 μs，不超過1 μs。在Reduce通信卸載算法中各結點的單次歸約執行過程是：葉結點僅將本結點參與歸約計算的數據報文發送到網絡接口即完成任務，中間結點等待接收完子結點的歸約計算報文并將計算結果向上發送給父結點后完成任務，根節點需要接收所有子結點的歸約數據并將計算結果發到本結點的報文接收隊列里，發送完報文后一直等待接收歸約計算結果并完成解析才完成任務。與Allreduce的通信卸載算法實現相比，Reduce的通信卸載算法實現不包含向下廣播數據的隱式同步過程，通信任務更為簡單，對樹形結構不敏感，性能提升更明顯。

Figure 6 Comparison diagram of Reduce communication offloaded algorithm and MPICH implementation圖6 Reduce通信卸載算法與MPICH實現對比圖

5 結束語

本文描述了面向聚合通信優化的基于觸發操作的通信卸載機制，并基于這種通信卸載機制優化了MPI接口中的Allreduce和Reduce 2種歸約操作，通過設計與實現在互連網絡硬件中自動觸發執行的樹形結構歸約算法，去優化歸約操作的性能。實驗測試評估了在天河互連網絡上，針對不同結點規模和樹形分叉度的歸約操作性能。測試結果表明，利用通信卸載實現的歸約操作，比基于點對點通信的軟件層歸約操作有更好的延遲性能和可擴展性，并且在樹形結構通信卸載算法中選用合適的分叉度能實現最優的性能。下一步工作將利用觸發操作，實現多種其它聚合通信操作卸載算法，并更好地集成到MPI實現系統中。