王振亞，葉友達(dá)

基于多核計(jì)算機(jī)集群系統(tǒng)的網(wǎng)格分區(qū)策略

王振亞，葉友達(dá)

(國(guó)家計(jì)算流體力學(xué)實(shí)驗(yàn)室，北京100191)

網(wǎng)格分區(qū)技術(shù)是提高并行計(jì)算效率的重要手段?；趫D的分區(qū)技術(shù)(如Metis等)已經(jīng)可以完全做到負(fù)載平衡，但是隨著計(jì)算機(jī)集群系統(tǒng)的發(fā)展，節(jié)點(diǎn)間的通訊成為并行計(jì)算中的重要時(shí)間消耗部分。為此，提出一種適用于非結(jié)構(gòu)網(wǎng)格的新分區(qū)策略(MC Partition method)，減少了節(jié)點(diǎn)間的通訊規(guī)模，結(jié)果表明，這種分區(qū)方法可以較大的提高并行計(jì)算效率。

非結(jié)構(gòu)網(wǎng)格;多核;集群;并行;通信

0 引言

計(jì)算流體力學(xué)(CFD)在航空航天以及很多工業(yè)過(guò)程中都得到了非常廣泛的應(yīng)用。由于求解問(wèn)題的復(fù)雜程度越來(lái)越高，需要的計(jì)算網(wǎng)格數(shù)量急劇增加，如果說(shuō)10年以前的網(wǎng)格數(shù)量主要在百萬(wàn)量級(jí)的話，現(xiàn)在使用上千萬(wàn)量級(jí)的網(wǎng)格求解已經(jīng)很常見(jiàn)的，對(duì)于一些復(fù)雜外形，網(wǎng)格規(guī)模甚至達(dá)到上億量級(jí)，并行計(jì)算已成為必需的手段。對(duì)基于非結(jié)構(gòu)網(wǎng)格的解算器而言，由于非結(jié)構(gòu)網(wǎng)格不具有結(jié)構(gòu)網(wǎng)格數(shù)據(jù)隱含的順序性，用什么原則進(jìn)行網(wǎng)格分區(qū)，怎樣才能夠提高非結(jié)構(gòu)網(wǎng)格解算器的并行計(jì)算效率，一直是其中的一個(gè)重要問(wèn)題。

在網(wǎng)格規(guī)模增加的同時(shí)，計(jì)算機(jī)技術(shù)也在飛速進(jìn)步，雖然單核運(yùn)算速度比十年前快了一個(gè)量級(jí)，但是計(jì)算機(jī)技術(shù)中最令人矚目的屬于大規(guī)模并行計(jì)算機(jī)的飛速發(fā)展。從2012年11月13日的第40屆TOP500排名［1］中可以發(fā)現(xiàn)，排名第一的Titan系統(tǒng)的Linpack性能達(dá)到17.59Pflops，排在第十位的Fermi系統(tǒng)也達(dá)到1.72Pflops;而進(jìn)入TOP100的系統(tǒng)性能也從一年前(38屆)的115.9Tflops提升到243.9Tflops。工業(yè)標(biāo)準(zhǔn)化的集群系統(tǒng)(Cluster)已經(jīng)牢牢占據(jù)了本屆TOP 500HPC排行榜的壟斷地位，從2001年6月只有32套，發(fā)展到2012年411套系統(tǒng)，82.2%的比重，十年間增長(zhǎng)了近13倍。越來(lái)越強(qiáng)的計(jì)算能力對(duì)算法提出了更高的要求。由于采用GPU等加速技術(shù)，單個(gè)節(jié)點(diǎn)的計(jì)算速度可以得到大幅提高，但是現(xiàn)在大家發(fā)現(xiàn)當(dāng)前大規(guī)模并行計(jì)算機(jī)遇到的瓶頸主要是數(shù)據(jù)交換的速度，包括網(wǎng)絡(luò)速度，甚至I/O速度等［2］。新的集群系統(tǒng)每個(gè)節(jié)點(diǎn)都是由多核CPU組成，計(jì)算中的數(shù)據(jù)交換與通信就存在計(jì)算機(jī)節(jié)點(diǎn)內(nèi)部的總線速度——節(jié)點(diǎn)之間的網(wǎng)絡(luò)速度——I/O速度之間的平衡，從而需要計(jì)算軟件用更多的注意力來(lái)解決這些新的問(wèn)題。

