1、一種超大規(guī)模MPI柵欄同步的硬件卸載方法摘要：在大規(guī)模并行計(jì)算機(jī)中，聚合通信的性能一直是全系統(tǒng)的性能瓶頸.本文提出了一種在超大規(guī)模并行計(jì)算機(jī)系統(tǒng)中采用的基于NIC的硬件卸載MPI柵欄同步的方法.方法基于改良的Dissemination柵欄同步算法，由MPI驅(qū)動(dòng)程序生成柵欄同步的算法框架，實(shí)際的通信操作由NIC硬件自動(dòng)完成，針對(duì)算法設(shè)計(jì)了硬件易于實(shí)現(xiàn)的基于描繪符的軟硬件接口和硬件執(zhí)行算法，大大進(jìn)步了柵欄同步的效率.通過(guò)與軟件實(shí)現(xiàn)的算法性能比擬，本文方法的通信延遲比現(xiàn)有方法平均進(jìn)步了40%.關(guān)鍵詞：柵欄同步；硬件卸載；描繪符中圖分類(lèi)號(hào)：TP302.1 文獻(xiàn)標(biāo)識(shí)碼：ANIC Based Hardwa

2、re Offload of MPI Barrierfor Exascale Super puterWANG Shao-gang，XU Wei-xia，WU Dan，PANG Zheng-bin，XU Jin-boCollege of puter， National Univ of Defense Technology， Changsha， Hunan 410073， ChinaAbstract： Barrier synchronization is an important munication pattern for high performance super puters. This p

3、aper proposed a new NIC-based barrier munication offload method. The new method improved the traditional dissemination barrier algorithm to support parallel barrier message sending and receiving， which greatly reduced the munication delay. Based on the new barrier algorithm， this paper proposed new

4、descriptor based hardware-software interface and the hardware implementation. The performance was greatly improved， pared with the traditional barrier implementation.Key words： barrier munication；hardware offload； munication descriptor聚合通信在MPI程序中占據(jù)相當(dāng)大的比例，對(duì)系統(tǒng)性能的影響很大，據(jù)已有統(tǒng)計(jì)，在大量科學(xué)計(jì)算和工程應(yīng)用程序中，聚合通信的通信時(shí)間占MP

5、I通信時(shí)間的80%，其執(zhí)行時(shí)間占總執(zhí)行時(shí)間的60%2.因此，對(duì)聚合通信進(jìn)展硬件加速很有必要.事實(shí)上，目前的一些大系統(tǒng)上，節(jié)點(diǎn)控制器或NIC芯片有很大的一局部功能用來(lái)實(shí)現(xiàn)MPI卸載功能.因此，基于NIC芯片的聚合通信卸載是進(jìn)步MPI聚合通信效率的重要途徑3-5.基于Exascale級(jí)計(jì)算機(jī)系統(tǒng)的通信需求，本文提出了一種基于柵欄同步描繪符的硬件卸載方案，將原來(lái)由軟件實(shí)現(xiàn)的柵欄同步下放到硬件中自動(dòng)執(zhí)行，實(shí)現(xiàn)了計(jì)算與通信的并行，可有效地支持上10萬(wàn)個(gè)節(jié)點(diǎn)間的柵欄通信.本文的主要奉獻(xiàn)包括：1提出了易于硬件實(shí)現(xiàn)的大規(guī)模柵欄同步算法，算法針對(duì)經(jīng)典的Dissemination算法進(jìn)展了改良6-7，提出了多路并

6、行的改良算法，更適宜在目前高帶寬和延遲的網(wǎng)絡(luò)中采用.2針對(duì)柵欄同步算法的特性，設(shè)計(jì)了基于描繪符的軟硬件接口.描繪符描繪了硬件執(zhí)行算法時(shí)的執(zhí)行過(guò)程，由軟件負(fù)責(zé)生成，而詳細(xì)的通信那么交給NIC硬件自動(dòng)執(zhí)行，實(shí)現(xiàn)了聚合通信與主機(jī)計(jì)算的并行，可有效支持MPI3.08的非阻塞通信特性.3 詳細(xì)測(cè)試了基于改良Dissemination算法的硬件卸載方案，測(cè)試說(shuō)明，本文方案具有明顯的性能優(yōu)勢(shì)，在128個(gè)節(jié)點(diǎn)規(guī)模下，比傳統(tǒng)方案的延遲降低了近73%.1 算 法1.1 Dissemination算法經(jīng)典的Dissemination算法步驟如圖1所示.假設(shè)全系統(tǒng)參與柵欄同步的節(jié)點(diǎn)數(shù)目為p， 在Disseminati

