針對天河2號的一種嵌套剖分負(fù)載平衡算法

劉 旭 楊 章 楊 揚(yáng)

1(計(jì)算物理重點(diǎn)實(shí)驗(yàn)室(北京應(yīng)用物理與計(jì)算數(shù)學(xué)研究所) 北京 100094)2(北京應(yīng)用物理與計(jì)算數(shù)學(xué)研究所高性能計(jì)算中心 北京 100094)(liu_xu@iapcm.ac.cn)

當(dāng)前，超級計(jì)算機(jī)，特別是億億次計(jì)算機(jī)，呈現(xiàn)出海量并行、多級嵌套的數(shù)據(jù)傳輸系統(tǒng)和異構(gòu)加速的體系結(jié)構(gòu)特征：

1) 海量并行.現(xiàn)在的億億次計(jì)算機(jī)都具有數(shù)十萬核，例如，神威太湖之光具有超過1 000萬核；若包括至強(qiáng)融核協(xié)處理器(many integrated core， MIC)，天河2號具有超過3百萬核.

2) 多級嵌套的數(shù)據(jù)傳輸系統(tǒng).超級計(jì)算機(jī)的數(shù)據(jù)傳輸系統(tǒng)具有很深的層次結(jié)構(gòu)，以天河2號為例，可以分為“主干交換機(jī)-分支交換機(jī)-葉子交換機(jī)-遠(yuǎn)端內(nèi)存-本地內(nèi)存-多級緩存系統(tǒng)”.在這些級之間，數(shù)據(jù)傳輸?shù)钠骄鶐捑哂兄鸺夁f增的趨勢，延遲具有逐級遞減的趨勢，每級之間一般具有一倍至幾倍的差異.在多級嵌套的數(shù)據(jù)傳輸系統(tǒng)中，數(shù)據(jù)傳輸?shù)拈_銷不但與數(shù)據(jù)傳輸量和數(shù)據(jù)傳輸次數(shù)相關(guān)，還與數(shù)據(jù)傳輸?shù)耐ㄐ沛溌废嚓P(guān).

3) 異構(gòu)加速不可忽視.為了在較低的功耗下獲得較好的計(jì)算性能，很多超級計(jì)算機(jī)采用了異構(gòu)加速的技術(shù).據(jù)文獻(xiàn)[1]統(tǒng)計(jì)，在全球最快的10臺超級計(jì)算機(jī)中，神威太湖之光使用了主從核結(jié)構(gòu)，天河2號使用了MIC加速，Titan和Piz Daint使用了GPU加速.特別地，我國排名前5的超級計(jì)算機(jī)中，神威太湖之光采用了主從核結(jié)構(gòu)，2臺采用了CPUMIC加速的結(jié)構(gòu)，2臺采用了CPUGPU加速的結(jié)構(gòu).異構(gòu)超級計(jì)算機(jī)節(jié)點(diǎn)內(nèi)的體系結(jié)構(gòu)有2點(diǎn)顯著的變化：①節(jié)點(diǎn)內(nèi)CPU核和加速器之間(或主從核)的計(jì)算速度出現(xiàn)了差異；②CPU核和加速器之間(或主從核)的訪存特征出現(xiàn)了差異，且節(jié)點(diǎn)內(nèi)的通信出現(xiàn)了與節(jié)點(diǎn)間通信相似的特性(見圖1).

Fig. 1 Intra-node bandwidth distribution of Tianhe-2圖1 天河2號節(jié)點(diǎn)內(nèi)帶寬分布

億億次超級計(jì)算機(jī)的上述3個(gè)特征，給負(fù)載平衡算法提出了3個(gè)要求：

1) 低算法復(fù)雜度.一方面，超級計(jì)算機(jī)具有海量的并行度;另一方面，應(yīng)用模擬問題也具有海量的未知量規(guī)模.因此，負(fù)載平衡算法面對的問題規(guī)模也非常巨大.如果將高算法復(fù)雜度的負(fù)載平衡算法用于解決動態(tài)負(fù)載平衡問題，其負(fù)載平衡算法執(zhí)行開銷就會接近甚至超過數(shù)值計(jì)算時(shí)間，從而變得不可接受.

