張 鑫 董德尊 龐征斌

（國防科技大學(xué)計(jì)算機(jī)學(xué)院 長(zhǎng)沙 410073）

1 引言

在共享和分布式存儲(chǔ)的并行系統(tǒng)中，聚合通信通常是分布式應(yīng)用程序的一組進(jìn)程間互相協(xié)作，通過相互之間的消息傳遞來達(dá)到數(shù)據(jù)交換、任務(wù)控制和全局計(jì)算的目的。聚合操作可以被認(rèn)為是一種同步操作，因?yàn)樗笤谕ㄐ胖猩婕暗乃羞^程協(xié)同工作。因此，聚合通信操作的快慢會(huì)直接影響并行應(yīng)用的效率。并且聚合操作在高性能計(jì)算機(jī)的科學(xué)計(jì)算時(shí)間消耗上有時(shí)候可占據(jù)高達(dá)70%。文獻(xiàn)［1］總結(jié)了在不同大規(guī)模應(yīng)用程序中不同聚合通信操作所占據(jù)的比例。而許多并行程序的執(zhí)行都是計(jì)算和通信交替進(jìn)行，在計(jì)算階段，各個(gè)進(jìn)程在處理節(jié)點(diǎn)上獨(dú)立的運(yùn)行，通信階段進(jìn)程則在互連網(wǎng)絡(luò)中執(zhí)行同步和數(shù)據(jù)交換。在通信階段，處理節(jié)點(diǎn)實(shí)際上是處于等待狀態(tài)，不進(jìn)行任何計(jì)算操作，極大地降低了高性能計(jì)算機(jī)的效率，并行程序難以獲得理想的運(yùn)算速度和并行效率。聚合通信性能尤其對(duì)統(tǒng)計(jì)、數(shù)據(jù)挖掘和人工智能領(lǐng)域發(fā)展產(chǎn)生關(guān)鍵影響，因此如何更進(jìn)一步地提高聚合通信性能仍是研究的熱點(diǎn)。

隨著高性能計(jì)算機(jī)越來越復(fù)雜，在通信系統(tǒng)中引入了越來越多的異構(gòu)性［2］。這導(dǎo)致了系統(tǒng)內(nèi)不同層級(jí)的通信性能差異，給聚合通信的優(yōu)化提出了更多的挑戰(zhàn)。目前有很多研究［3］為具體應(yīng)用程序中的同步、廣播或者規(guī)約操作提供了更有效的算法和優(yōu)化。由于聚合通信操作的性能取決于特定通信操作的內(nèi)在因素和基礎(chǔ)環(huán)境的等外在因素，不存在所有場(chǎng)景中都高效的聚合通信操作算法，所以多數(shù)用戶都會(huì)通過多種形式的優(yōu)化策略來滿足其具體應(yīng)用場(chǎng)景的性能需求，諸如研究拓?fù)涓兄木酆贤ㄐ潘惴ㄒ约案鶕?jù)網(wǎng)絡(luò)中實(shí)時(shí)消息的大小進(jìn)行相應(yīng)的算法選擇和處理。在大規(guī)模的聚合通信場(chǎng)景下，合理和有針對(duì)性的算法選擇顯得十分關(guān)鍵。但在目前高性能計(jì)算機(jī)系統(tǒng)內(nèi)不同層級(jí)通信性能變化的條件下，找到一個(gè)合適的優(yōu)化策略也是一項(xiàng)挑戰(zhàn)。

目前聚合通信實(shí)現(xiàn)有三種方式：軟件實(shí)現(xiàn)、硬件實(shí)現(xiàn)和軟硬件結(jié)合的方式。硬件實(shí)現(xiàn)有許多優(yōu)點(diǎn)但是因?yàn)槠鋸?fù)雜度高和經(jīng)濟(jì)投入高的特點(diǎn)，本文中不再具體討論。高性能計(jì)算領(lǐng)域新技術(shù)的發(fā)展給軟硬件開發(fā)提供了更多的支持，給提出高性能的聚合通信方案提供了基礎(chǔ)，使得新技術(shù)在各種系統(tǒng)上的有效集成成為了可能。智能網(wǎng)卡和交換機(jī)對(duì)聚合通信操作的支持使得聚合通信的計(jì)算可以卸載到互連網(wǎng)絡(luò)中，使得計(jì)算和通信同時(shí)進(jìn)行，有效地提高了CPU的使用效率。同時(shí)，也給部署新型的拓?fù)涓兄木酆贤ㄐ潘惴ㄌ峁┝擞欣臈l件。