本文將主要通過(guò)分區(qū)方法的改進(jìn)來(lái)提高并行計(jì)算效率。第一部分將通過(guò)分析提出問(wèn)題，并提出解決問(wèn)題的方法;第二部分將在通過(guò)數(shù)值計(jì)算來(lái)驗(yàn)證新方法;第三部分將是本文的小結(jié)。

1 算法介紹

一直以來(lái)，負(fù)載平衡和減少通信量都是并行計(jì)算中必須考慮的兩個(gè)問(wèn)題。并行計(jì)算的計(jì)算時(shí)間一般可以如下表示:

并行計(jì)算時(shí)間=繼承的串行計(jì)算時(shí)間+

并行的額外時(shí)間開(kāi)銷(1)

負(fù)載平衡就是要求分配到每個(gè)計(jì)算單元的計(jì)算規(guī)模基本一致，它和并行繼承的串行計(jì)算時(shí)間有關(guān)，計(jì)算中不希望出現(xiàn)由于負(fù)載不平衡造成快的計(jì)算單元等待慢的計(jì)算單元的情況;通信量的減少就可以相應(yīng)減少計(jì)算中不同計(jì)算單元間數(shù)據(jù)通信產(chǎn)生的時(shí)間。

對(duì)于非結(jié)構(gòu)網(wǎng)格而言，隨著很多基于圖(graph)的分區(qū)軟件(如Metis［3］等)的應(yīng)用，負(fù)載平衡在基于非結(jié)構(gòu)網(wǎng)格的計(jì)算流體力學(xué)軟件中已經(jīng)可以很方便做到［4］。對(duì)于同樣的網(wǎng)格(約16 000 000單元)和同樣的網(wǎng)格分區(qū)(用pmetis分成112個(gè)區(qū)域)，完全負(fù)載平衡，我們?cè)趦蓚€(gè)不同的集群系統(tǒng)中做了測(cè)試(表1)。從結(jié)果可以發(fā)現(xiàn)，兩個(gè)計(jì)算機(jī)系統(tǒng)的速度相差7倍，如果再仔細(xì)分析，可以發(fā)現(xiàn)其中由于每個(gè)計(jì)算單元的運(yùn)算速度提高使得相應(yīng)的計(jì)算速度提高了4倍，然而由于數(shù)據(jù)傳輸速度的提升使得計(jì)算時(shí)通信速度提高了24倍。

表1 不同集群系統(tǒng)比較Table 1Comparation of different clusters

為了進(jìn)一步研究數(shù)據(jù)通信在計(jì)算中的影響，我們?cè)诎岩粋€(gè)網(wǎng)格(約39 000 000單元)分成不同數(shù)量的任務(wù)并行計(jì)算，計(jì)算結(jié)果見(jiàn)表2?？梢园l(fā)現(xiàn)，隨著參與計(jì)算的計(jì)算單元數(shù)量超過(guò)128，并行計(jì)算效率逐漸下降。由于在網(wǎng)格分區(qū)時(shí)已做到負(fù)載平衡，并行計(jì)算效率降低主要原因是因?yàn)殡S著參與計(jì)算的計(jì)算單元數(shù)量增加，分配到每個(gè)計(jì)算單元的網(wǎng)格數(shù)量隨之減少，相應(yīng)造成了通信數(shù)據(jù)在總的計(jì)算數(shù)據(jù)中所占的比例增加，通信造成的時(shí)間開(kāi)銷在總計(jì)算時(shí)間中的比重不再是不可忽略的小量。

表2 并行計(jì)算效率比較Table 2Comparation of the parallel computing efficiency