2) 適應(yīng)多級嵌套的數(shù)據(jù)傳輸系統(tǒng).在多級嵌套的數(shù)據(jù)傳輸系統(tǒng)中，數(shù)據(jù)傳輸速度與通信鏈路相關(guān).傳統(tǒng)的負(fù)載平衡算法只考慮了通信量，沒有考慮通信鏈路，因此，即使能夠最小化數(shù)據(jù)傳輸量，也不能最小化數(shù)據(jù)傳輸開銷.

3) 支撐異構(gòu)協(xié)同計(jì)算.對于復(fù)雜應(yīng)用來說，要想充分利用計(jì)算資源，就需要做好異構(gòu)協(xié)同計(jì)算.但是，在異構(gòu)協(xié)同計(jì)算中，由于CPU與異構(gòu)加速器之間計(jì)算速度等性能特征存在很大差異，因此會造成即使在同構(gòu)計(jì)算中自然平衡的應(yīng)用，此時(shí)也需要處理復(fù)雜的負(fù)載平衡問題.另外，對于天河2號而言，其MIC加速器與遠(yuǎn)程CPU或其他MIC加速器的通信鏈路性能很差，因此負(fù)載平衡算法必須規(guī)避MIC加速器的遠(yuǎn)程通信.

面向億億次超級計(jì)算機(jī)，針對結(jié)構(gòu)網(wǎng)格并行應(yīng)用的異構(gòu)協(xié)同計(jì)算，我們設(shè)計(jì)了一種3級嵌套負(fù)載平衡算法，并且針對天河2號進(jìn)行了特殊處理，使得該算法能夠滿足上述3個(gè)要求.

1 相關(guān)研究與問題分析

1.1 通過并行化降低負(fù)載平衡算法復(fù)雜度

面對數(shù)百上千萬核的并行度，即便是線性復(fù)雜度的串行負(fù)載平衡算法都難以滿足實(shí)際應(yīng)用的需求，而并行化是最主要的降低負(fù)載平衡算法復(fù)雜度的方法.

明尼蘇達(dá)大學(xué)的Karypis等人[2-3]，Sandia國家實(shí)驗(yàn)室的Boman等人[4]，波爾多國立高等電子、信息與無線電通訊學(xué)校的Pellegrini 等人[5]設(shè)計(jì)并實(shí)現(xiàn)了并行多層次圖剖分方法，提升了負(fù)載剖分的速度.這些工作分別集成到了軟件ParMetis[6]，Zoltan[7]，pt-scotch[8]中.Menon等人[9]以Charm++為平臺，研究了基于統(tǒng)計(jì)學(xué)的并行擴(kuò)散式負(fù)載平衡算法，在保持算法高可擴(kuò)展性的同時(shí)改進(jìn)了負(fù)載調(diào)整的質(zhì)量.Lawrence Livermore國家實(shí)驗(yàn)室的Gunney等人[10]提出了一種并行擴(kuò)散式負(fù)載平衡算法(cascade partitioning algorithm)，算法集成到SAMRAI框架，能夠支撐自適應(yīng)計(jì)算的示例程序在Sequoia上強(qiáng)擴(kuò)展到150萬核.

總體而言，由于擴(kuò)散式負(fù)載平衡算法主要使用局部操作，因此其并行可擴(kuò)展性較好，可以擴(kuò)展到上百萬核.圖剖分類和空間填充曲線類的負(fù)載平衡算法由于具有一些非局部操作，因此并行可擴(kuò)展性較差.但是,上述算法未考慮異構(gòu)體系結(jié)構(gòu)，還不能適應(yīng)異構(gòu)協(xié)同計(jì)算.

1.2 匹配多級嵌套的數(shù)據(jù)傳輸系統(tǒng)負(fù)載平衡算法

Zheng[11]設(shè)計(jì)了一種多級的負(fù)載平衡算法，該算法使用一棵樹管理所有的核，樹的每個(gè)葉子節(jié)點(diǎn)對應(yīng)1個(gè)核，算法將計(jì)算任務(wù)沿著樹的邊從過載核調(diào)整到輕載核，從而達(dá)到負(fù)載平衡.特別地，該樹的結(jié)構(gòu)與計(jì)算機(jī)的體系結(jié)構(gòu)相匹配.利用這種匹配性，負(fù)載平衡算法可以適應(yīng)多級嵌套的數(shù)據(jù)傳輸系統(tǒng)，減小數(shù)據(jù)傳輸開銷.此外，算法自根向樹葉執(zhí)行，不同子樹的負(fù)載平衡可以并行執(zhí)行，因此，算法具有較好的并行可擴(kuò)展性.

