孫浩男,王 飛,魏 迪,尹萬(wàn)旺,史俊達(dá)
(1.國(guó)家并行計(jì)算機(jī)工程技術(shù)研究中心,北京 100080;2.清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,北京 100084)
科學(xué)與工程計(jì)算領(lǐng)域中并行應(yīng)用對(duì)計(jì)算能力的需求使得高性能計(jì)算系統(tǒng)的規(guī)模日益增大。通常情況下,并行應(yīng)用將數(shù)據(jù)存儲(chǔ)于本地內(nèi)存進(jìn)行計(jì)算,并通過(guò)消息傳遞接口按照一定的規(guī)則進(jìn)行交互。通用消息傳遞接口MPI(Message Passing Interface)成為交互的標(biāo)準(zhǔn)。MPI定義了多種集合通信標(biāo)準(zhǔn),如Gather、Scatter和Alltoall。這些標(biāo)準(zhǔn)接口支持指定進(jìn)程范圍內(nèi)的規(guī)則數(shù)據(jù)通信,即參與集合通信的進(jìn)程發(fā)送或接收的數(shù)據(jù)量相同,且數(shù)據(jù)存儲(chǔ)的位置連續(xù)。為了不失靈活性,對(duì)于Gather、Scatter和Alltoall,MPI標(biāo)準(zhǔn)還支持了上述操作的不規(guī)則版本,即參與集合通信的進(jìn)程發(fā)送或接收的數(shù)據(jù)量不相同,且最終數(shù)據(jù)存儲(chǔ)的位置可以不連續(xù)。
MPI不規(guī)則集合通信是在大規(guī)模并行應(yīng)用中常用的通信手段。Laguna等[1]對(duì)高性能計(jì)算領(lǐng)域數(shù)百個(gè)開(kāi)源應(yīng)用的調(diào)研表明,不規(guī)則集合通信的使用十分廣泛,其中超過(guò)30%的應(yīng)用使用了Gatherv功能。在編碼解碼、深度學(xué)習(xí)和矩陣運(yùn)算等[2 - 5]方向的研究工作中,Allgatherv或Gatherv不規(guī)則集合通信具有廣泛的應(yīng)用需求。
Gatherv作為Gather的不規(guī)則版本,擴(kuò)展之處在于:根進(jìn)程可從不同的進(jìn)程接收不同長(zhǎng)度的消息,同時(shí)將收到的消息數(shù)據(jù)存放到緩沖區(qū)的任意位置。然而,不規(guī)則集合通信在為并行應(yīng)用設(shè)計(jì)帶來(lái)了極大的靈活性,提升了MPI標(biāo)準(zhǔn)描述能力的同時(shí),也為MPI集合通信在大規(guī)模環(huán)境下的實(shí)現(xiàn)帶來(lái)了較大的挑戰(zhàn)。
Linear結(jié)構(gòu)是Gatherv最為直觀、簡(jiǎn)單的實(shí)現(xiàn)方式,如圖1所示,根節(jié)點(diǎn)以串行方式逐次與其他節(jié)點(diǎn)進(jìn)行交互。MPICH[6]和OpenMPI[7]作為主流MPI實(shí)現(xiàn)方式,均采用傳統(tǒng)Linear結(jié)構(gòu)實(shí)現(xiàn)Gatherv。但是,當(dāng)節(jié)點(diǎn)數(shù)為n時(shí),其時(shí)間復(fù)雜度為O(n),由此帶來(lái)了嚴(yán)重的可擴(kuò)展性問(wèn)題。隨著進(jìn)程規(guī)模的增大,根進(jìn)程root需要和其他進(jìn)程建立大量連接通路,需要同時(shí)處理來(lái)自其他n-1個(gè)節(jié)點(diǎn)的通信請(qǐng)求,這使得連接通路產(chǎn)生的內(nèi)存開(kāi)銷隨之陡增,且通信熱點(diǎn)問(wèn)題顯著,難以支撐大規(guī)模并發(fā)應(yīng)用的不規(guī)則通信需求。
Figure 1 Structure of Linear圖1 Linear結(jié)構(gòu)
Binomial-Tree結(jié)構(gòu)如圖2所示,是一種二項(xiàng)式模型。當(dāng)進(jìn)程數(shù)為m時(shí),根節(jié)點(diǎn)的通信連接數(shù)控制在lb (m),其余進(jìn)程逐級(jí)承擔(dān)通信任務(wù),通信過(guò)程在各層級(jí)間有序異步并發(fā),可以有效緩解Linear結(jié)構(gòu)中根進(jìn)程連接通路內(nèi)存開(kāi)銷大、通信熱點(diǎn)顯著的問(wèn)題。目前,Binomial-Tree結(jié)構(gòu)廣泛應(yīng)用于諸如Bcast、Gather、Scatter和Reduce等規(guī)則集合通信實(shí)現(xiàn)。
Figure 2 Structure of Binomial-Tree圖2 Binomial-Tree結(jié)構(gòu)
在不規(guī)則集合通信的相關(guān)研究方面,Kang等[8]重點(diǎn)討論了通信拓?fù)浣Y(jié)構(gòu)上的優(yōu)化;Mallón等[9]通過(guò)在預(yù)處理階段使用Gather替代Gatherv的方式優(yōu)化圖像合成應(yīng)用的性能;Ascension等[10]基于Gatherv數(shù)據(jù)分塊進(jìn)行改進(jìn),以提高大型陣列計(jì)算應(yīng)用的性能;Jocksch等[11]著重于不規(guī)則集合通信算法的選擇與組合,此類研究有一定的參考意義,但對(duì)物理環(huán)境和應(yīng)用類型有一定的局限性。在Gatherv算法模型的相關(guān)研究上,Pje?ivac- Grbovic[12]和Nuriyev等[13]均詳細(xì)對(duì)比分析了Binomial-Tree結(jié)構(gòu)相對(duì)于Linear結(jié)構(gòu)在Gather上的應(yīng)用優(yōu)勢(shì);Traff[14,15]討論了MPI不規(guī)則集合通信建模方法, 對(duì)基于Binomial-Tree結(jié)構(gòu)建模的Scatterv和Gatherv進(jìn)行了深入的理論研究,為Gatherv基于Binomial-Tree結(jié)構(gòu)的高性能實(shí)現(xiàn)提供了理論支撐。
Binomial-Tree結(jié)構(gòu)在降低通信通路內(nèi)存開(kāi)銷和提升通信并發(fā)度方面,相對(duì)于Linear結(jié)構(gòu)具有無(wú)可比擬的優(yōu)勢(shì)。但是,將其應(yīng)用于不規(guī)則集合通信實(shí)現(xiàn),將面臨如下挑戰(zhàn):(1)接收數(shù)據(jù)量和偏移僅對(duì)根進(jìn)程有效,其他進(jìn)程無(wú)法掌握全局信息,導(dǎo)致根節(jié)點(diǎn)外的其他中間節(jié)點(diǎn)無(wú)法掌握本子樹(shù)內(nèi)的通信細(xì)節(jié),因此無(wú)法實(shí)現(xiàn)通信緩沖區(qū)的精細(xì)化管理;(2)該模型結(jié)構(gòu)涉及多個(gè)層次的消息通信,大規(guī)模并發(fā)條件下建立通信關(guān)系存在一定的計(jì)算開(kāi)銷;(3)由于消息目的地址可能不連續(xù),根進(jìn)程在處理消息偏移過(guò)程中可能存在頻繁的拷貝操作。
針對(duì)上述挑戰(zhàn),本文對(duì)MPI不規(guī)則集合通信Gatherv進(jìn)行了深入分析,從優(yōu)化等級(jí)、臨時(shí)緩沖區(qū)管理等方面,解決了不規(guī)則特性帶來(lái)的優(yōu)化難題,將Binomial-Tree結(jié)構(gòu)應(yīng)用于Gatherv實(shí)現(xiàn);并進(jìn)一步提出消息鏈調(diào)度機(jī)制,提升Gatherv在大規(guī)模環(huán)境下的性能。
在MPI文本定義[16]中,Gatherv部分參數(shù),如消息長(zhǎng)度recvcounts、偏移displs屬性,僅對(duì)根進(jìn)程有效,使得其它進(jìn)程在無(wú)法獲取全局信息的情況下難以建立Binomial-Tree結(jié)構(gòu)中的節(jié)點(diǎn)映射關(guān)系。為此,本文提出2種優(yōu)化等級(jí):符合文本定義的保守優(yōu)化等級(jí)和充分挖掘性能潛力的激進(jìn)優(yōu)化等級(jí)。
(1)保守優(yōu)化等級(jí):由根進(jìn)程通過(guò)廣播操作將recvcounts、displs及算法決策發(fā)送給其他進(jìn)程,使所有進(jìn)程都可以掌握全局信息。該方式符合文本定義,作為保守優(yōu)化等級(jí)。
(2)激進(jìn)優(yōu)化等級(jí):保守優(yōu)化等級(jí)嚴(yán)格遵守文本定義,但帶來(lái)了一定的廣播開(kāi)銷。在使用Gatherv的實(shí)際并行應(yīng)用中,各進(jìn)程常共享全局信息,因此本文在不規(guī)則屬性對(duì)所有進(jìn)程都有效、可見(jiàn)的條件下省略廣播操作,作為Gatherv激進(jìn)優(yōu)化等級(jí)。
2種優(yōu)化等級(jí)都能夠令所有進(jìn)程掌握全局信息,為構(gòu)建Binomial-Tree結(jié)構(gòu)提供先決條件。
建立Gatherv的模型結(jié)構(gòu):首先根據(jù)式(1),由各進(jìn)程的進(jìn)程號(hào)rank相對(duì)于根進(jìn)程的進(jìn)程號(hào)root計(jì)算相對(duì)進(jìn)程號(hào)relative_rank:
relative_rank=(rank-root+nt)%n
(1)
其中,nt為通信域進(jìn)程數(shù)。根據(jù)relative_rank建立進(jìn)程到節(jié)點(diǎn)的映射關(guān)系,將各進(jìn)程映射為葉節(jié)點(diǎn)、中間節(jié)點(diǎn)和根節(jié)點(diǎn),構(gòu)成Binomial-Tree。主要模型結(jié)構(gòu)如圖3所示,由各葉節(jié)點(diǎn)發(fā)送消息至其中間節(jié)點(diǎn),根節(jié)點(diǎn)和各中間節(jié)點(diǎn)接收子樹(shù)節(jié)點(diǎn)消息并存入各自臨時(shí)緩沖區(qū)tmp_buf,經(jīng)過(guò)多輪的消息收集和轉(zhuǎn)發(fā),最終將所有節(jié)點(diǎn)消息匯集至根節(jié)點(diǎn)。
該模型結(jié)構(gòu)不僅能消除根進(jìn)程通信熱點(diǎn)問(wèn)題,充分利用網(wǎng)絡(luò)帶寬,還能夠節(jié)省大量因建立連接通路而占用的內(nèi)存空間,對(duì)于進(jìn)程數(shù)為nt的通信域,根節(jié)點(diǎn)所需建立的連接通路個(gè)數(shù)為lb(nt),對(duì)比Linear結(jié)構(gòu)的n-1個(gè)連接通路,內(nèi)存開(kāi)銷大大降低。
Figure 3 Structure of Gatherv model圖3 Gatherv模型結(jié)構(gòu)
Gatherv支持進(jìn)程消息長(zhǎng)度各異的特性,為模型中臨時(shí)緩沖區(qū)管理帶來(lái)了難度:(1)為控制內(nèi)存開(kāi)銷、按需分配緩沖區(qū)空間,需要設(shè)計(jì)算法令根節(jié)點(diǎn)和中間節(jié)點(diǎn)計(jì)算出其子樹(shù)中所有節(jié)點(diǎn)進(jìn)程號(hào)src(作為消息源),從而根據(jù)進(jìn)程號(hào)src計(jì)算得出所需空間大??;(2)多層次的通信過(guò)程也需要計(jì)算消息源以建立通信關(guān)系,冗雜的計(jì)算過(guò)程帶了一定的成本。
為此,本文設(shè)計(jì)了消息源列表計(jì)算算法。如算法1所示,根節(jié)點(diǎn)和中間節(jié)點(diǎn)計(jì)算出當(dāng)前迭代mask下的直接消息源src,再分別計(jì)算出以直接消息源src作為中間節(jié)點(diǎn)的子樹(shù)中節(jié)點(diǎn)個(gè)數(shù)recvblks;根節(jié)點(diǎn)和中間節(jié)點(diǎn)分別根據(jù)式(2)和式(3)計(jì)算每輪通信中消息源節(jié)點(diǎn)個(gè)數(shù)recvblks;經(jīng)消息輪數(shù)mask和每輪通信中消息源節(jié)點(diǎn)個(gè)數(shù)recvblks的迭代逐個(gè)計(jì)算出所有消息源并寫入src_list列表,完成根節(jié)點(diǎn)和中間節(jié)點(diǎn)消息源列表src_list的建立。可以看到,src_list一方面用于計(jì)算臨時(shí)緩沖區(qū)大小,為進(jìn)程按需分配空間,以控制內(nèi)存開(kāi)銷;另一方面用于計(jì)算消息收發(fā)過(guò)程中的消息長(zhǎng)度,以“一次計(jì)算,多次使用”的方式控制計(jì)算成本。
(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 即時(shí)拷貝 此外,該模型結(jié)構(gòu)需要為根節(jié)點(diǎn)和中間節(jié)點(diǎn)分配臨時(shí)緩沖區(qū)tmp_buf以暫存消息,為節(jié)省內(nèi)存采取按需分配空間的方式。分配規(guī)則如下所示:(1)中間節(jié)點(diǎn)分配的臨時(shí)緩沖區(qū)大小為所需接收的所有子節(jié)點(diǎn)的消息長(zhǎng)度總和;(2)根節(jié)點(diǎn)分配的臨時(shí)緩沖區(qū)大小為除根節(jié)點(diǎn)及其直接葉節(jié)點(diǎn)外的所有節(jié)點(diǎn)的消息長(zhǎng)度總和。 3.3.2 消息收發(fā)規(guī)則 如圖4所示,模型中消息收發(fā)規(guī)則如下所示:(1)葉節(jié)點(diǎn):在第1輪通信中(step 1)直接將消息發(fā)給中間節(jié)點(diǎn)。(2)中間節(jié)點(diǎn):將自身消息從本地拷貝至臨時(shí)緩沖區(qū)tmp_buf,逐輪接收子節(jié)點(diǎn)消息至臨時(shí)緩沖區(qū)tmp_buf,最終將tmp_buf發(fā)給中間節(jié)點(diǎn)。中間節(jié)點(diǎn)根據(jù)模型結(jié)構(gòu)分布,有若干次接收操作和一次發(fā)送操作。(3)根節(jié)點(diǎn):預(yù)先(step 0)將自身消息由sendbuf本地拷貝至recvbuf對(duì)應(yīng)位置disp[root];再將直接葉節(jié)點(diǎn)在第1輪通信中(step 1)直接接收至recvbuf對(duì)應(yīng)的位置(參考disp屬性);來(lái)自中間節(jié)點(diǎn)的消息逐輪接收至臨時(shí)緩沖區(qū)tmp_buf。 由圖中可知,根節(jié)點(diǎn)臨時(shí)緩沖區(qū)在每輪接收消息后,結(jié)合消息源列表src_list和不規(guī)則屬性即時(shí)將臨時(shí)緩沖區(qū)消息拷貝至recvbuf,以通信和拷貝輪轉(zhuǎn)進(jìn)行的方式,避免了根節(jié)點(diǎn)前期通信密集、后期拷貝密集而造成的網(wǎng)絡(luò)擁塞和讀寫繁忙。此處拷貝方式和次數(shù)對(duì)性能影響較大,將在第3節(jié)詳細(xì)介紹關(guān)于消息鏈調(diào)度的優(yōu)化機(jī)制。 根節(jié)點(diǎn)逐個(gè)將每條消息按不規(guī)則屬性從臨時(shí)緩沖區(qū)拷貝至recvbuf的過(guò)程帶來(lái)了巨大開(kāi)銷。如圖3和圖4所示,根節(jié)點(diǎn)除了其葉節(jié)點(diǎn)消息直接發(fā)送至recvbuf外,其余所有消息都需從本地拷貝,且拷貝的次數(shù)隨消息輪數(shù)的增加呈指數(shù)級(jí)增長(zhǎng),當(dāng)消息長(zhǎng)度較大時(shí),拷貝帶寬受限,可以預(yù)見(jiàn)優(yōu)化效果并不理想。因此結(jié)合應(yīng)用特點(diǎn),盡量將消息直接寫入用戶地址空間,以減少拷貝次數(shù),這是提高Gatherv性能的有效途徑。 假設(shè)在每輪由中間節(jié)點(diǎn)發(fā)送至根節(jié)點(diǎn)的消息集中,將中間節(jié)點(diǎn)臨時(shí)緩沖區(qū)內(nèi)相鄰的消息相對(duì)劃分為前置消息pre_msg和當(dāng)前消息cur_msg,其對(duì)應(yīng)消息源稱為pre_src和cur_src,則2條消息連續(xù)的條件如式(4)所示: recvcounts[pre_src]*recvtype_size= displs[cur_src]*datatype_size (4) 當(dāng)式(4)成立時(shí),中間節(jié)點(diǎn)臨時(shí)緩沖區(qū)中相鄰消息在根節(jié)點(diǎn)recvbuf中的接收位置也相鄰,則定義2個(gè)相鄰消息為連續(xù)消息,否則為非連續(xù)消息。 對(duì)于使用Gatherv的大規(guī)模并行應(yīng)用,盡量將符合連續(xù)條件的通信過(guò)程合并成消息鏈,由根節(jié)點(diǎn)直接接收消息鏈至recvbuf,以減少本地拷貝操作,進(jìn)一步提升性能。需要說(shuō)明的是,根節(jié)點(diǎn)在每輪通信中從不同子樹(shù)接收消息,因此每輪通信之間的消息是否連續(xù)并不影響根節(jié)點(diǎn)行為。構(gòu)建消息鏈的工作主要集中在中間節(jié)點(diǎn)向根節(jié)點(diǎn)發(fā)送消息集的內(nèi)部。 首先基于消息源列表src_list獲取消息集內(nèi)每個(gè)消息的長(zhǎng)度和偏移屬性,并以第1個(gè)消息為起點(diǎn)構(gòu)建消息鏈。如圖5所示,依據(jù)式(4)以第1個(gè)消息(msg4)為消息鏈起點(diǎn),當(dāng)?shù)?個(gè)消息(msg5)與第1個(gè)消息的目的空間連續(xù)時(shí),則初始化消息鏈為連續(xù)消息鏈,否則為非連續(xù)消息鏈。 Figure 5 Construction of message chain圖5 消息鏈構(gòu)建 此后,每個(gè)當(dāng)前消息cur_msg都與前置消息pre_msg以式(4)為依據(jù)進(jìn)行連續(xù)性匹配,從而進(jìn)行消息鏈擴(kuò)展或重構(gòu)。如圖6所示,當(dāng)前消息與前置消息連續(xù),則需查看前置消息pre_msg所在消息鏈?zhǔn)欠駷檫B續(xù)消息鏈: (1)對(duì)于連續(xù)消息鏈,則將當(dāng)前消息cur_msg連接在前置消息pre_msg后,擴(kuò)展該消息鏈。 (2)對(duì)于非連續(xù)消息鏈,則將前置消息pre_msg之前的消息鏈(不包括pre_msg)執(zhí)行接收/發(fā)送操作,根節(jié)點(diǎn)通過(guò)臨時(shí)緩沖區(qū)接收非連續(xù)消息鏈,進(jìn)行“一次接收,逐個(gè)拷貝”操作,將各消息拷貝至recvbuf相應(yīng)位置。隨后中間節(jié)點(diǎn)以前置消息pre_msg作為起點(diǎn),將當(dāng)前消息cur_msg連接在pre_msg后,構(gòu)成連續(xù)消息鏈。 Figure 6 Scheduling of continuous message圖6 連續(xù)消息調(diào)度 如圖7所示,當(dāng)前消息與前置消息不連續(xù)時(shí),也需根據(jù)前置消息pre_msg所在的消息鏈類型進(jìn)行處理: (1)對(duì)于非連續(xù)消息鏈,則將當(dāng)前消息cur_msg連接在前置消息pre_msg后,擴(kuò)展該非連續(xù)消息鏈。非連續(xù)鏈的構(gòu)建和擴(kuò)展目的在于最大程度地將非連續(xù)消息鏈合并發(fā)送至根節(jié)點(diǎn),雖無(wú)法避免根節(jié)點(diǎn)在接收到非連續(xù)消息鏈后的拷貝開(kāi)銷,但能夠有效減少通信次數(shù),減輕網(wǎng)絡(luò)壓力。 (2)對(duì)于連續(xù)消息鏈,則根據(jù)“連續(xù)消息最大化直接接收”的原則,將前置消息pre_msg擴(kuò)展至連續(xù)消息鏈,再令連續(xù)消息鏈執(zhí)行接收/發(fā)送操作,根節(jié)點(diǎn)直接將連續(xù)消息鏈接收至recvbuf。隨后以當(dāng)前消息cur_msg為起點(diǎn)重構(gòu)消息鏈。 Figure 7 Scheduling of discontinuous message圖7 非連續(xù)消息調(diào)度 在每輪通信處理完最后一個(gè)消息后,將連續(xù)/非連續(xù)消息鏈發(fā)出,根節(jié)點(diǎn)依據(jù)消息鏈類型進(jìn)行接收。由此,通過(guò)消息鏈調(diào)度機(jī)制,根節(jié)點(diǎn)能夠最大程度地由recvbuf直接接收連續(xù)消息,避免對(duì)連續(xù)消息進(jìn)行拷貝,減少了開(kāi)銷;對(duì)非連續(xù)消息也能實(shí)現(xiàn)“一次接收,逐個(gè)拷貝”,減輕了網(wǎng)絡(luò)壓力。 本文在神威高性能計(jì)算系統(tǒng)上實(shí)現(xiàn)了Gatherv優(yōu)化方法,并以神威高性能計(jì)算系統(tǒng)為目標(biāo)平臺(tái),使用自編micro-benchmark及標(biāo)準(zhǔn)測(cè)試程序IMB(Intel MPI Benchmark),分別對(duì)本文優(yōu)化方法的內(nèi)存開(kāi)銷及Gatherv通信性能進(jìn)行了測(cè)試,并和Gather規(guī)則通信的性能進(jìn)行了對(duì)比。 通信過(guò)程中,通信雙方需要通過(guò)上下文來(lái)支持連接通路,連接通路的數(shù)量將決定通信支撐環(huán)境的內(nèi)存開(kāi)銷。本文采用自編micro-benchmark,通過(guò)通信過(guò)程結(jié)束前后的可用內(nèi)存差值來(lái)計(jì)算通信過(guò)程中構(gòu)建通信連接通路所產(chǎn)生的內(nèi)存開(kāi)銷。本節(jié)對(duì)比了Linear結(jié)構(gòu)實(shí)現(xiàn)和本文優(yōu)化實(shí)現(xiàn)的Gatherv在構(gòu)建連接通路方面的內(nèi)存開(kāi)銷情況。如圖8所示,32 768個(gè)進(jìn)程規(guī)模下Linear結(jié)構(gòu)產(chǎn)生了約1 312.12 MB內(nèi)存開(kāi)銷,而本文基于Binomial-Tree結(jié)構(gòu)將內(nèi)存開(kāi)銷控制在較低水平(僅約0.60 MB);其他進(jìn)程規(guī)模下,本文優(yōu)化實(shí)現(xiàn)方法(保守優(yōu)化與激進(jìn)優(yōu)化內(nèi)存開(kāi)銷一致)的內(nèi)存開(kāi)銷為L(zhǎng)inear結(jié)構(gòu)的lbn/(n-1),優(yōu)化效果符合預(yù)期。通過(guò)上述測(cè)試數(shù)據(jù)不難發(fā)現(xiàn),本文優(yōu)化方法可以以極低的內(nèi)存開(kāi)銷高效支持用戶在大規(guī)模并發(fā)條件下的Gatherv不規(guī)則集合通信。 Figure 8 Comparision of Gatherv memory overhead圖8 Gatherv內(nèi)存開(kāi)銷對(duì)比 本節(jié)使用標(biāo)準(zhǔn)測(cè)試程序IMB對(duì)MPICH基于Linear結(jié)構(gòu)實(shí)現(xiàn)的Gatherv與本文保守優(yōu)化實(shí)現(xiàn)的Gatherv通信性能進(jìn)行了對(duì)比測(cè)試。如表1、表2、圖9和圖10所示,相對(duì)于Linear結(jié)構(gòu)實(shí)現(xiàn),Gatherv保守優(yōu)化實(shí)現(xiàn)有大幅的性能提升,且優(yōu)化效果隨進(jìn)程規(guī)模增大而增強(qiáng),在消息長(zhǎng)度為8 B、進(jìn)程規(guī)模為32 768時(shí)加速比達(dá)到41 068;在消息長(zhǎng)度為8 KB、進(jìn)程規(guī)模為32 768時(shí),加速比達(dá)到32 709。另外,數(shù)據(jù)顯示Linear結(jié)構(gòu)下的短消息(8 B)開(kāi)銷比長(zhǎng)消息(8 KB)開(kāi)銷更大,原因?yàn)槎滔⒉捎玫腅ager協(xié)議需要接收端進(jìn)行用戶數(shù)據(jù)的拷貝操作,而長(zhǎng)消息采用Rendezvous協(xié)議,數(shù)據(jù)由發(fā)送端通過(guò)遠(yuǎn)程直接內(nèi)存訪問(wèn)RDMA(Remote Direct Memory Access)寫操作寫入接收端目的地址。因此,短消息協(xié)議下Linear結(jié)構(gòu)根節(jié)點(diǎn)的拷貝壓力更大,熱點(diǎn)效應(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 消息長(zhǎng)度為8 KB時(shí)的Gatherv保守優(yōu)化效果 Figure 9 Gatherv overhead when message length is 8 B圖9 消息長(zhǎng)度為8 B時(shí)的Gatherv開(kāi)銷 Figure 10 Gatherv overhead when message length is 8 KB圖10 消息長(zhǎng)度為8 KB時(shí)的Gatherv開(kāi)銷 對(duì)比測(cè)試表明,本文提出的優(yōu)化方法在模型結(jié)構(gòu)上具備一定的優(yōu)越性,同時(shí)消息鏈調(diào)度機(jī)制能夠有效控制拷貝開(kāi)銷,相較于傳統(tǒng)Linear方法具有明顯優(yōu)勢(shì)。 本節(jié)對(duì)2種Gatherv優(yōu)化實(shí)現(xiàn)和基于Binomial-Tree結(jié)構(gòu)實(shí)現(xiàn)的Gather進(jìn)行性能對(duì)比測(cè)試,以驗(yàn)證本文優(yōu)化方法可以有效擴(kuò)展至大規(guī)模并發(fā)情況。測(cè)試使用標(biāo)準(zhǔn)測(cè)試程序IMB,分別測(cè)試8 B短消息和8 KB長(zhǎng)消息的Gatherv及Gather開(kāi)銷。圖11和圖12的測(cè)試結(jié)果表明:(1)Gatherv保守優(yōu)化和激進(jìn)優(yōu)化實(shí)現(xiàn)的開(kāi)銷在進(jìn)程規(guī)模2倍遞增時(shí)均實(shí)現(xiàn)了小于2倍的增長(zhǎng),具有良好的性能可擴(kuò)展性。(2)Gatherv保守優(yōu)化與激進(jìn)優(yōu)化實(shí)現(xiàn)之間存在略微的性能差距,主要來(lái)自于預(yù)處理階段對(duì)recvcounts、displs及算法決策信息的廣播開(kāi)銷。(3)激進(jìn)優(yōu)化實(shí)現(xiàn)的Gatherv性能,和基于Binomial-Tree結(jié)構(gòu)實(shí)現(xiàn)的Gather性能相比,基本處于同一數(shù)量級(jí),只存在局部差異。消息長(zhǎng)度較短(8 B)時(shí),激進(jìn)優(yōu)化實(shí)現(xiàn)的Gatherv開(kāi)銷略高于Gather的。原因?yàn)椋和ㄐ砰_(kāi)銷相對(duì)較小,此時(shí)構(gòu)建src_list和消息鏈的額外開(kāi)銷在整體開(kāi)銷中占比相對(duì)較大,因此導(dǎo)致整體開(kāi)銷略大。消息長(zhǎng)度較長(zhǎng)(8 KB)時(shí),激進(jìn)優(yōu)化實(shí)現(xiàn)的Gatherv開(kāi)銷略低于Gather的原因?yàn)椋和ㄐ砰_(kāi)銷在整體開(kāi)銷中的占比較大,一定程度上弱化了激進(jìn)優(yōu)化實(shí)現(xiàn)的額外開(kāi)銷的影響,且由于激進(jìn)優(yōu)化實(shí)現(xiàn)在通信過(guò)程中直接使用預(yù)先構(gòu)建的src_list和消息鏈,而基于Binomial- Tree結(jié)構(gòu)實(shí)現(xiàn)的Gather采用“邊通信邊計(jì)算對(duì)象”的模式,因此,激進(jìn)優(yōu)化的Gatherv實(shí)現(xiàn)帶寬利用率略好。需要說(shuō)明的是,構(gòu)建src_list和消息鏈的額外開(kāi)銷會(huì)隨著進(jìn)程數(shù)的增加而增大,當(dāng)進(jìn)程數(shù)增加到一定程度且消息長(zhǎng)度不變時(shí),會(huì)使激進(jìn)優(yōu)化實(shí)現(xiàn)中的上述額外開(kāi)銷的影響逐漸顯現(xiàn)。圖12中當(dāng)進(jìn)程規(guī)模增大至32 768時(shí),就出現(xiàn)了激進(jìn)優(yōu)化實(shí)現(xiàn)的Gatherv開(kāi)銷略高于Gather開(kāi)銷的現(xiàn)象。但是,如果消息長(zhǎng)度增加,可以預(yù)見(jiàn)額外開(kāi)銷對(duì)于激進(jìn)優(yōu)化實(shí)現(xiàn)的性能影響將進(jìn)一步被弱化,激進(jìn)優(yōu)化實(shí)現(xiàn)的Gatherv開(kāi)銷仍將低于基于Binomial-Tree結(jié)構(gòu)實(shí)現(xiàn)的Gather的。 Figure 11 Gatherv/Gather overhead when message length is 8 B圖11 消息長(zhǎng)度為8 B時(shí)的Gatherv/Gather開(kāi)銷 Figure 12 Gatherv/Gather overhead when message length is 8 KB圖12 消息長(zhǎng)度為8 KB時(shí)的Gatherv/Gather開(kāi)銷 本文針對(duì)當(dāng)前MPI不規(guī)則化集合通信Gatherv實(shí)現(xiàn)方法存在的通信熱點(diǎn)突出、內(nèi)存開(kāi)銷大和訪存效率低等問(wèn)題,提出了一種面向大規(guī)模并發(fā)的Gatherv優(yōu)化方法。從優(yōu)化等級(jí)、臨時(shí)緩沖區(qū)管理等方面出發(fā),研究高效均衡、內(nèi)存開(kāi)銷可控的優(yōu)化措施,將Binomial-Tree結(jié)構(gòu)成功應(yīng)用于Gatherv的實(shí)現(xiàn),并基于此設(shè)計(jì)了消息鏈調(diào)度機(jī)制,有效限制根進(jìn)程拷貝開(kāi)銷,進(jìn)一步提升了Gatherv性能,對(duì)MPI不規(guī)則集合通信的優(yōu)化工作有一定的參考意義。測(cè)試結(jié)果表明,本文方法可以有效解決現(xiàn)有方法存在的缺陷,相對(duì)于Linear結(jié)構(gòu),在內(nèi)存開(kāi)銷和通信性能方面均有顯著改進(jìn),可以有效保證Gatherv不規(guī)則集合通信在大規(guī)模并發(fā)條件下的高效可擴(kuò)展性。4 基于消息鏈調(diào)度的性能優(yōu)化機(jī)制
4.1 消息鏈初始化
4.2 連續(xù)消息調(diào)度
4.3 非連續(xù)消息調(diào)度
5 測(cè)試與分析
5.1 內(nèi)存開(kāi)銷測(cè)試
5.2 通信性能對(duì)比測(cè)試
5.3 性能擴(kuò)展性測(cè)試
6 結(jié)束語(yǔ)