7、on算法下，共需要進(jìn)展s輪迭代.在第r輪中節(jié)點(diǎn)j得悉的已到達(dá)柵欄點(diǎn)的節(jié)點(diǎn)集合為Sjr， 那么柵欄同步所需的輪數(shù)為log2p輪.在經(jīng)典的Dissemination算法中，節(jié)點(diǎn)的一輪?wèn)艡谕讲僮魍瓿傻臈l件是：向目的節(jié)點(diǎn)發(fā)送了柵欄到達(dá)的消息，且收到了其他節(jié)點(diǎn)發(fā)送來(lái)的柵欄消息， p個(gè)節(jié)點(diǎn)完成柵欄同步共需要log2p輪.根據(jù)大規(guī)模并行計(jì)算機(jī)節(jié)點(diǎn)通信的特點(diǎn)：節(jié)點(diǎn)帶寬比擬高而節(jié)點(diǎn)間傳輸?shù)难舆t比擬大.在經(jīng)典的Dissemination算法中，每一輪發(fā)出一個(gè)報(bào)文后，需要等待響應(yīng)報(bào)文的到達(dá)，這期間節(jié)點(diǎn)是空閑的.假設(shè)增加每一輪發(fā)送的報(bào)文數(shù)，使節(jié)點(diǎn)等待響應(yīng)報(bào)文的時(shí)間重疊，就可以有效利用節(jié)點(diǎn)網(wǎng)絡(luò)的傳輸帶寬，并減少柵欄算

8、法的輪數(shù). 針對(duì)以上問(wèn)題，對(duì)Dissemination算法做出如下改良：在每一輪中，每個(gè)節(jié)點(diǎn)向多個(gè)目的節(jié)點(diǎn)發(fā)送柵欄到達(dá)報(bào)文，同時(shí)接收其他多個(gè)節(jié)點(diǎn)發(fā)送給該節(jié)點(diǎn)的報(bào)文消息.在2路的Dissemination算法下，對(duì)任意節(jié)點(diǎn)i，在第s輪中，其發(fā)送的目的節(jié)點(diǎn)號(hào)j為： j=i+3smodp 和i-3s+pmodp；接收的兩個(gè)節(jié)點(diǎn)號(hào)為：j=i+3smodp和 i-3s+pmodp.改良的Dissemination算法的過(guò)程如圖2所示.假設(shè)全系統(tǒng)參與柵欄同步的節(jié)點(diǎn)數(shù)目為p， 在改良的Dissemination算法下，共需要進(jìn)展s輪迭代.在第r輪中節(jié)點(diǎn)j得悉的已到達(dá)柵欄點(diǎn)的節(jié)點(diǎn)集合為Sjr，那么柵欄同步所需

9、的輪數(shù)為log3p輪.證明 采用數(shù)學(xué)歸納法證明.綜上證明，對(duì)p個(gè)節(jié)點(diǎn)完成柵欄同步操作，需要滿(mǎn)足3sp， 即共需要進(jìn)展log3p輪?wèn)艡谕?證畢.改良的Dissemination算法的步驟數(shù)由原來(lái)的og2p輪減少為log3p輪，針對(duì)網(wǎng)絡(luò)的詳細(xì)情況，改良的Dissemination算法還允許繼續(xù)增加輪中報(bào)文發(fā)送和接收的數(shù)量.如圖3所示.2 支持柵欄同步硬件卸載的NIC體系構(gòu)造針對(duì)改良的Dissemination算法，本文設(shè)計(jì)了支持硬件自動(dòng)執(zhí)行算法的體系構(gòu)造.硬件執(zhí)行改良Dissemination算法的主要思想是： 軟件生成基于改良Dissemination的算法步驟計(jì)算出之后，生成柵欄同步描繪符，