南里奧格蘭德聯(lián)邦大學(xué)的Pilla等人[12]和法國國家信息與自動化研究所的Jeannot等人[13]對上述算法進(jìn)行了改造，重點(diǎn)減小了數(shù)據(jù)傳輸?shù)拈_銷.但是，這2種算法時(shí)間復(fù)雜度過高，不適用于大規(guī)模問題.

1.3 支撐異構(gòu)協(xié)同計(jì)算的負(fù)載平衡算法

Fig. 2 Illustration of the inner-outer subdomain partitioning method: one MIC and one CPU圖2 Inner-outer subdomain剖分方法

薛巍、楊超和盧宇彤等人[14-15]對CPUMIC異構(gòu)協(xié)同計(jì)算的負(fù)載平衡算法進(jìn)行了深入的研究.特別地，針對MIC加速器與遠(yuǎn)程CPU或其他MIC加速器的通信鏈路性能差的問題，提出了inner-outer subdomain partition方法.如圖2所示.該方法使用2級剖分，第1級以MIC加速器及其本地CPU為單位剖分計(jì)算區(qū)域，第2級進(jìn)一步將每個(gè)子區(qū)域剖分為內(nèi)部區(qū)域和邊界區(qū)域，MIC加速器分配內(nèi)部區(qū)域，CPU分配邊界區(qū)域.該方法避免了MIC加速器與遠(yuǎn)程CPU或其他MIC加速器的通信，提升了通信性能.

但是，目前該方法只能適用于負(fù)載均勻分布的應(yīng)用，對于負(fù)載非均勻分布的應(yīng)用(如粒子類模擬)，還不能適應(yīng).

1.4 已有負(fù)載平衡算法的問題

這些改進(jìn)的算法針對特定的優(yōu)化目標(biāo)取得了明顯的進(jìn)展.但是在實(shí)際億億次計(jì)算機(jī)上，實(shí)際應(yīng)用的負(fù)載平衡問題往往是復(fù)雜的多約束多目標(biāo)優(yōu)化問題，不但要滿足低算法復(fù)雜度、匹配數(shù)據(jù)傳輸系統(tǒng)和支撐異構(gòu)協(xié)同計(jì)算，還要能適應(yīng)非均勻的負(fù)載分布、復(fù)雜的計(jì)算區(qū)域以及滿足應(yīng)用的特殊約束[16-17].例如，在使用PIC方法進(jìn)行的慣性約束核聚變激光等離子體相互作用模擬中，粒子在空間中非均勻分布(如圖3，粒子分布于圖中圓椎體部分)，造成計(jì)算負(fù)載在空間中的非均勻分布，負(fù)載平衡算法必須能夠處理負(fù)載非均勻分布的問題.然而，現(xiàn)有的針對億億次協(xié)同計(jì)算設(shè)計(jì)的負(fù)載平衡算法還不能解決上述問題.

Fig. 3 The non-uniform distribution of particles in a laser plasma interaction simulation圖3 激光等離子體相互作用模擬中的非均勻粒子分布

2 支撐異構(gòu)協(xié)同計(jì)算的3級嵌套負(fù)載平衡算法

2.1 設(shè)計(jì)目標(biāo)

為了支撐異構(gòu)協(xié)同計(jì)算，本文設(shè)計(jì)的負(fù)載平衡算法需要滿足2個(gè)目標(biāo)：

1) 適應(yīng)億億次計(jì)算機(jī)，做到低算法復(fù)雜度、適應(yīng)多級嵌套的數(shù)據(jù)傳輸系統(tǒng)和支撐異構(gòu)協(xié)同計(jì)算；

2) 適應(yīng)實(shí)際應(yīng)用，能夠處理非均勻負(fù)載分布.

2.2 3級嵌套的負(fù)載平衡算法框架

當(dāng)計(jì)算機(jī)不包含加速器時(shí)，3級嵌套的負(fù)載平衡算法框架執(zhí)行流程如下(見圖4所示)：