本文的主要目的是探討聚合通信優(yōu)化技術(shù)的廣度和現(xiàn)狀，并深入了解它們?cè)诟鞣N應(yīng)用領(lǐng)域的適用性和局限性。文章將詳細(xì)介紹聚合通信算法的各種實(shí)現(xiàn)方式，總結(jié)近年來優(yōu)化實(shí)現(xiàn)的典型案例。從而總結(jié)出未來聚合通信優(yōu)化的趨勢(shì)。

2 聚合通信的概念和聚合通信操作算法的簡(jiǎn)介

2.1 聚合通信的概念

聚合通信涉及參與一個(gè)通信操作的多個(gè)進(jìn)程，并且影響所有或一些節(jié)點(diǎn)之間的數(shù)據(jù)傳輸。聚合通信操作包括：廣播（Broadcast）、柵欄同步（Barrier）、規(guī)約（Reduce）、分散（Scatter）和收集（Gather）等。與使用一系列單播消息實(shí)現(xiàn)相同的操作相比，聚合通信操作可以減少延遲和網(wǎng)絡(luò)流量。支持聚合通信的網(wǎng)絡(luò)提供了有效和可擴(kuò)展的聚合操作架構(gòu)，有效地降低了處理器的開銷。

根據(jù)聚合通信的數(shù)據(jù)流的流向，可以將聚合通信操作分為有根的通信操作（Rooted Communication）和無根的通信操作（Non-Rooted Communication）。有 根 的 聚 合 操 作 包 括Broadcast、Gather、Scatter 和Reduce。無根操作則不是源于或者是將消息注入一個(gè)特定的節(jié)點(diǎn)。這類的操作主要有Allgather，AllScatter，AllReduce和Barrier等。

2.2 常見的聚合通信操作算法

2.2.1 廣播（Broadcast）

廣播是許多應(yīng)用中常見的聚合操作，它由根進(jìn)程向其他所有進(jìn)程發(fā)送消息。廣播操作常見的算法有：扁平樹、二叉樹、二項(xiàng)樹、流水線樹、拆分二叉樹、鏈?zhǔn)剿惴?、Van de Geijn 算法［5］。

2.2.2 規(guī)約/分散/收集（Reduce/Scatter/Gather）

這些操作的實(shí)現(xiàn)都緊密跟隨著廣播算法。例如，收集操作可以通過特征或鏈?zhǔn)剿惴▉韺?shí)現(xiàn)，它們通過樹或鏈拓?fù)鋵⒎植际綌?shù)據(jù)向上游傳遞到根進(jìn)程。

2.2.3 柵欄同步（Barrier）

同步是指應(yīng)用程序需要保證所有的進(jìn)程都到達(dá)某個(gè)檢查點(diǎn)后才能繼續(xù)執(zhí)行。有各種各樣的算法可以用于實(shí)現(xiàn)同步操作，該操作可以是有根的操作也可以是無根的。這一類算法有線性同步算法、基于樹的同步算法、蝴蝶算法（迭代算法）。

2.2.4 Allgather/Allreduce/All-to-All

Allgather 是一個(gè)收集的操作，其中每個(gè)進(jìn)程貢獻(xiàn)的數(shù)據(jù)將收集在所有參與的進(jìn)程上。這個(gè)操作的本質(zhì)是非根類的聚合操作。該聚合通信操作使用許多不同類型的算法，一些比較常用的算法有：環(huán)算法、遞歸加倍算法、布魯克（Bruck）算法等。

Allreduce 是一種非根型聚合操作。其交換消息的時(shí)候額外有一個(gè)規(guī)約操作，對(duì)每個(gè)進(jìn)程貢獻(xiàn)的數(shù)據(jù)進(jìn)行相應(yīng)的規(guī)約，最后所有的進(jìn)程都得到該規(guī)約結(jié)果。其算法有環(huán)算法、遞歸加倍算法、向量減半與距離加倍算法［4］、Rabenseifner［5］算法等。

