一種面向大規(guī)模并發(fā)的Gatherv優(yōu)化方法*

孫浩男,王 飛,魏 迪,尹萬旺,史俊達

(1.國家并行計算機工程技術(shù)研究中心，北京 100080；2.清華大學計算機科學與技術(shù)系，北京 100084)

1 引言

科學與工程計算領(lǐng)域中并行應(yīng)用對計算能力的需求使得高性能計算系統(tǒng)的規(guī)模日益增大。通常情況下，并行應(yīng)用將數(shù)據(jù)存儲于本地內(nèi)存進行計算，并通過消息傳遞接口按照一定的規(guī)則進行交互。通用消息傳遞接口MPI(Message Passing Interface)成為交互的標準。MPI定義了多種集合通信標準，如Gather、Scatter和Alltoall。這些標準接口支持指定進程范圍內(nèi)的規(guī)則數(shù)據(jù)通信，即參與集合通信的進程發(fā)送或接收的數(shù)據(jù)量相同，且數(shù)據(jù)存儲的位置連續(xù)。為了不失靈活性，對于Gather、Scatter和Alltoall，MPI標準還支持了上述操作的不規(guī)則版本，即參與集合通信的進程發(fā)送或接收的數(shù)據(jù)量不相同，且最終數(shù)據(jù)存儲的位置可以不連續(xù)。

MPI不規(guī)則集合通信是在大規(guī)模并行應(yīng)用中常用的通信手段。Laguna等[1]對高性能計算領(lǐng)域數(shù)百個開源應(yīng)用的調(diào)研表明，不規(guī)則集合通信的使用十分廣泛，其中超過30%的應(yīng)用使用了Gatherv功能。在編碼解碼、深度學習和矩陣運算等[2 - 5]方向的研究工作中，Allgatherv或Gatherv不規(guī)則集合通信具有廣泛的應(yīng)用需求。

2 背景

Gatherv作為Gather的不規(guī)則版本，擴展之處在于：根進程可從不同的進程接收不同長度的消息，同時將收到的消息數(shù)據(jù)存放到緩沖區(qū)的任意位置。然而，不規(guī)則集合通信在為并行應(yīng)用設(shè)計帶來了極大的靈活性，提升了MPI標準描述能力的同時，也為MPI集合通信在大規(guī)模環(huán)境下的實現(xiàn)帶來了較大的挑戰(zhàn)。

2.1 Linear結(jié)構(gòu)

Linear結(jié)構(gòu)是Gatherv最為直觀、簡單的實現(xiàn)方式，如圖1所示，根節(jié)點以串行方式逐次與其他節(jié)點進行交互。MPICH[6]和OpenMPI[7]作為主流MPI實現(xiàn)方式，均采用傳統(tǒng)Linear結(jié)構(gòu)實現(xiàn)Gatherv。但是，當節(jié)點數(shù)為n時，其時間復雜度為O(n),由此帶來了嚴重的可擴展性問題。隨著進程規(guī)模的增大，根進程root需要和其他進程建立大量連接通路，需要同時處理來自其他n-1個節(jié)點的通信請求，這使得連接通路產(chǎn)生的內(nèi)存開銷隨之陡增，且通信熱點問題顯著，難以支撐大規(guī)模并發(fā)應(yīng)用的不規(guī)則通信需求。

Figure 1 Structure of Linear圖1 Linear結(jié)構(gòu)

2.2 Binomial-Tree結(jié)構(gòu)

Binomial-Tree結(jié)構(gòu)如圖2所示，是一種二項式模型。當進程數(shù)為m時，根節(jié)點的通信連接數(shù)控制在lb (m)，其余進程逐級承擔通信任務(wù)，通信過程在各層級間有序異步并發(fā)，可以有效緩解Linear結(jié)構(gòu)中根進程連接通路內(nèi)存開銷大、通信熱點顯著的問題。目前，Binomial-Tree結(jié)構(gòu)廣泛應(yīng)用于諸如Bcast、Gather、Scatter和Reduce等規(guī)則集合通信實現(xiàn)。