步驟1. 計(jì)算節(jié)點(diǎn)層負(fù)載平衡(串行執(zhí)行).

步驟2. CPU層負(fù)載平衡(并行執(zhí)行).

步驟3. CPU核層負(fù)載平衡(并行執(zhí)行).

該算法框架與文獻(xiàn)[11]比較接近，利用步驟2～3的并行執(zhí)行，降低整體的算法復(fù)雜度.同時(shí)，該框架在步驟1中采用極小化數(shù)據(jù)通信的算法、步驟2中采用極小化遠(yuǎn)程訪存的算法，從而適應(yīng)多級嵌套數(shù)據(jù)傳輸系統(tǒng).與文獻(xiàn)[11]不同，該算法框架直接與最典型的3級嵌套體系結(jié)構(gòu)相匹配，并且在計(jì)算節(jié)點(diǎn)內(nèi)采用共享存儲線程并行，從而進(jìn)一步提升執(zhí)行性能.基于該算法框架，剩下的核心問題就是處理異構(gòu)協(xié)同計(jì)算.

Fig. 4 Illustration of the nested partitioning load balancing algorithm圖4 3級嵌套的負(fù)載平衡算法框架流程示意圖

2.3 適應(yīng)計(jì)算能力差異

異構(gòu)協(xié)同計(jì)算的首要要求是適應(yīng)計(jì)算能力的差異.基于2.2節(jié)的3級嵌套負(fù)載平衡算法框架，在流程的步驟1～3分別嵌入適應(yīng)計(jì)算能力差異的剖分算法，則該流程就能夠適應(yīng)異構(gòu)協(xié)同計(jì)算.此時(shí)，每層剖分算法需要求解的問題為：給定加速器與CPU的計(jì)算速度比，給定計(jì)算區(qū)域及其上的負(fù)載分布，求計(jì)算區(qū)域的剖分及其到CPU、加速器的映射.我們基于貪婪策略設(shè)計(jì)了算法1.

算法1. 異構(gòu)協(xié)同計(jì)算的貪婪子區(qū)域剖分算法.

輸入：計(jì)算區(qū)域集合B、計(jì)算資源集合P(包括計(jì)算速度的比值)；

輸出：子區(qū)域集合B′、B′到P的映射M.

步驟1. 計(jì)算每個(gè)計(jì)算資源應(yīng)分到的計(jì)算量，初始化剩余的計(jì)算資源集合L=P；

步驟2. 初始化未分配的計(jì)算區(qū)域集合Q=B；

步驟3. 根據(jù)貪婪原則分配計(jì)算區(qū)域；

WhileQ≠?

① 從Q中取出最大的子區(qū)域b，從L中取出剩余計(jì)算能力最多的元素c；

② Ifb>cthen

將b剖分成若干子區(qū)域b0～bn，其中b0是計(jì)算量不小于c的最小子區(qū)域，b0分配給c，更新B′和M，將b1～bn放回Q；

Else

將b分配給c，更新B′和M；

End If

③ 更新c，加入L；

End While

步驟4. ReturnB′和M.

MIC計(jì)算能力較強(qiáng)，且適合處理單塊計(jì)算區(qū)域.如果要保證1個(gè)MIC僅分配1個(gè)子區(qū)域，則在步驟3③增加：如果c是加速器，則不再加入L即可.從步驟3可以看出，算法優(yōu)先將較大的整塊區(qū)域分配給計(jì)算能力強(qiáng)的MIC，滿足了MIC的特點(diǎn).從步驟3②可以看出，算法能夠定量地根據(jù)MIC與CPU的計(jì)算速度比值，分配不同大小的計(jì)算區(qū)域.

Fig. 5 Domain partitioning result produced by algorithm 1 for the case of three MICs and two CPUs圖5 3塊MIC和2塊CPU時(shí)算法1得到的子區(qū)域剖分

圖5表現(xiàn)了算法1在天河2號的1個(gè)節(jié)點(diǎn)上執(zhí)行的效果，其中不同顏色表示MIC或者不同CPU核上分配的子區(qū)域.從圖5中可以看出，算法1能夠根據(jù)計(jì)算速度的不同分配不同計(jì)算量的子區(qū)域.