All-to-All 也是一種非根型聚合通信操作，其中每一個(gè)進(jìn)程都有各自唯一的數(shù)據(jù)要發(fā)送到每個(gè)其他進(jìn)程。該操作的算法有布魯克索引算法、RDMA算法等。

2.3 聚合通信算法的分析和選擇

在不同的應(yīng)用場(chǎng)景和網(wǎng)絡(luò)結(jié)構(gòu)中，以及消息大小的不同時(shí)，選擇不同的算法開銷可能存在很大的差異。雖然目前研究領(lǐng)域提出了眾多算法，但是在實(shí)際的應(yīng)用中，往往并非只使用單一的算法。在聚合通信操作中，不存在一個(gè)算法在任何應(yīng)用場(chǎng)景都高效的情況，需要根據(jù)消息的大小，節(jié)點(diǎn)的規(guī)模等來決定。表1 是對(duì)常用的聚合通信算法應(yīng)用的一些歸類總結(jié)。

表1 聚合通信操作算法歸類總結(jié)

2.4 聚合通信算法的發(fā)展

2.1 ～2.3 節(jié)介紹的是傳統(tǒng)算法和基于傳統(tǒng)算法改進(jìn)的一些算法。目前，隨著系統(tǒng)規(guī)模的擴(kuò)大，通信渠道的異構(gòu)性特點(diǎn)更加顯著，如RDMA，NVMe協(xié)議，GPU+CPU 等，這導(dǎo)致了系統(tǒng)內(nèi)不同層級(jí)通信性能的變化。近年來，通信設(shè)備提供商Mellanox公司生產(chǎn)的新一代BlueFieldTM智能網(wǎng)卡，Connect-X 系列交換機(jī)功能不斷強(qiáng)大，可以幫助網(wǎng)絡(luò)中的設(shè)備去實(shí)時(shí)地了解網(wǎng)絡(luò)拓?fù)浣?jīng)有諸多研究成果致力于拓?fù)涓兄?3］的聚合通信算法，它們將從全局上了解整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔?，根?jù)這些全局信息，來有效地分配通信和計(jì)算資源，以避免消息在較慢的信道上傳輸。

3 聚合通信實(shí)現(xiàn)方式的發(fā)展歷程和現(xiàn)狀

聚合通信的實(shí)現(xiàn)方式可以根據(jù)硬件的支持程度劃分為三類：基于軟件方式、基于硬件方式和軟硬件結(jié)合的方式。在本章中，將對(duì)聚合通信的軟件實(shí)現(xiàn)方式和軟硬件結(jié)合實(shí)現(xiàn)方式的方法進(jìn)行介紹。

3.1 軟件實(shí)現(xiàn)

3.1.1 軟件實(shí)現(xiàn)的發(fā)展歷程

軟件聚合通信是當(dāng)前實(shí)現(xiàn)聚合通信操作種類最全，使用最廣的方式。一直被廣泛使用并且功能強(qiáng)大、算法豐富的聚合通信操作接口是MPI［6～7］。

聚合通信操作的軟件實(shí)現(xiàn)是在單播實(shí)現(xiàn)的基礎(chǔ)上結(jié)合前面介紹的算法來實(shí)現(xiàn)的，并且軟件算法具有很好的適應(yīng)性，可以在不需要改變?cè)Z的情況下，根據(jù)實(shí)際的需要采用不同的聚合通信算法。

3.1.2 軟件實(shí)現(xiàn)的優(yōu)勢(shì)分析和潛在局限性

聚合通信操作的軟件實(shí)現(xiàn)是在單播實(shí)現(xiàn)的基礎(chǔ)上結(jié)合前面介紹的算法來實(shí)現(xiàn)的，并且軟件算法具有很好的適應(yīng)性，平臺(tái)通用性很好使用范圍廣泛，幾乎所有的高性能計(jì)算機(jī)系統(tǒng)都使用MPI編程模型進(jìn)行應(yīng)用的開發(fā)和優(yōu)化。它可以在不需要改變?cè)Z的情況下，根據(jù)實(shí)際的需要采用不同的聚合通信算法，在實(shí)際使用的時(shí)候只需要將軟件庫配置好就可以使用。

這種方法雖然使用簡(jiǎn)單，但是仍然有以下缺點(diǎn)：