Figure 2 Structure of Binomial-Tree圖2 Binomial-Tree結(jié)構(gòu)

2.3 相關(guān)研究

在不規(guī)則集合通信的相關(guān)研究方面，Kang等[8]重點討論了通信拓撲結(jié)構(gòu)上的優(yōu)化;Mallón等[9]通過在預處理階段使用Gather替代Gatherv的方式優(yōu)化圖像合成應(yīng)用的性能；Ascension等[10]基于Gatherv數(shù)據(jù)分塊進行改進，以提高大型陣列計算應(yīng)用的性能;Jocksch等[11]著重于不規(guī)則集合通信算法的選擇與組合，此類研究有一定的參考意義，但對物理環(huán)境和應(yīng)用類型有一定的局限性。在Gatherv算法模型的相關(guān)研究上，Pje?ivac- Grbovic[12]和Nuriyev等[13]均詳細對比分析了Binomial-Tree結(jié)構(gòu)相對于Linear結(jié)構(gòu)在Gather上的應(yīng)用優(yōu)勢；Traff[14,15]討論了MPI不規(guī)則集合通信建模方法， 對基于Binomial-Tree結(jié)構(gòu)建模的Scatterv和Gatherv進行了深入的理論研究，為Gatherv基于Binomial-Tree結(jié)構(gòu)的高性能實現(xiàn)提供了理論支撐。

Binomial-Tree結(jié)構(gòu)在降低通信通路內(nèi)存開銷和提升通信并發(fā)度方面，相對于Linear結(jié)構(gòu)具有無可比擬的優(yōu)勢。但是，將其應(yīng)用于不規(guī)則集合通信實現(xiàn)，將面臨如下挑戰(zhàn)：(1)接收數(shù)據(jù)量和偏移僅對根進程有效，其他進程無法掌握全局信息，導致根節(jié)點外的其他中間節(jié)點無法掌握本子樹內(nèi)的通信細節(jié)，因此無法實現(xiàn)通信緩沖區(qū)的精細化管理；(2)該模型結(jié)構(gòu)涉及多個層次的消息通信，大規(guī)模并發(fā)條件下建立通信關(guān)系存在一定的計算開銷；(3)由于消息目的地址可能不連續(xù)，根進程在處理消息偏移過程中可能存在頻繁的拷貝操作。

針對上述挑戰(zhàn)，本文對MPI不規(guī)則集合通信Gatherv進行了深入分析，從優(yōu)化等級、臨時緩沖區(qū)管理等方面，解決了不規(guī)則特性帶來的優(yōu)化難題，將Binomial-Tree結(jié)構(gòu)應(yīng)用于Gatherv實現(xiàn)；并進一步提出消息鏈調(diào)度機制，提升Gatherv在大規(guī)模環(huán)境下的性能。

3 基于Binomial-Tree的Gatherv實現(xiàn)

3.1 基于等級劃分的優(yōu)化策略

在MPI文本定義[16]中，Gatherv部分參數(shù),如消息長度recvcounts、偏移displs屬性,僅對根進程有效，使得其它進程在無法獲取全局信息的情況下難以建立Binomial-Tree結(jié)構(gòu)中的節(jié)點映射關(guān)系。為此，本文提出2種優(yōu)化等級：符合文本定義的保守優(yōu)化等級和充分挖掘性能潛力的激進優(yōu)化等級。

(1)保守優(yōu)化等級：由根進程通過廣播操作將recvcounts、displs及算法決策發(fā)送給其他進程，使所有進程都可以掌握全局信息。該方式符合文本定義，作為保守優(yōu)化等級。

(2)激進優(yōu)化等級：保守優(yōu)化等級嚴格遵守文本定義，但帶來了一定的廣播開銷。在使用Gatherv的實際并行應(yīng)用中，各進程常共享全局信息，因此本文在不規(guī)則屬性對所有進程都有效、可見的條件下省略廣播操作，作為Gatherv激進優(yōu)化等級。