算法1具有一個(gè)額外的功能：能夠處理計(jì)算節(jié)點(diǎn)具有不同計(jì)算能力的問題.(該功能主要為了解決由于部件老化造成的計(jì)算節(jié)點(diǎn)間存在計(jì)算能力不同，從而引發(fā)的負(fù)載不平衡問題.)圖6表現(xiàn)了算法1在1個(gè)具有32個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)分別具有0～3個(gè)MIC的計(jì)算環(huán)境上執(zhí)行的效果，其中不同顏色表示不同節(jié)點(diǎn)分配的子區(qū)域.從中可以看出，算法1能夠根據(jù)不同節(jié)點(diǎn)具有MIC數(shù)量的不同分配不同計(jì)算量的子區(qū)域.

Fig. 6 Gray-scale illustration of partition assignment over 32 nodes圖6 32節(jié)點(diǎn)情況下進(jìn)程的子計(jì)算區(qū)域分布灰度圖

2.4 規(guī)避MIC的遠(yuǎn)程通信

對于天河2號來說，異構(gòu)協(xié)同計(jì)算還需要規(guī)避MIC的遠(yuǎn)程通信瓶頸.基于2.2節(jié)的3級嵌套負(fù)載平衡算法框架，在步驟3嵌入規(guī)避MIC遠(yuǎn)程通信的剖分算法，則該流程就能夠適應(yīng)異構(gòu)協(xié)同計(jì)算.為此，推廣了文獻(xiàn)[14-15]中的inner-outer subdomain partitioning算法，設(shè)計(jì)了算法2，使之能夠適應(yīng)負(fù)載非均勻分布的應(yīng)用.

算法2. 推廣的內(nèi)外區(qū)域剖分算法.

輸入：計(jì)算區(qū)域集合B(包括影像區(qū)寬度)、計(jì)算資源集合P(包括計(jì)算速度的比值)；

輸出：子區(qū)域集合B′、B′到P的映射M.

步驟1. 計(jì)算每個(gè)計(jì)算資源應(yīng)分到的計(jì)算量，初始化MIC計(jì)算資源集合L；

步驟2. 初始化未分配的計(jì)算區(qū)域集合Q=B；

步驟3. 根據(jù)inner-outer subdomain算法為MIC分配計(jì)算區(qū)域；

WhileL≠?

① 從L中取出計(jì)算能力最強(qiáng)的元素c，計(jì)算Q的內(nèi)部區(qū)域，從中取出適當(dāng)?shù)淖訁^(qū)域分給c，更新B′和M；

End While

步驟4. 使用算法1分配剩余計(jì)算區(qū)域到CPU，更新B′和M；

步驟5. ReturnB′和M.

從步驟3①可以看出，算法能夠保證MIC僅分配當(dāng)前的內(nèi)部計(jì)算區(qū)域，因此MIC可以避免遠(yuǎn)程通信.圖7表現(xiàn)了算法2在天河2號的1個(gè)節(jié)點(diǎn)上執(zhí)行的效果，其中不同顏色表示MIC或者不同CPU核上分配的子區(qū)域.在該算例中，影像區(qū)寬度為1.從中可以看出，算法2不但能夠根據(jù)計(jì)算速度的不同分配不同計(jì)算量的子區(qū)域，而且可以保證MIC避免遠(yuǎn)程通信.

Fig. 7 Domain partitioning result produced by algorithm 2 for the case of three MICs and two CPUs圖7 3塊MIC和2塊CPU時(shí)算法2得到的子區(qū)域剖分

3 應(yīng)用效果

我們設(shè)計(jì)了3組測試驗(yàn)證算法的效果.第1組測試使用模型問題和模型計(jì)算環(huán)境，統(tǒng)計(jì)負(fù)載平衡算法的模型負(fù)載平衡效率，檢測理想環(huán)境下負(fù)載平衡算法的負(fù)載平衡效果.第2組測試使用JEMS-TD應(yīng)用程序，在天河2號上執(zhí)行，比較應(yīng)用程序使用算法1和算法2的通信時(shí)間，測試算法2規(guī)避MIC遠(yuǎn)程通信的效果.第3組測試使用JEMS-TD，LAP3D，LARED-S，LARED-P，MOASP 5個(gè)應(yīng)用程序，在天河2號上執(zhí)行，統(tǒng)計(jì)程序執(zhí)行的并行效率，考察負(fù)載平衡算法的整體效果.