10、通過(guò)主機(jī)與NIC間的描繪符提交機(jī)制，交由NIC硬件自動(dòng)執(zhí)行.算法步驟在硬件執(zhí)行完成后，硬件通知軟件同步完成，在此期間，實(shí)現(xiàn)了通信與計(jì)算的并行.2.1 NIC體系構(gòu)造本方案提出的硬件實(shí)現(xiàn)架構(gòu)如圖4所示，主要包含：描繪符隊(duì)列管理模塊、各種描繪符處理模塊MP，RDMA，BARRIER等、訪(fǎng)存仲裁模塊、網(wǎng)絡(luò)仲裁模塊、主機(jī)接口以及網(wǎng)絡(luò)接口模塊.每個(gè)描繪符處理模塊支持一種類(lèi)型的通信點(diǎn)對(duì)點(diǎn)或聚合通信.2.1.1 描繪符隊(duì)列管理模塊其主要作用是管理虛端口上的各種軟硬件接口隊(duì)列和中斷，包括描繪符隊(duì)列、完成隊(duì)列、完成中斷管理等.描繪符隊(duì)列管理模塊讀取一個(gè)描繪符之后，根據(jù)描繪符的類(lèi)型，向描繪符處理單元派發(fā)描繪符信息

11、，同時(shí)接收各個(gè)模塊返回的完成信息，根據(jù)要求更新完成隊(duì)列或觸發(fā)中斷等.在NIC中，描繪符管理模塊及各種描繪符處理模塊會(huì)產(chǎn)生訪(fǎng)存懇求.例如，MP描繪符處理模塊需要向MP接收隊(duì)列中寫(xiě)數(shù)據(jù)，RDMA描繪符處理模塊需要讀寫(xiě)本地RDMA緩沖區(qū)，描繪符中可能規(guī)定向本地節(jié)點(diǎn)的某個(gè)地址寫(xiě)完成值等.為了統(tǒng)一處理這些模塊的訪(fǎng)存懇求，設(shè)置訪(fǎng)存仲裁模塊，用來(lái)仲裁這些模塊的訪(fǎng)存懇求.為了支持虛擬地址傳輸形式，在訪(fǎng)存仲裁模塊中，還允許增加地址轉(zhuǎn)換邏輯.2.1.3 主機(jī)接口主機(jī)接口實(shí)現(xiàn)與主機(jī)的通信，根據(jù)處理器類(lèi)型，可選擇支持PCIE或QPI等協(xié)議，主機(jī)接口的實(shí)現(xiàn)對(duì)內(nèi)存處理邏輯透明.2.1.4 網(wǎng)絡(luò)接口各種描繪符處理模塊都需要

12、向網(wǎng)絡(luò)中發(fā)送報(bào)文，為了實(shí)現(xiàn)各個(gè)描繪符處理模塊的獨(dú)立性，簡(jiǎn)化設(shè)計(jì)，且方便網(wǎng)絡(luò)報(bào)文的派發(fā)仲裁，每種類(lèi)型的描繪符處理模塊定義自己的專(zhuān)用報(bào)文類(lèi)型，并根據(jù)各自操作的要求，獨(dú)立定義報(bào)文搭載數(shù)據(jù)的格式.網(wǎng)絡(luò)仲裁模塊根據(jù)報(bào)文類(lèi)型，對(duì)來(lái)自于各個(gè)模塊的網(wǎng)絡(luò)報(bào)文發(fā)送懇求進(jìn)展仲裁，同時(shí)向各個(gè)模塊派發(fā)從網(wǎng)絡(luò)中接收到的報(bào)文.NIC體系構(gòu)造的優(yōu)點(diǎn)是模塊功能劃分比擬明晰，各模塊間互相獨(dú)立，易于硬件實(shí)現(xiàn)，并且可以靈敏地根據(jù)實(shí)際情況對(duì)硬件功能進(jìn)展增加或裁減.2.2 基于改良Dissemination算法的描繪符在本文提出的方案中，描繪符是軟硬件之間的接口.描繪符給出了基于改良Dissemination算法的執(zhí)行步驟.在參與同步的

13、各個(gè)節(jié)點(diǎn)上，軟件通過(guò)節(jié)點(diǎn)本地的信息即可計(jì)算出算法步驟，包括以下信息：算法共需要多少輪操作，每輪操作的源節(jié)點(diǎn)是哪些，目的節(jié)點(diǎn)是哪些.節(jié)點(diǎn)上的軟件只需要知道本結(jié)點(diǎn)的RANK號(hào)，及參與柵欄同步的通信域節(jié)點(diǎn)個(gè)數(shù)就可以計(jì)算出，而不需要進(jìn)展實(shí)際的通信，最大化地實(shí)現(xiàn)數(shù)據(jù)處理與通信的獨(dú)立及重疊.柵欄同步描繪符的格式如圖5所示.由于算法每輪的操作具有依賴(lài)的關(guān)系，及下一輪的操作需要等待上一輪的操作完成后才進(jìn)展.硬件部件設(shè)計(jì)的關(guān)鍵是提供條件觸發(fā)執(zhí)行的機(jī)制. 基于本文給出的描繪符構(gòu)造，系統(tǒng)最多支持20輪的Dissemination柵欄同步算法，理論上，算法支持上百萬(wàn)個(gè)節(jié)點(diǎn)的柵欄同步，可以滿(mǎn)足Exascale級(jí)計(jì)算機(jī)同