2種優(yōu)化等級都能夠令所有進程掌握全局信息，為構(gòu)建Binomial-Tree結(jié)構(gòu)提供先決條件。

3.2 模型結(jié)構(gòu)

建立Gatherv的模型結(jié)構(gòu)：首先根據(jù)式(1)，由各進程的進程號rank相對于根進程的進程號root計算相對進程號relative_rank:

relative_rank=(rank-root+nt)%n

(1)

其中,nt為通信域進程數(shù)。根據(jù)relative_rank建立進程到節(jié)點的映射關(guān)系，將各進程映射為葉節(jié)點、中間節(jié)點和根節(jié)點，構(gòu)成Binomial-Tree。主要模型結(jié)構(gòu)如圖3所示，由各葉節(jié)點發(fā)送消息至其中間節(jié)點，根節(jié)點和各中間節(jié)點接收子樹節(jié)點消息并存入各自臨時緩沖區(qū)tmp_buf，經(jīng)過多輪的消息收集和轉(zhuǎn)發(fā)，最終將所有節(jié)點消息匯集至根節(jié)點。

該模型結(jié)構(gòu)不僅能消除根進程通信熱點問題，充分利用網(wǎng)絡(luò)帶寬，還能夠節(jié)省大量因建立連接通路而占用的內(nèi)存空間，對于進程數(shù)為nt的通信域，根節(jié)點所需建立的連接通路個數(shù)為lb(nt)，對比Linear結(jié)構(gòu)的n-1個連接通路，內(nèi)存開銷大大降低。

Figure 3 Structure of Gatherv model圖3 Gatherv模型結(jié)構(gòu)

3.3 消息規(guī)則3.3.1 消息源計算

Gatherv支持進程消息長度各異的特性，為模型中臨時緩沖區(qū)管理帶來了難度：(1)為控制內(nèi)存開銷、按需分配緩沖區(qū)空間，需要設(shè)計算法令根節(jié)點和中間節(jié)點計算出其子樹中所有節(jié)點進程號src(作為消息源)，從而根據(jù)進程號src計算得出所需空間大小；(2)多層次的通信過程也需要計算消息源以建立通信關(guān)系，冗雜的計算過程帶了一定的成本。

為此，本文設(shè)計了消息源列表計算算法。如算法1所示，根節(jié)點和中間節(jié)點計算出當前迭代mask下的直接消息源src，再分別計算出以直接消息源src作為中間節(jié)點的子樹中節(jié)點個數(shù)recvblks；根節(jié)點和中間節(jié)點分別根據(jù)式(2)和式(3)計算每輪通信中消息源節(jié)點個數(shù)recvblks;經(jīng)消息輪數(shù)mask和每輪通信中消息源節(jié)點個數(shù)recvblks的迭代逐個計算出所有消息源并寫入src_list列表，完成根節(jié)點和中間節(jié)點消息源列表src_list的建立。可以看到，src_list一方面用于計算臨時緩沖區(qū)大小，為進程按需分配空間,以控制內(nèi)存開銷；另一方面用于計算消息收發(fā)過程中的消息長度，以“一次計算，多次使用”的方式控制計算成本。

(2)

(3)

算法1Calculatesrc_list

Input:relative_rank,nt。

Output:src_list。

1mask←1;

2num←0;

3whilemask

4ifmask&relative_rank=0then

5src←relative_rank|mask;

6ifrank=rootthen

7 Calculaterecvblksaccording to formula (2);

8else

9 Calculaterecvblksaccording to formula (3);

10end

11forx←0 torecvblksdo

12src_list[num]←(src+x+nt)%nt;

13num++;

14end

15else

16break;

17end

18mask?1;

19end

Figure 4 Instant copy圖4 即時拷貝