3.1 異構(gòu)計(jì)算環(huán)境下的負(fù)載平衡效率計(jì)算公式

為了評價(jià)負(fù)載平衡算法的效果，需要一個(gè)能夠從平衡性方面評價(jià)負(fù)載平衡算法執(zhí)行結(jié)果的指標(biāo).在同構(gòu)計(jì)算環(huán)境下，評價(jià)平衡性的指標(biāo)主要有負(fù)載平衡效率、負(fù)載不平衡因子等[18].這些指標(biāo)可以互相轉(zhuǎn)換，沒有本質(zhì)區(qū)別.

在同構(gòu)計(jì)算環(huán)境下，負(fù)載平衡效率指平均計(jì)算時(shí)間與最大計(jì)算時(shí)間的比值，記為LBE.負(fù)載平衡效率滿足2個(gè)性質(zhì)：1)屬于(0,1]區(qū)間的實(shí)數(shù)；2)在僅考慮負(fù)載平衡因素，不考慮通信開銷等因素的情況下，負(fù)載平衡效率越高，計(jì)算時(shí)間越短.對于負(fù)載平衡算法而言，其執(zhí)行效果受限于輸入負(fù)載模型的精度.因此，根據(jù)負(fù)載模型計(jì)算出的模型負(fù)載平衡效率可以更好地反映負(fù)載平衡算法的效果.模型負(fù)載平衡效率

(1)

其中l(wèi)i表示核i分到的負(fù)載.

為了在異構(gòu)計(jì)算環(huán)境中，保證2個(gè)性質(zhì)繼續(xù)成立，將式(1)推廣為

(2)

3.2 模型負(fù)載平衡效率測試

測試計(jì)算區(qū)域是一個(gè)1600×320的2維區(qū)域.模型計(jì)算環(huán)境有3種：1)純CPU；2)每個(gè)節(jié)點(diǎn)3個(gè)MIC；3)每個(gè)節(jié)點(diǎn)具有0～3個(gè)MIC(數(shù)量隨機(jī)生成).其中每個(gè)節(jié)點(diǎn)有2個(gè)CPU，CPU具有12核，MIC卡與CPU核的計(jì)算速度之比為12∶1.測試使用算法2.

圖8給出了算法將計(jì)算區(qū)域分到32個(gè)節(jié)點(diǎn)的結(jié)果，實(shí)線代表剖分.從圖8中可以看出MIC和CPU分到的計(jì)算區(qū)域大小不同.此外，圖8中灰度表示進(jìn)程號，可以看出，相鄰區(qū)域進(jìn)程號接近(灰度接近的進(jìn)程號也接近)，避免了遠(yuǎn)距離通信.

Fig. 8 Partition assignment over 32 nodes圖8 32節(jié)點(diǎn)的子計(jì)算區(qū)域剖分

圖9顯示了算法在1～32個(gè)節(jié)點(diǎn)上執(zhí)行得到的負(fù)載平衡效率.首先，3條負(fù)載平衡效率曲線都高于0.9，表明算法可以保證較好的負(fù)載平衡.其次，點(diǎn)線(3MIC環(huán)境)與實(shí)線(全CPU環(huán)境)基本相當(dāng)，同時(shí)虛線略低于點(diǎn)線和實(shí)線，表明算法對異構(gòu)協(xié)同計(jì)算的支持效果接近同構(gòu)計(jì)算，而且能夠適應(yīng)計(jì)算機(jī)的節(jié)點(diǎn)之間具有差異的情況.

Fig. 9 Model load balance efficiency for different number of nodes圖9 模型負(fù)載平衡效率

3.3 規(guī)避MIC遠(yuǎn)程通信測試

JEMS-TD是一個(gè)3維時(shí)域全波電磁模擬程序,使用時(shí)域有限差分(FDTD)方法求解Maxwell 方程組,對包含多種材料的復(fù)雜模型的輻射和散射問題進(jìn)行全波電磁模擬，獲得時(shí)域近場和遠(yuǎn)場電磁數(shù)據(jù).測試計(jì)算區(qū)域是一個(gè)600×400×400的3維區(qū)域.測試在天河2號上進(jìn)行，每個(gè)節(jié)點(diǎn)具有3個(gè)MIC，2個(gè)CPU，每個(gè)CPU具有12核.測試中每個(gè)計(jì)算節(jié)點(diǎn)用滿了195個(gè)CPU核和MIC核.對于該程序，MIC卡與CPU核的計(jì)算速度之比約為12∶1.