從而可以發(fā)現(xiàn)，在達(dá)到負(fù)載平衡以后，通信速度已經(jīng)成為當(dāng)前的并行計(jì)算流體力學(xué)軟件一個(gè)主要瓶頸，這個(gè)問(wèn)題和連接計(jì)算集群每個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)的物理特性有關(guān)，包括網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、網(wǎng)絡(luò)帶寬等，同時(shí)和通信數(shù)據(jù)的構(gòu)成也有很大關(guān)系。當(dāng)前計(jì)算機(jī)集群的每個(gè)節(jié)點(diǎn)的CPU一般都是由多核組成，節(jié)點(diǎn)內(nèi)的多核之間的數(shù)據(jù)通信是基于總線，不同節(jié)點(diǎn)之間的數(shù)據(jù)通信是基于網(wǎng)絡(luò)，而對(duì)于當(dāng)前的計(jì)算機(jī)技術(shù)而言，計(jì)算機(jī)內(nèi)部總線的速度比網(wǎng)絡(luò)速度要快得多。顯然可以發(fā)現(xiàn)，如果在分區(qū)時(shí)僅僅考慮負(fù)載平衡的話，則分區(qū)形成的每個(gè)子區(qū)基本上相互獨(dú)立，那么會(huì)在并行計(jì)算中造成普遍以網(wǎng)絡(luò)速度來(lái)衡量數(shù)據(jù)通信速度的情況，表3采用和表1同樣的網(wǎng)格，用Metis分成48個(gè)分區(qū)，可以做到完全負(fù)載平衡，考察其在一個(gè)由6節(jié)點(diǎn)共48核(6×8)的集群上運(yùn)行的結(jié)果，在每個(gè)節(jié)點(diǎn)中取一個(gè)核為代表，研究其通信數(shù)據(jù)的分布情況。

表3 只考慮負(fù)載平衡的分區(qū)通信數(shù)據(jù)分析(Metis)Table 3Analysis of communication data considering of load balancing

從表3中可以發(fā)現(xiàn)，根據(jù)這種分區(qū)原則得到的網(wǎng)格分區(qū)，節(jié)點(diǎn)之間的通信量在每個(gè)計(jì)算單元的全部通信量中所占比例非常大，有的計(jì)算單元甚至都在和本節(jié)點(diǎn)外的計(jì)算單元通信，而節(jié)點(diǎn)之間的通信是按照網(wǎng)絡(luò)速度來(lái)計(jì)算的，這樣的數(shù)據(jù)分布必然會(huì)大大降低通信速度。通過(guò)這樣的分析，為了進(jìn)一步提高數(shù)據(jù)通信速度，我們需要——調(diào)整計(jì)算單元內(nèi)的通信數(shù)據(jù)分布，增加節(jié)點(diǎn)內(nèi)通信數(shù)據(jù)的比例。

如果計(jì)算機(jī)集群系統(tǒng)由N個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)內(nèi)有M個(gè)核(記為N×M)，根據(jù)這個(gè)原則，我們提出多核集群分區(qū)策略(MultiCore Partition，簡(jiǎn)稱MC)，可以如下描述:

MC Partition策略(如圖1)

1)按照負(fù)載平衡的原則把網(wǎng)格分為N個(gè)區(qū)，對(duì)應(yīng)N個(gè)節(jié)點(diǎn);

2)For i=1 to N

按照負(fù)載平衡的原則把每一個(gè)子區(qū)分為M個(gè)區(qū)，生成的子區(qū)分別對(duì)應(yīng)于第i個(gè)節(jié)點(diǎn)的M個(gè)核;

圖1基于多核的分區(qū)方法(MC Partition)Fig.1Partition method by MC