此外，該模型結(jié)構(gòu)需要為根節(jié)點和中間節(jié)點分配臨時緩沖區(qū)tmp_buf以暫存消息，為節(jié)省內(nèi)存采取按需分配空間的方式。分配規(guī)則如下所示：(1)中間節(jié)點分配的臨時緩沖區(qū)大小為所需接收的所有子節(jié)點的消息長度總和；(2)根節(jié)點分配的臨時緩沖區(qū)大小為除根節(jié)點及其直接葉節(jié)點外的所有節(jié)點的消息長度總和。

3.3.2 消息收發(fā)規(guī)則

如圖4所示，模型中消息收發(fā)規(guī)則如下所示：(1)葉節(jié)點：在第1輪通信中(step 1)直接將消息發(fā)給中間節(jié)點。(2)中間節(jié)點：將自身消息從本地拷貝至臨時緩沖區(qū)tmp_buf，逐輪接收子節(jié)點消息至臨時緩沖區(qū)tmp_buf，最終將tmp_buf發(fā)給中間節(jié)點。中間節(jié)點根據(jù)模型結(jié)構(gòu)分布，有若干次接收操作和一次發(fā)送操作。(3)根節(jié)點：預先(step 0)將自身消息由sendbuf本地拷貝至recvbuf對應(yīng)位置disp[root]；再將直接葉節(jié)點在第1輪通信中(step 1)直接接收至recvbuf對應(yīng)的位置(參考disp屬性)；來自中間節(jié)點的消息逐輪接收至臨時緩沖區(qū)tmp_buf。

由圖中可知，根節(jié)點臨時緩沖區(qū)在每輪接收消息后，結(jié)合消息源列表src_list和不規(guī)則屬性即時將臨時緩沖區(qū)消息拷貝至recvbuf，以通信和拷貝輪轉(zhuǎn)進行的方式，避免了根節(jié)點前期通信密集、后期拷貝密集而造成的網(wǎng)絡(luò)擁塞和讀寫繁忙。此處拷貝方式和次數(shù)對性能影響較大，將在第3節(jié)詳細介紹關(guān)于消息鏈調(diào)度的優(yōu)化機制。

4 基于消息鏈調(diào)度的性能優(yōu)化機制

根節(jié)點逐個將每條消息按不規(guī)則屬性從臨時緩沖區(qū)拷貝至recvbuf的過程帶來了巨大開銷。如圖3和圖4所示，根節(jié)點除了其葉節(jié)點消息直接發(fā)送至recvbuf外，其余所有消息都需從本地拷貝，且拷貝的次數(shù)隨消息輪數(shù)的增加呈指數(shù)級增長，當消息長度較大時，拷貝帶寬受限，可以預見優(yōu)化效果并不理想。因此結(jié)合應(yīng)用特點，盡量將消息直接寫入用戶地址空間，以減少拷貝次數(shù)，這是提高Gatherv性能的有效途徑。

4.1 消息鏈初始化

假設(shè)在每輪由中間節(jié)點發(fā)送至根節(jié)點的消息集中，將中間節(jié)點臨時緩沖區(qū)內(nèi)相鄰的消息相對劃分為前置消息pre_msg和當前消息cur_msg，其對應(yīng)消息源稱為pre_src和cur_src，則2條消息連續(xù)的條件如式(4)所示：

recvcounts[pre_src]*recvtype_size=

displs[cur_src]*datatype_size

(4)

當式(4)成立時，中間節(jié)點臨時緩沖區(qū)中相鄰消息在根節(jié)點recvbuf中的接收位置也相鄰，則定義2個相鄰消息為連續(xù)消息，否則為非連續(xù)消息。

對于使用Gatherv的大規(guī)模并行應(yīng)用，盡量將符合連續(xù)條件的通信過程合并成消息鏈，由根節(jié)點直接接收消息鏈至recvbuf，以減少本地拷貝操作，進一步提升性能。需要說明的是，根節(jié)點在每輪通信中從不同子樹接收消息，因此每輪通信之間的消息是否連續(xù)并不影響根節(jié)點行為。構(gòu)建消息鏈的工作主要集中在中間節(jié)點向根節(jié)點發(fā)送消息集的內(nèi)部。