由于時(shí)間所限，我們只進(jìn)行了中等規(guī)模的測試.圖10顯示了應(yīng)用程序的通信時(shí)間，其中實(shí)線表示使用算法1的通信時(shí)間，虛線表示使用算法2的通信時(shí)間).從圖10中可以看出，使用算法2普遍可以比算法1降低通信時(shí)間.32個(gè)節(jié)點(diǎn)時(shí)，使用算法2比算法1降低約50%的通信時(shí)間.

3.4 并行效率驗(yàn)證

選取了5個(gè)典型應(yīng)用進(jìn)行了并行效率的測試.除了3.3節(jié)介紹的JEMS-TD外，LAP3D是一個(gè)3維激光等離子體相互作用成絲不穩(wěn)定性模擬程序，LARED-S是一個(gè)3維輻射流體力學(xué)界面不穩(wěn)定性模擬程序，LARED-P是一個(gè)3維激光等離子體相互作用粒子模擬程序，MOASP是一個(gè)經(jīng)典分子動力學(xué)模擬程序.測試在天河2號上進(jìn)行，每個(gè)計(jì)算節(jié)點(diǎn)用滿了195個(gè)CPU核和MIC核.測試使用算法2，采用弱可擴(kuò)展性測試，由于篇幅限制，這里不列出測試模型的具體信息.

表1給出了5個(gè)程序的并行效率.其中，由于時(shí)間所限，LARED-S和MOASP沒有測到93.6萬核的數(shù)據(jù).從測試結(jié)果看，本文的負(fù)載平衡算法成功支撐了5個(gè)典型應(yīng)用高效擴(kuò)展到數(shù)十萬到近百萬核，并行效率最高可達(dá)80%.

Table 1 Parallel Efficiency of Five Applications Using CPUMIC Hybrid Computing表1 5個(gè)應(yīng)用程序異構(gòu)協(xié)同計(jì)算的并行效率

Table 1 Parallel Efficiency of Five Applications Using CPUMIC Hybrid Computing表1 5個(gè)應(yīng)用程序異構(gòu)協(xié)同計(jì)算的并行效率

NumberofCoresParallelEfficiency∕%JEMS?TDLAP3DLARED?SLARED?PMOASP195100100100100100780929297908415609491958992624092869387651248092819285604992089698984481996809079918241399360846289794379872080548479936000805378

4 結(jié)束語

面向億億次超級計(jì)算機(jī)，針對結(jié)構(gòu)網(wǎng)格并行應(yīng)用的異構(gòu)協(xié)同計(jì)算，通過組合3級嵌套負(fù)載平衡算法框架、貪婪剖分算法和內(nèi)外子區(qū)域剖分算法，我們設(shè)計(jì)了一種負(fù)載平衡算法，能夠同時(shí)滿足低算法復(fù)雜度、適應(yīng)多級嵌套的數(shù)據(jù)傳輸系統(tǒng)和支撐異構(gòu)協(xié)同計(jì)算3方面要求.模型測試表明，算法可以達(dá)到90%以上的負(fù)載平衡效率.天河2號上32個(gè)節(jié)點(diǎn)的測試表明，算法能夠保證通信開銷較小.5個(gè)典型應(yīng)用在天河2號上最大93.6萬核的測試表明，算法能夠支撐應(yīng)用高效擴(kuò)展，并行效率最高可達(dá)80%.

本文的算法需要輸入CPU與加速器的計(jì)算速度比值，但是對于實(shí)際應(yīng)用，如何得到該比值也是一個(gè)需要研究的問題，在下一步的工作中，我們將在這個(gè)方面開展研究.此外，我們準(zhǔn)備移植和實(shí)現(xiàn)更多異構(gòu)協(xié)同負(fù)載平衡算法，進(jìn)行更加充分的對比和分析.

[1]Dongarra J. TOP500[EB/OL]. Knoxville: University of Tennessee, 2016-11 [2017-01-13]. https://www.top500.org/lists/2016/11/