1）可擴(kuò)展性差；

2）容易受到系統(tǒng)噪聲的影響；

3）降低了計(jì)算和通信的重疊率。

3.2 軟硬件結(jié)合方式實(shí)現(xiàn)

研究表明，雖然軟件實(shí)現(xiàn)的方式有諸多優(yōu)點(diǎn)，但是網(wǎng)絡(luò)的利用效率低下，為了增加資源的利用率，提出了軟硬件結(jié)合的方法。硬件的實(shí)現(xiàn)可以獲得高速度，軟件靈活性強(qiáng)、代價(jià)低。該方法就是希望結(jié)合兩種方式的優(yōu)點(diǎn)來優(yōu)化聚合通信操作。目前主要有兩大類實(shí)現(xiàn)方式，一種是基于網(wǎng)卡（NIC）的實(shí)現(xiàn)方式，一種是基于交換機(jī)（Switch）的方式。

3.2.1 基于NIC的方式實(shí)現(xiàn)

1）實(shí)現(xiàn)動(dòng)機(jī)和基礎(chǔ)

計(jì)算節(jié)點(diǎn)通過網(wǎng)卡連接到網(wǎng)絡(luò)中，網(wǎng)卡最接近終端處理器。因此，可以用于執(zhí)行各種網(wǎng)絡(luò)卸載機(jī)制。帶有處理器的智能網(wǎng)卡可用于對(duì)傳入的網(wǎng)絡(luò)數(shù)據(jù)執(zhí)行復(fù)雜的操作。它們還可以用于卸載一系列聚合通信操作然后網(wǎng)卡繼續(xù)執(zhí)行，從而釋放主處理器以返回計(jì)算。

2）典型實(shí)現(xiàn)

Connect-X［15］系列從Connect-2 NIC 就開始支持簡(jiǎn)單的聚合通信操作卸載。最新的Connect-6產(chǎn)品嵌入了eSwitch，不但支持L2交換，數(shù)據(jù)包分類和虛擬網(wǎng)絡(luò)隧道協(xié)議處理，如VXLAN封裝和解封裝，而且支持諸如包重寫之類的L3 層操作，比如標(biāo)簽推送/彈出之類的MPLS操作?；趀Switch網(wǎng)卡硬件的ASAP2 技術(shù)允許整個(gè)虛擬交換機(jī)的等功能卸載到網(wǎng)卡上，以實(shí)現(xiàn)聚合通信數(shù)據(jù)包處理速度的極大提高，并且顯著降低CPU開銷。

3）優(yōu)缺點(diǎn)總結(jié)

總結(jié)基于NIC實(shí)現(xiàn)的方式有如下優(yōu)點(diǎn)：

（1）數(shù)據(jù)發(fā)送由網(wǎng)卡上的輔助硬件完成，減少發(fā)送延遲，減輕CPU負(fù)擔(dān)，促使計(jì)算和通信重疊。

（2）系統(tǒng)噪聲小。

（3）可擴(kuò)展性較好。

但是，這種方法不能從根本上改變整個(gè)系統(tǒng)聚合通信效率低下的問題。

3.2.2 基于Switch的方式實(shí)現(xiàn)

1）實(shí)現(xiàn)動(dòng)機(jī)和基礎(chǔ)

交換機(jī)構(gòu)成了互連網(wǎng)絡(luò)的主干。高性能網(wǎng)絡(luò)具有點(diǎn)對(duì)點(diǎn)鏈接以最大化性能。交換機(jī)負(fù)責(zé)將數(shù)據(jù)包從源節(jié)點(diǎn)路由到目標(biāo)節(jié)點(diǎn)。由于交換機(jī)處于中心位置，因此聚合通信操作卸載到交換機(jī)中是非常具有吸引力的。一些公司也設(shè)計(jì)了產(chǎn)品來加速聚合通信操作，這些產(chǎn)品的目的是將處理機(jī)端的通信和簡(jiǎn)單計(jì)算工作卸載到交換機(jī)端，以此來解決軟件聚合通信的可擴(kuò)展性問題，同時(shí)提高計(jì)算與通信的重疊率和屏蔽系統(tǒng)噪聲。

2）典型的實(shí)現(xiàn)和分析