首先基于消息源列表src_list獲取消息集內(nèi)每個消息的長度和偏移屬性，并以第1個消息為起點構(gòu)建消息鏈。如圖5所示，依據(jù)式(4)以第1個消息(msg4)為消息鏈起點，當?shù)?個消息(msg5)與第1個消息的目的空間連續(xù)時，則初始化消息鏈為連續(xù)消息鏈，否則為非連續(xù)消息鏈。

Figure 5 Construction of message chain圖5 消息鏈構(gòu)建

4.2 連續(xù)消息調(diào)度

此后，每個當前消息cur_msg都與前置消息pre_msg以式(4)為依據(jù)進行連續(xù)性匹配，從而進行消息鏈擴展或重構(gòu)。如圖6所示，當前消息與前置消息連續(xù)，則需查看前置消息pre_msg所在消息鏈是否為連續(xù)消息鏈：

(1)對于連續(xù)消息鏈，則將當前消息cur_msg連接在前置消息pre_msg后，擴展該消息鏈。

(2)對于非連續(xù)消息鏈，則將前置消息pre_msg之前的消息鏈(不包括pre_msg)執(zhí)行接收/發(fā)送操作，根節(jié)點通過臨時緩沖區(qū)接收非連續(xù)消息鏈，進行“一次接收，逐個拷貝”操作，將各消息拷貝至recvbuf相應(yīng)位置。隨后中間節(jié)點以前置消息pre_msg作為起點，將當前消息cur_msg連接在pre_msg后，構(gòu)成連續(xù)消息鏈。

Figure 6 Scheduling of continuous message圖6 連續(xù)消息調(diào)度

4.3 非連續(xù)消息調(diào)度

如圖7所示，當前消息與前置消息不連續(xù)時，也需根據(jù)前置消息pre_msg所在的消息鏈類型進行處理：

(1)對于非連續(xù)消息鏈，則將當前消息cur_msg連接在前置消息pre_msg后，擴展該非連續(xù)消息鏈。非連續(xù)鏈的構(gòu)建和擴展目的在于最大程度地將非連續(xù)消息鏈合并發(fā)送至根節(jié)點，雖無法避免根節(jié)點在接收到非連續(xù)消息鏈后的拷貝開銷，但能夠有效減少通信次數(shù)，減輕網(wǎng)絡(luò)壓力。

(2)對于連續(xù)消息鏈，則根據(jù)“連續(xù)消息最大化直接接收”的原則，將前置消息pre_msg擴展至連續(xù)消息鏈，再令連續(xù)消息鏈執(zhí)行接收/發(fā)送操作，根節(jié)點直接將連續(xù)消息鏈接收至recvbuf。隨后以當前消息cur_msg為起點重構(gòu)消息鏈。

Figure 7 Scheduling of discontinuous message圖7 非連續(xù)消息調(diào)度

在每輪通信處理完最后一個消息后，將連續(xù)/非連續(xù)消息鏈發(fā)出，根節(jié)點依據(jù)消息鏈類型進行接收。由此，通過消息鏈調(diào)度機制，根節(jié)點能夠最大程度地由recvbuf直接接收連續(xù)消息，避免對連續(xù)消息進行拷貝，減少了開銷；對非連續(xù)消息也能實現(xiàn)“一次接收，逐個拷貝”，減輕了網(wǎng)絡(luò)壓力。

5 測試與分析

本文在神威高性能計算系統(tǒng)上實現(xiàn)了Gatherv優(yōu)化方法，并以神威高性能計算系統(tǒng)為目標平臺，使用自編micro-benchmark及標準測試程序IMB(Intel MPI Benchmark)，分別對本文優(yōu)化方法的內(nèi)存開銷及Gatherv通信性能進行了測試，并和Gather規(guī)則通信的性能進行了對比。