14、步的需求.軟件生成的描繪符提交的方式可以采用如下兩種：1 描繪符存放在系統(tǒng)主存中，由網(wǎng)絡(luò)接口控制器NIC主動(dòng)訪(fǎng)問(wèn)系統(tǒng)主存獲??；2 主機(jī)通過(guò)主機(jī)與網(wǎng)絡(luò)接口控制器NIC的接口PCIe發(fā)送NIO存放器寫(xiě)命令將描繪符寫(xiě)入網(wǎng)絡(luò)接口控制器NIC的存放器或片上存儲(chǔ)器中.2.3 柵欄同步報(bào)文為了實(shí)現(xiàn)上述的改良Dissemination柵欄同步算法，需要根本的同步報(bào)文支持.經(jīng)過(guò)分解算法，柵欄同步算法可以通過(guò)以下最根本的柵欄操作實(shí)現(xiàn).如圖6所示，節(jié)點(diǎn)P0通過(guò)發(fā)送柵欄到達(dá)報(bào)文給目的節(jié)點(diǎn)P1，通知目的節(jié)點(diǎn)源節(jié)點(diǎn)已經(jīng)到達(dá)柵欄點(diǎn)，由于目的節(jié)點(diǎn)可能會(huì)出現(xiàn)無(wú)法處理的情況，因此需要響應(yīng)報(bào)文返回源節(jié)點(diǎn).在目的方，設(shè)置有一定深度的

15、報(bào)文緩沖DAMQ9-10，報(bào)文只要進(jìn)入DAMQ，源節(jié)點(diǎn)就認(rèn)為已經(jīng)通知了目的節(jié)點(diǎn)，目的節(jié)點(diǎn)給出響應(yīng).目的節(jié)點(diǎn)的柵欄同步描繪符提交后，檢查DAMQ中是否有之前接收的柵欄到達(dá)報(bào)文，并進(jìn)展處理.假設(shè)目的節(jié)點(diǎn)的DAMQ已滿(mǎn)，且描繪符還未提交，那么給出NACK響應(yīng)，通知源節(jié)點(diǎn)該通知報(bào)文未被處理，源節(jié)點(diǎn)收到NACK響應(yīng)后，將延遲重發(fā)柵欄通知報(bào)文，直到目的節(jié)點(diǎn)的描繪符提交，對(duì)報(bào)文進(jìn)展了處理.SDQ：內(nèi)存中的描繪符隊(duì)列，軟件通知NIC硬件主動(dòng)到內(nèi)存中取描繪符.HDQ：NIC使用片上存儲(chǔ)器實(shí)現(xiàn)的描繪符隊(duì)列，軟件通過(guò)PIO的方式提交.OF：描繪符派發(fā)邏輯，從SDQ和HDQ中取出描繪符，并派發(fā)給相應(yīng)的執(zhí)行模塊.TE：

16、從OF收到描繪符后，根據(jù)描繪符規(guī)定的柵欄到達(dá)報(bào)文發(fā)送順序，向目的節(jié)點(diǎn)發(fā)出報(bào)文；在某一輪，有可能需要向多個(gè)節(jié)點(diǎn)發(fā)出通知報(bào)文，發(fā)送完畢后，檢查響應(yīng)報(bào)文DAMQ中，響應(yīng)是否收齊，然后根據(jù)條件看是否處理下一輪?wèn)艡诓僮鞯膱?bào)文.某一輪?wèn)艡谕ㄖ獔?bào)文可以發(fā)送的條件是：節(jié)點(diǎn)已經(jīng)全部接收了該輪之前所應(yīng)該收到的來(lái)自其他節(jié)點(diǎn)的柵欄通知報(bào)文，該信息由SE輸出給TE模塊.SE：該模塊接收來(lái)自其他節(jié)點(diǎn)的柵欄通知報(bào)文，根據(jù)描繪符規(guī)定的順序，當(dāng)某一輪應(yīng)當(dāng)收到的柵欄通知報(bào)文收全后，才開(kāi)場(chǎng)接收下一輪的報(bào)文.其他節(jié)點(diǎn)發(fā)送的柵欄通知報(bào)文，先保存在DAMQ中.該模塊接收?qǐng)?bào)文完成的輪數(shù)需要輸出給TE模塊，以便確定本節(jié)點(diǎn)柵欄報(bào)文的發(fā)送時(shí)機(jī).