采用表3對(duì)應(yīng)的網(wǎng)格，我們?cè)诳紤]計(jì)算機(jī)集群系統(tǒng)(6×8)上每個(gè)節(jié)點(diǎn)的多核性質(zhì)后，按照MC方法進(jìn)行分區(qū)，分區(qū)結(jié)果見(jiàn)表4。由于節(jié)點(diǎn)之間以及核之間的分區(qū)算法考察了負(fù)載平衡，所以也達(dá)到了完全負(fù)載平衡。從表4可以發(fā)現(xiàn)，基于這種分區(qū)策略的分區(qū)結(jié)果，使得每個(gè)計(jì)算單元的節(jié)點(diǎn)內(nèi)通信數(shù)據(jù)所占比例大大增加，平均值提高了35%。這種分區(qū)策略實(shí)際上造成的結(jié)果是使得計(jì)算數(shù)據(jù)不僅僅在計(jì)算機(jī)內(nèi)存中存放在一起，同時(shí)它們?cè)趲缀紊弦彩窍噜彽?。根?jù)基本常識(shí)判斷，這樣應(yīng)該會(huì)帶來(lái)通信時(shí)間的減少，從而提高計(jì)算速度和并行效率。

表4 多核分區(qū)方法(MC Partition)的通信數(shù)據(jù)分析Table 4Analysis of communication data by MC partition

2 數(shù)值結(jié)果

表5為表3和表4對(duì)應(yīng)的兩種不同分區(qū)方法在同一個(gè)6×8集群系統(tǒng)的測(cè)試計(jì)算結(jié)果，從中可以看到采用MC Partition方法的分區(qū)使得通信速度提高了32%，總的計(jì)算速度提高了10%。

并行加速比一般如下表示［5］:

表5 不同分區(qū)方法比較(6×8)Table 5Comparation of different partition methods(6×8)

為了更好地測(cè)試計(jì)算方法，我們用一個(gè)更大規(guī)模的網(wǎng)格(約33 600 000單元的非結(jié)構(gòu)網(wǎng)格)來(lái)計(jì)算，分成112個(gè)分區(qū)，測(cè)試在同一個(gè)7×16集群系統(tǒng)進(jìn)行。測(cè)試結(jié)果在表6給出?？梢钥闯觯m然此計(jì)算機(jī)系統(tǒng)的網(wǎng)絡(luò)性能已經(jīng)比較好，但是在采用MC Partition方法之后，通信速度仍然提高了32%，計(jì)算速度提高了近10%。

表6 不同分區(qū)方法比較(7×16)Table 6Comparation of different partition methods(7×16)

串行計(jì)算的CPU時(shí)間是不變的，并行計(jì)算時(shí)間按照(1)式計(jì)算，由于并行計(jì)算中負(fù)載平衡的實(shí)現(xiàn)，每個(gè)計(jì)算單元所繼承的串行計(jì)算量也是基本固定的，如果共有K個(gè)參與計(jì)算的單元，則每個(gè)計(jì)算單元所繼承的串行計(jì)算量可以近似為1/K;如果通信效率提高30%，那么就可以提高并行加速比，尤其在數(shù)據(jù)通信時(shí)間在計(jì)算中所占比例很大的時(shí)候，將會(huì)得到更明顯的表現(xiàn)。

從表5和表6可以發(fā)現(xiàn)，由于兩種分區(qū)算法都能夠很好的保證負(fù)載平衡，所以并行計(jì)算中的串行計(jì)算部分的時(shí)間開(kāi)銷都基本保持不變。為了提高并行計(jì)算中的串行計(jì)算部分的速度，當(dāng)前的并行計(jì)算機(jī)集群系統(tǒng)已經(jīng)大量采用了如GPU等加速計(jì)算技術(shù)，但是數(shù)據(jù)傳輸部分的通信時(shí)間開(kāi)銷也是并行計(jì)算中需要重點(diǎn)注意的部分。對(duì)比表6和表2，可以發(fā)現(xiàn)對(duì)于總的網(wǎng)格量而言，112個(gè)分區(qū)基本上還在并行計(jì)算的線性加速區(qū)內(nèi)，由于計(jì)算條件限制，沒(méi)有采用更多的計(jì)算單元，我們可以預(yù)計(jì)在分區(qū)增加、計(jì)算單元增加的情況下，這種分區(qū)方法仍然是可以有效提高通信速度的。