5.1 內(nèi)存開銷測試

通信過程中，通信雙方需要通過上下文來支持連接通路，連接通路的數(shù)量將決定通信支撐環(huán)境的內(nèi)存開銷。本文采用自編micro-benchmark，通過通信過程結(jié)束前后的可用內(nèi)存差值來計算通信過程中構(gòu)建通信連接通路所產(chǎn)生的內(nèi)存開銷。本節(jié)對比了Linear結(jié)構(gòu)實現(xiàn)和本文優(yōu)化實現(xiàn)的Gatherv在構(gòu)建連接通路方面的內(nèi)存開銷情況。如圖8所示，32 768個進程規(guī)模下Linear結(jié)構(gòu)產(chǎn)生了約1 312.12 MB內(nèi)存開銷，而本文基于Binomial-Tree結(jié)構(gòu)將內(nèi)存開銷控制在較低水平(僅約0.60 MB)；其他進程規(guī)模下，本文優(yōu)化實現(xiàn)方法(保守優(yōu)化與激進優(yōu)化內(nèi)存開銷一致)的內(nèi)存開銷為Linear結(jié)構(gòu)的lbn/(n-1)，優(yōu)化效果符合預期。通過上述測試數(shù)據(jù)不難發(fā)現(xiàn)，本文優(yōu)化方法可以以極低的內(nèi)存開銷高效支持用戶在大規(guī)模并發(fā)條件下的Gatherv不規(guī)則集合通信。

Figure 8 Comparision of Gatherv memory overhead圖8 Gatherv內(nèi)存開銷對比

5.2 通信性能對比測試

本節(jié)使用標準測試程序IMB對MPICH基于Linear結(jié)構(gòu)實現(xiàn)的Gatherv與本文保守優(yōu)化實現(xiàn)的Gatherv通信性能進行了對比測試。如表1、表2、圖9和圖10所示，相對于Linear結(jié)構(gòu)實現(xiàn)，Gatherv保守優(yōu)化實現(xiàn)有大幅的性能提升，且優(yōu)化效果隨進程規(guī)模增大而增強，在消息長度為8 B、進程規(guī)模為32 768時加速比達到41 068；在消息長度為8 KB、進程規(guī)模為32 768時，加速比達到32 709。另外，數(shù)據(jù)顯示Linear結(jié)構(gòu)下的短消息(8 B)開銷比長消息(8 KB)開銷更大，原因為短消息采用的Eager協(xié)議需要接收端進行用戶數(shù)據(jù)的拷貝操作，而長消息采用Rendezvous協(xié)議，數(shù)據(jù)由發(fā)送端通過遠程直接內(nèi)存訪問RDMA(Remote Direct Memory Access)寫操作寫入接收端目的地址。因此，短消息協(xié)議下Linear結(jié)構(gòu)根節(jié)點的拷貝壓力更大，熱點效應(yīng)更明顯。

Table 1 Effect of Gatherv conservative optimization when message length is 8 B

Table 2 Effect of Gatherv conservative optimization when message length is 8 KB表2 消息長度為8 KB時的Gatherv保守優(yōu)化效果

Figure 9 Gatherv overhead when message length is 8 B圖9 消息長度為8 B時的Gatherv開銷

Figure 10 Gatherv overhead when message length is 8 KB圖10 消息長度為8 KB時的Gatherv開銷

對比測試表明，本文提出的優(yōu)化方法在模型結(jié)構(gòu)上具備一定的優(yōu)越性，同時消息鏈調(diào)度機制能夠有效控制拷貝開銷，相較于傳統(tǒng)Linear方法具有明顯優(yōu)勢。

5.3 性能擴展性測試