（1）FCA［8］

Voltaire（現(xiàn)已與Mellanox 合并）的Fabric Channel Accelerator技術(shù)，簡(jiǎn)稱FCA。FCA是一個(gè)軟件插包，已經(jīng)集成到MPI 庫上。并且，已經(jīng)實(shí)現(xiàn)了映射底層網(wǎng)絡(luò)拓?fù)涞骄酆纤惴ǖ哪芰Γ沟镁酆贤ㄐ挪僮髟谒惴▽幽軌颢@取物理拓?fù)浣Y(jié)構(gòu)的信息，并根據(jù)這些信息構(gòu)建拓?fù)涓兄木酆贤ㄐ艠洹Ｔ诰酆贤ㄐ艠渲?，一旦聚合通信樹的父?jié)點(diǎn)知道了最終結(jié)果，則FCA 僅發(fā)送一條消息，就可以利用交換機(jī)硬件將結(jié)果廣播到其他過程。FCA 還提供了通信隔離專用虛擬網(wǎng)絡(luò)（VLane）將聚合通信流量和交換中的其余流量隔離，從而消除與其他類型流量的爭(zhēng)用［11］。

圖1 FCA整體架構(gòu)示意圖

（2）SHArP（Scalable Hierarchical Aggregation Protocol）

SHArP［9］是Mellanox 公司在2016 年發(fā)布的卸載聚合通信到網(wǎng)絡(luò)中的協(xié)議。2019年3月，Mellanox 宣布其采用“可擴(kuò)展分層聚合和歸約協(xié)議”SHArP 技術(shù)的HDR 200G InfiniBand 創(chuàng)造了新的性能記錄，使深度學(xué)習(xí)操作性能提高了一倍。

SHArP 提供了描述數(shù)據(jù)規(guī)約的抽象。實(shí)現(xiàn)了消息在遍歷網(wǎng)絡(luò)時(shí)操縱數(shù)據(jù)，最小化數(shù)據(jù)移動(dòng)距離。

3）優(yōu)缺點(diǎn)總結(jié)

（1）可以在交換機(jī)端口復(fù)制數(shù)據(jù)包，從而減少網(wǎng)絡(luò)流量［10］。

（2）提供了基于硬件的可靠機(jī)制來確保廣播分組到達(dá)其目的地。

（3）計(jì)算和通信的重疊率提高。

（4）可以創(chuàng)建拓?fù)涓兄木酆贤ㄐ艠鋪慝@得更低的聚合通信操作延遲。

目前，基于Switch 的卸載聚合通信操作的這種實(shí)現(xiàn)方式還在進(jìn)一步研究和部署中。

4 結(jié)語

影響聚合通信性能的因素有很多，主要有以下幾個(gè)方面：集群熱點(diǎn)和擁塞，算法對(duì)物理拓?fù)洳幻舾?，操作系統(tǒng)的噪聲。根據(jù)前面三章的介紹，需要不斷地采用創(chuàng)新的架構(gòu)來優(yōu)化聚合通信操作。在算法上，繼續(xù)開發(fā)拓?fù)涿舾械木酆贤ㄐ潘惴?，使得能夠充分利用網(wǎng)絡(luò)的全局信息來調(diào)度聚合通信；在實(shí)現(xiàn)上，不斷提升計(jì)算和通信的重疊率，使得數(shù)據(jù)在移動(dòng)的過程中被處理，減輕CPU 負(fù)擔(dān)，降低系統(tǒng)噪聲。

未來一段時(shí)間內(nèi)，該領(lǐng)域的研究主要集中在通過利用先進(jìn)的多核架構(gòu)和網(wǎng)絡(luò)功能來增強(qiáng)軟件設(shè)計(jì)降低聚合操作的延遲；利用先進(jìn)的智能網(wǎng)卡［14］和交換機(jī)，設(shè)計(jì)和改進(jìn)允許應(yīng)用程序?qū)崿F(xiàn)計(jì)算與通信重疊的非阻塞類型的聚合通信操作算法；探索檢測(cè)系統(tǒng)拓?fù)涞奶娲桨福_發(fā)新型拓?fù)涓兄酆贤ㄐ潘惴?，最終使得并行應(yīng)用程序獲得更快的運(yùn)算速度。