[2]Karypis G, Kumar V. Parallel multilevel k-way partitioning scheme for irregular graphs[C] //Proc of the 1996 ACM/IEEE Conf on Supercomputing (Supercomputing’96). Los Alamitos, CA: IEEE Computer Society, 1996: No.35

[3]Lasalle D, Karypis G. Multi-threaded graph partitioning[C] //Proc of the 27th IEEE Int Symp on Parallel and Distributed Processing (IPDPS’13). Los Alamitos, CA: IEEE Computer Society, 2013: 225-236

[4]Devine K D, Boman E G, Heaphy R T, et al. Parallel hypergraph partitioning for scientific computing[C] //Proc of the 20th Int Conf on Parallel and Distributed Processing (IPDPS’06). Los Alamitos, CA: IEEE Computer Society, 2006: 124-124

[5]Chevalier C, Pellegrini F. PT-Scotch: A tool for efficient parallel graph ordering[J]. Parallel Computing, 2008, 34(6): 318-331

[6]Karypis G. ParMETIS[CP/OL]. Twin Cities: University of Minnesota, (2013-03-30) [2017-01-13]. http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview

[7]Boman E. Zoltan[CP/OL]. Albuquerque: Sandia National Laboratories, 2016-01 [2017-01-13]. http://www.cs.sandia.gov/zoltan/

[8]Pellegrini F. PT-SCOTCH[CP/OL]. Bordeaux: INRIA, (2012-12-02) [2017-01-13]. http://www.labri.fr/perso/pelegrin/scotch

[9]Menon H, Kalé L. A distributed dynamic load balancer for iterative applications[C] //Proc of the Int Conf on High Performance Computing, Networking, Storage and Analysis (SC’13). New York: ACM, 2013: No.15

[10]Gunney B T N, Anderson R W. Advances in patch-based adaptive mesh refinement scalability[J]. Journal of Parallel & Distributed Computing, 2016, 89(C): 65-84

[11]Zheng G, Bhatelé A, Meneses E, et al. Periodic hierarchical load balancing for large supercomputers[J]. Int Journal of High Performance Computing Applications, 2011, 25(4): 371-385

[12]Pilla L L, Ribeiro C P, Coucheney P, et al. A topology-aware load balancing algorithm for clustered hierarchical multi-core machines[J]. Future Generation Computer Systems, 2014, 30(1): 191-201

[13]Jeannot E, Mercier G, Tessier F. Topology and affinity aware hierarchical and distributed load-balancing in Charm++[C] //Proc of the 1st Workshop on Optimization of Communication in HPC (COM-HPC’16). Piscataway, NJ: IEEE, 2016: 63-72

[14]Xue Wei, Yang Chao, Fu Haohuan, et al. Enabling and scaling a global shallow-water atmospheric model on Tianhe-2[C] //Proc of the 28th IEEE Int Symp on Parallel and Distributed Processing (IPDPS’14). Los Alamitos, CA: IEEE Computer Society, 2014: 745-754

[15]Xue Wei, Yang Chao, Fu Haohuan, et al. Ultra-scalable CPU-MIC acceleration of mesoscale atmospheric modeling on Tianhe-2[J]. IEEE Trans on Computers, 2015, 64(8): 2382-2393

[16]Li Leisheng, Wang Chaowei, Ma Zhitao, et al. petaPar: A scalable and fault tolerant petascale free mesh simulation system[J]. Journal of Computer Research & Development, 2015, 52(4): 823-832 (in Chinese)(黎雷生, 王朝尉, 馬志濤, 等. 千萬億次可擴(kuò)展可容錯自由網(wǎng)格數(shù)值模擬系統(tǒng)[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(4): 823-832)

[17]Cao Xiaolin, Zhang Aiqing, Mo Zeyao. Parallel computation for particle simulations based on object-oriented design[J]. Journal of Computer Research & Development, 2007, 44(10): 1647-1651 (in Chinese)(曹小林, 張愛清, 莫則堯. 基于面向?qū)ο蟮牧Ｗ宇惸M并行計(jì)算研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(10): 1647-1651)

[18]Willebeeklemair M H, Reeves A P. Strategies for dynamic load balancing on highly parallel computers[J]. IEEE Trans on Parallel & Distributed Systems, 1993, 4(9): 979-993