本節(jié)對2種Gatherv優(yōu)化實現(xiàn)和基于Binomial-Tree結(jié)構(gòu)實現(xiàn)的Gather進行性能對比測試，以驗證本文優(yōu)化方法可以有效擴展至大規(guī)模并發(fā)情況。測試使用標準測試程序IMB，分別測試8 B短消息和8 KB長消息的Gatherv及Gather開銷。圖11和圖12的測試結(jié)果表明：(1)Gatherv保守優(yōu)化和激進優(yōu)化實現(xiàn)的開銷在進程規(guī)模2倍遞增時均實現(xiàn)了小于2倍的增長，具有良好的性能可擴展性。(2)Gatherv保守優(yōu)化與激進優(yōu)化實現(xiàn)之間存在略微的性能差距，主要來自于預處理階段對recvcounts、displs及算法決策信息的廣播開銷。(3)激進優(yōu)化實現(xiàn)的Gatherv性能，和基于Binomial-Tree結(jié)構(gòu)實現(xiàn)的Gather性能相比，基本處于同一數(shù)量級，只存在局部差異。消息長度較短(8 B)時，激進優(yōu)化實現(xiàn)的Gatherv開銷略高于Gather的。原因為：通信開銷相對較小，此時構(gòu)建src_list和消息鏈的額外開銷在整體開銷中占比相對較大，因此導致整體開銷略大。消息長度較長(8 KB)時，激進優(yōu)化實現(xiàn)的Gatherv開銷略低于Gather的原因為：通信開銷在整體開銷中的占比較大，一定程度上弱化了激進優(yōu)化實現(xiàn)的額外開銷的影響，且由于激進優(yōu)化實現(xiàn)在通信過程中直接使用預先構(gòu)建的src_list和消息鏈，而基于Binomial- Tree結(jié)構(gòu)實現(xiàn)的Gather采用“邊通信邊計算對象”的模式，因此，激進優(yōu)化的Gatherv實現(xiàn)帶寬利用率略好。需要說明的是，構(gòu)建src_list和消息鏈的額外開銷會隨著進程數(shù)的增加而增大，當進程數(shù)增加到一定程度且消息長度不變時，會使激進優(yōu)化實現(xiàn)中的上述額外開銷的影響逐漸顯現(xiàn)。圖12中當進程規(guī)模增大至32 768時，就出現(xiàn)了激進優(yōu)化實現(xiàn)的Gatherv開銷略高于Gather開銷的現(xiàn)象。但是，如果消息長度增加，可以預見額外開銷對于激進優(yōu)化實現(xiàn)的性能影響將進一步被弱化，激進優(yōu)化實現(xiàn)的Gatherv開銷仍將低于基于Binomial-Tree結(jié)構(gòu)實現(xiàn)的Gather的。

Figure 11 Gatherv/Gather overhead when message length is 8 B圖11 消息長度為8 B時的Gatherv/Gather開銷

Figure 12 Gatherv/Gather overhead when message length is 8 KB圖12 消息長度為8 KB時的Gatherv/Gather開銷

6 結(jié)束語

本文針對當前MPI不規(guī)則化集合通信Gatherv實現(xiàn)方法存在的通信熱點突出、內(nèi)存開銷大和訪存效率低等問題，提出了一種面向大規(guī)模并發(fā)的Gatherv優(yōu)化方法。從優(yōu)化等級、臨時緩沖區(qū)管理等方面出發(fā)，研究高效均衡、內(nèi)存開銷可控的優(yōu)化措施，將Binomial-Tree結(jié)構(gòu)成功應(yīng)用于Gatherv的實現(xiàn)，并基于此設(shè)計了消息鏈調(diào)度機制，有效限制根進程拷貝開銷，進一步提升了Gatherv性能，對MPI不規(guī)則集合通信的優(yōu)化工作有一定的參考意義。測試結(jié)果表明，本文方法可以有效解決現(xiàn)有方法存在的缺陷，相對于Linear結(jié)構(gòu)，在內(nèi)存開銷和通信性能方面均有顯著改進，可以有效保證Gatherv不規(guī)則集合通信在大規(guī)模并發(fā)條件下的高效可擴展性。