3 結(jié)論

本文提出了一種適合現(xiàn)代多核計(jì)算機(jī)集群系統(tǒng)的分區(qū)方法(MC Partition)，分區(qū)時(shí)不僅可以達(dá)到每個(gè)計(jì)算單元之間的負(fù)載平衡，而且由于考慮了計(jì)算機(jī)集群系統(tǒng)每個(gè)節(jié)點(diǎn)內(nèi)多核的特點(diǎn)，讓計(jì)算機(jī)內(nèi)更高速的數(shù)據(jù)傳輸部件傳輸盡可能多的數(shù)據(jù)，大大減少了并行計(jì)算中依靠節(jié)點(diǎn)間的網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量，較大的提高了數(shù)據(jù)傳輸速度，提高了計(jì)算速度和并行效率。

當(dāng)然，對(duì)于CFD而言，并行計(jì)算的數(shù)據(jù)傳輸不可能做到速度為零，但是我們通過(guò)考慮計(jì)算機(jī)系統(tǒng)的特點(diǎn)，確實(shí)可以提高并行計(jì)算的效率。

致謝:感謝國(guó)家計(jì)算流體力學(xué)實(shí)驗(yàn)室的周越同志大力提供計(jì)算資源。

［1］http://www.top500.org/

［2］Hu Q F，Numerical simnulation and high-performance computer［C］//Beijing:seminar on key technology in high performance numerical simulation of military engineering，2010.(in Chinese)胡慶豐.數(shù)值模擬和高性能計(jì)算機(jī)［C］//北京:軍工高性能數(shù)值模擬中重大基礎(chǔ)關(guān)鍵技術(shù)研討會(huì)會(huì)議論文集.2010年1月.

［3］Karypis G，Kumar V.Multilevel k-way partitioning scheme for irregular graphs［J］.Journal of Parallel and Distributed Computing，1998，48:96-129.

［4］Wang Z Y，Lu S，Ye Y D，Grid partition of unstructured grid［C］//14thComputational Fluid Dynamics Conference，2004(in Chinese)王振亞，盧笙，葉友達(dá).非結(jié)構(gòu)網(wǎng)格分區(qū)技術(shù)研究［C］//第十二屆全國(guó)計(jì)算流體力學(xué)會(huì)議論文集，2004.

［5］Michael J Quinn.Parallel programming in C with MPI and OpenMP［M］.Beijing:Tsinghua University Press.

A new grid partition strategy for muliti-core cluster system

Wang Zhenya，Ye Youda
(National Laboratory of Computational Fluid Dynamics，Beijing100191，China)

Grid partition method is important to the efficiency of parallel computing.By now，partition method on graph，as Metis，can do load balancing very well.While as the cluster systems improve，communication between node of cluster becomes important.A new partition strategy for unstructured grid according to the new multi-core computer cluster system is proposed.As it is realized and proven to reduce the communication between the nodes，it can improve the parallel computing efficiency about 10%.

unstructured grids;multi-core cluster;parallel;communication

V211.3

Adoi:10.7638/kqdlxxb-2013.0013

0258-1825(2015)01-0087-04

2013-01-24;

2013-05-06

王振亞(1974-)，男，湖南醴陵人，博士，助理研究員，主要從事非結(jié)構(gòu)網(wǎng)格生成以及基于非結(jié)構(gòu)網(wǎng)格的數(shù)值計(jì)算軟件研制工作.E-mail:niels_wang@163.com

王振亞，葉友達(dá).基于多核計(jì)算機(jī)集群系統(tǒng)的網(wǎng)格分區(qū)策略［J］.空氣動(dòng)力學(xué)學(xué)報(bào)，2015，33(1):87-90.

10.7638/kqdlxxb-2013.0013.Wang Z Y，Ye Y D.A new grid partition strategy for muliti-core cluster system［J］.Acta Aerodynamica Sinica，2015，33(1):87-90.