17、遠(yuǎn)程懇求報(bào)文DAMQ：保存其他節(jié)點(diǎn)發(fā)送給本節(jié)點(diǎn)的柵欄到達(dá)通知，采用DAMQ方式管理，報(bào)文只要進(jìn)入DAMQ，就認(rèn)為已經(jīng)通知了本節(jié)點(diǎn)，給出正常的響應(yīng)，假設(shè)DAMQ隊(duì)列已滿(mǎn)，那么DAMQ模塊給出NACK響應(yīng)，通知發(fā)送節(jié)點(diǎn)目的方無(wú)法接收，發(fā)送節(jié)點(diǎn)需要在延遲一段時(shí)間后，重新發(fā)出報(bào)文.遠(yuǎn)程響應(yīng)報(bào)文DAMQ：本節(jié)點(diǎn)發(fā)出的柵欄通知報(bào)文的響應(yīng)報(bào)文先保存在DAMQ中，DAMQ的容量應(yīng)可以包容下發(fā)出的所有報(bào)文的響應(yīng)報(bào)文.3 基于硬件卸載的柵欄同步性能評(píng)測(cè)針對(duì)本文提出的支持改良Dissemination算法的NIC體系構(gòu)造，采用SystemVerilog建模語(yǔ)言實(shí)現(xiàn)了本文提出的柵欄同步引擎BE，并在VCS模擬器上針對(duì)

18、多種系統(tǒng)規(guī)模和實(shí)現(xiàn)參數(shù)進(jìn)展了仿真.在模擬環(huán)境中，本文最多實(shí)例化了128個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)間通過(guò)3D-Torus形式進(jìn)展互連，為簡(jiǎn)化網(wǎng)絡(luò)實(shí)現(xiàn)，路由采用維序路由，單跳延遲采取了固定值.3.1 柵欄同步延遲基于給定的網(wǎng)絡(luò)延遲，本文測(cè)試了不同節(jié)點(diǎn)規(guī)模的柵欄同步性能.為了測(cè)試算法本身的性能，本次測(cè)試不考慮節(jié)點(diǎn)間到達(dá)柵欄點(diǎn)的時(shí)間不同步而帶來(lái)的延遲.測(cè)試的結(jié)果如圖8所示.從本次測(cè)試可以看出，本文提出的基于改良Dissemination算法的柵欄同步硬件卸載方案具有很好的可擴(kuò)展性，在節(jié)點(diǎn)數(shù)增多時(shí)，柵欄同步的延遲并沒(méi)有像傳統(tǒng)的聚合通信算法那樣，呈現(xiàn)出指數(shù)級(jí)的延遲增加.本文提出的方案延遲根本呈現(xiàn)較緩慢的線(xiàn)性延遲增長(zhǎng)，這種特性對(duì)于Exascale級(jí)的超計(jì)算機(jī)來(lái)說(shuō)至關(guān)重要11.3.2 與軟件算法的性能比照為了測(cè)試基于硬件卸載的柵欄同步算法的性能改良，我們完全由軟件實(shí)現(xiàn)了傳統(tǒng)的Dissemination算法和改良的Dissemination算法，測(cè)試其性能，并與基于硬件實(shí)現(xiàn)改良算法的性能進(jìn)展比照，測(cè)試結(jié)果如圖9所示.可以看出，與軟件實(shí)現(xiàn)的方法相比，基于硬件卸載的實(shí)現(xiàn)途徑具有明顯的性能改良，特別是在大規(guī)模系統(tǒng)中，聚合通信的開(kāi)銷(xiāo)占全系統(tǒng)通信開(kāi)銷(xiāo)的80%以上，硬件卸載全局通信的性能優(yōu)勢(shì)更能有效地表達(dá)出來(lái).軟件算法實(shí)現(xiàn)建立在點(diǎn)對(duì)點(diǎn)算法根底上，而硬件卸載的改良Dissemination算法實(shí)現(xiàn)了多報(bào)