三維數(shù)值流形法覆蓋系統(tǒng)并行分區(qū)生成算法

潘帥琪， 張亞軍， 張友良， 劉哲亨

(海南大學(xué)土木建筑工程學(xué)院， ?？?570228)

數(shù)值流形法(numerical manifold method，NMM)是Shi[1-2]提出的一種能夠統(tǒng)一求解物體的小變形開裂以及分析非連續(xù)大位移的新數(shù)值方法。這種數(shù)值方法能夠模擬物體從連續(xù)到非連續(xù)狀態(tài)的全過程。NMM是將有限單元法(finite element method,FEM)和非連續(xù)變形分析(discontinuous deformation analysis,DDA)統(tǒng)一起來的推廣，在計(jì)算非連續(xù)面的滑動(dòng)、開裂等問題上具有獨(dú)特優(yōu)勢(shì)，適宜求解自由初邊值問題。盡管二維NMM目前已經(jīng)在諸多領(lǐng)域得到了廣泛應(yīng)用[3-6]，但三維NMM作為明顯更符合實(shí)際工程問題的方法，受限于接觸判斷和計(jì)算效率上遇到的瓶頸，目前使用三維NMM進(jìn)行計(jì)算的算例規(guī)模都相對(duì)較小[7-9]。

目前三維NMM多采用六面體或四面體網(wǎng)格生成數(shù)學(xué)覆蓋系統(tǒng)，流形單元的生成過程較二維更復(fù)雜。且與二維NMM相比，三維NMM具有更復(fù)雜的接觸判斷和單個(gè)流形元更多的自由度。三維NMM在求解過程中，需要計(jì)算的整體剛度矩陣的維數(shù)也較二維高，在相應(yīng)時(shí)間步內(nèi)還有大量耗時(shí)的迭代、接觸判斷過程，而在每一次的開閉迭代中都需要進(jìn)行方程組的求解。在模型較大時(shí)，如果時(shí)間步過小，數(shù)學(xué)網(wǎng)格設(shè)置過大則其收斂性難以保證，需要設(shè)置合適的網(wǎng)格大小以及設(shè)置較小的時(shí)間步使精度滿足工程需求；而且NMM的局部覆蓋位移函數(shù)由于使用全局坐標(biāo)的多項(xiàng)式形式，導(dǎo)致積分項(xiàng)階次提高以及自由度增大，雖然相較于FEM提高了計(jì)算精度，也使得NMM的計(jì)算量增大。這都使得程序的運(yùn)算時(shí)間大幅增加。接觸判斷和計(jì)算效率問題成為三維NMM研究應(yīng)用的關(guān)鍵性問題，在接觸判斷方面，石根華新提出的EAB(entrance block between block A and B)理論可初步解決目前三維NMM在接觸判斷方面面臨的困境。然而，EAB理論的引入也使得接觸判斷的計(jì)算量增加，因此亟需有效算法提升三維NMM的計(jì)算效率。

由于硅材料以及微觀尺度的限制，目前摩爾定律已逐漸失效，單個(gè)CPU主頻已很難獲得較大的提升，從軟件角度提升計(jì)算機(jī)的計(jì)算能力成為研究熱點(diǎn)。并行計(jì)算是一種強(qiáng)大的計(jì)算工具，能夠發(fā)揮多核CPU計(jì)算機(jī)或計(jì)算機(jī)集群優(yōu)勢(shì)，充分利用計(jì)算機(jī)資源，加快計(jì)算速度。在工程數(shù)值計(jì)算模擬仿真領(lǐng)域,大量研究人員正在使用并行計(jì)算技術(shù)來提升計(jì)算能力和擴(kuò)大計(jì)算規(guī)模[10-14]。將并行計(jì)算技術(shù)引入三維NMM覆蓋系統(tǒng)生成程序，可以有效提高三維NMM的整體計(jì)算速度。

在三維NMM覆蓋系統(tǒng)串行生成算法方面，已有多位學(xué)者提出了生成算法。李海楓等[15]利用塊體切割技術(shù)，實(shí)現(xiàn)了三維NMM流形單元的生成;楊石扣等[16]采用六面體數(shù)學(xué)網(wǎng)格覆蓋問題域，然后將復(fù)雜塊體與六面體網(wǎng)格進(jìn)行布爾交運(yùn)算, 進(jìn)一步生成流形單元和物理覆蓋?？洛\福等[17]運(yùn)用布爾運(yùn)算實(shí)現(xiàn)了簡(jiǎn)單的三維塊體切割功能，將四面體網(wǎng)格與問題域進(jìn)行布爾交運(yùn)算得到流形塊體；李偉等[18]、伍書重等[19]對(duì)三維NMM覆蓋的生成算法及其改進(jìn)進(jìn)行了研究。張友良等[20]使用MPI(message passing interface)對(duì)二維NMM覆蓋系統(tǒng)并行生成算法進(jìn)行了研究。對(duì)于三維NMM覆蓋系統(tǒng)并行生成算法則尚未有學(xué)者開展相關(guān)研究工作。并行計(jì)算的工具有很多種，如MPI、OpenMP、OpenACC等。其中MPI適用于粗粒度并行計(jì)算[21]，不僅可用于多核計(jì)算機(jī)，且可應(yīng)用于機(jī)群系統(tǒng)進(jìn)一步擴(kuò)大計(jì)算規(guī)模。由于本三維數(shù)值流形法程序基于Windows系統(tǒng)開發(fā)并采用C++編寫，使用MSMPI(Microsoft MPI)實(shí)現(xiàn)三維數(shù)值流形法覆蓋系統(tǒng)生成的粗粒度的并行化是比較合適的方案[22]。

鑒于此，基于布爾運(yùn)算的三維NMM覆蓋系統(tǒng)串行生成算法的基礎(chǔ)上，借鑒二維NMM覆蓋系統(tǒng)并行生成算法思路，對(duì)三維NMM覆蓋系統(tǒng)并行生成算法展開研究。主要研究三維NMM前處理過程中覆蓋系統(tǒng)、流形單元的并行生成算法，以及基于分布式內(nèi)存并行編程模式下覆蓋系統(tǒng)生成中界面數(shù)據(jù)傳遞算法，為后續(xù)的接觸判斷、方程組求解等模塊的并行計(jì)算提供并行前處理器。

在基于布爾運(yùn)算的三維NMM覆蓋系統(tǒng)串行生成算法基礎(chǔ)上,用分布式存儲(chǔ)系統(tǒng)的MPI編程接口將三維數(shù)值流形法前處理的串行程序改為并行程序，實(shí)現(xiàn)了三維NMM覆蓋系統(tǒng)的并行生成，為后續(xù)三維NMM應(yīng)用于大規(guī)模實(shí)際工程數(shù)值模擬開展基礎(chǔ)研究工作。

1 基于布爾運(yùn)算的三維數(shù)值流形法覆蓋系統(tǒng)生成算法

基于布爾運(yùn)算的三維NMM覆蓋生成算法中，定義在同一個(gè)數(shù)學(xué)覆蓋內(nèi)的流形單元，如果兩個(gè)流形元的交集為數(shù)學(xué)面，則此數(shù)學(xué)面為這兩個(gè)流形元的公共數(shù)學(xué)面。物理覆蓋根據(jù)“在覆蓋問題域的一個(gè)數(shù)學(xué)覆蓋內(nèi)，彼此有公共數(shù)學(xué)面的流形元并集形成一個(gè)物理覆蓋”。對(duì)于所使用的六面體數(shù)學(xué)網(wǎng)格，所生成的每個(gè)流形單元應(yīng)當(dāng)與8個(gè)物理覆蓋相關(guān)聯(lián)?？蓳?jù)此檢查物理覆蓋是否生成正確。

圖1 三維NMM的覆蓋系統(tǒng)和流形單元Fig.1 Covers and manifold elements for 3D-NMM

本文算法中一個(gè)數(shù)學(xué)網(wǎng)格與體模型進(jìn)行布爾交運(yùn)算生成流形單元的過程主要步驟如下。

步驟1將數(shù)學(xué)網(wǎng)格與物理模型進(jìn)行面面相互求交，得到物理交線集合，物理線和數(shù)學(xué)線進(jìn)行跡線求交得到數(shù)學(xué)、物理有向邊集合。

步驟2將六面體數(shù)學(xué)網(wǎng)格分別與物理模型進(jìn)行塊體布爾交運(yùn)算，將兩個(gè)求交塊體的各個(gè)面分割成許多個(gè)小面，若有向面的線段中有數(shù)學(xué)線即為數(shù)學(xué)面，否則就為物理面，同時(shí)根據(jù)面的坐標(biāo)及法向量確定需要?jiǎng)h除的面。

步驟3求各個(gè)面的法向量，按照空間塊體搜索的最大右轉(zhuǎn)角準(zhǔn)則[23]形成塊體。

步驟4三維流形單元塊體生成后，通過幾何運(yùn)算尋找每個(gè)流形單元關(guān)聯(lián)的數(shù)學(xué)覆蓋。

在三維流形塊體生成后，根據(jù)Shi[24]提出的三維塊體拓?fù)湫詸z查方法，對(duì)所有任意形狀的多面體進(jìn)行有效性檢查，如果能夠滿足：

?(?Bi)=0

(1)

(2)

式中：Bi為三維多面體；T為目標(biāo)體外邊界。

本文方法中物理覆蓋的搜索生成是通過每個(gè)數(shù)學(xué)覆蓋進(jìn)行的，在生成物理覆蓋的過程中不會(huì)相互影響，在并行程序中便于界面物理覆蓋生成以及與界面流形單元相關(guān)聯(lián)。用這種方法生成物理覆蓋時(shí)需要先生成流形單元，在形成物理覆蓋的同時(shí),可確定跟某個(gè)物理覆蓋關(guān)聯(lián)的所有流形單元以及生成物理覆蓋的數(shù)學(xué)覆蓋。整體物理覆蓋的生成過程如圖2所示。

圖 2 物理覆蓋系統(tǒng)生成流程圖Fig.2 Generating flow chart based on physical coverage system

程序中三維數(shù)學(xué)覆蓋、三維物理覆蓋和三維流形單元分別用MathCover3D、PhysicalCover3D和Manifold Element3D三個(gè)類來定義,基于分區(qū)計(jì)算算法的子區(qū)域用SubDomain3D類定義。這4個(gè)類之間的關(guān)系如圖3中UML類圖所示。在MathCover3D類中，_pc3D和_me3D分別表示此數(shù)學(xué)覆蓋所包含的物理覆蓋和流形單元。 PhysicalCover3D類中，_mc3D表示此物理覆蓋位于此數(shù)學(xué)覆蓋當(dāng)中;并且該物理覆蓋與_me3D容器中所存儲(chǔ)的流形單元相關(guān)聯(lián)。在ManifoldFlement3D類中，_pc3D表示與該流形單元相關(guān)的物理覆蓋，_mc3D表示與該流形單元相關(guān)的數(shù)學(xué)覆蓋。子區(qū)域中的_intfPc3D表示界面物理覆蓋，_intfMe3D表示界面流形單元，界面物理覆蓋與界面流形單元用于計(jì)算過程中區(qū)域間數(shù)據(jù)交換。

圖3 三維數(shù)值流形法數(shù)學(xué)覆蓋、物理覆蓋、流形單元及子覆蓋區(qū)UML類圖Fig.3 UML graph of math cover3D，physical-cover3D，manifold element3D，and SubDomain3D

2 三維NMM覆蓋系統(tǒng)并行生成算法

三維NMM覆蓋系統(tǒng)生成串行算法與并行算法主要不同點(diǎn)前節(jié)已經(jīng)闡述,以下將對(duì)這些不同點(diǎn)及對(duì)應(yīng)的處理算法進(jìn)行介紹。

2.1 并行任務(wù)分配與子計(jì)算區(qū)域劃分

粗粒度并行編程模式下覆蓋系統(tǒng)生成的核心是計(jì)算區(qū)域劃分。對(duì)于基于六面體數(shù)學(xué)網(wǎng)格生成數(shù)學(xué)覆蓋的三維NMM，采用分區(qū)覆蓋生成方法，并考慮2個(gè)并行算法重要約束條件：一是處理器負(fù)載基本均衡，即各個(gè)處理器分配的區(qū)域大小相似，最優(yōu)利用硬件資源，避免部分處理器處于閑置狀態(tài)而增加等待耗時(shí)；二是子區(qū)域邊界接觸面盡量小，降低界面單元數(shù)量，從而減少處理器間通訊耗時(shí)，降低程序并行過程中數(shù)據(jù)傳遞消耗，進(jìn)一步提升并行計(jì)算速度。

在三維NMM并行算法上采用分區(qū)計(jì)算方法來實(shí)現(xiàn)覆蓋系統(tǒng)的并行生成，將體模型在不同處理器上分別對(duì)體模型不同范圍區(qū)域的覆蓋系統(tǒng)進(jìn)行生成，在生成流形單元時(shí)各個(gè)子區(qū)域內(nèi)的數(shù)學(xué)網(wǎng)格同時(shí)與體模型進(jìn)行布爾交運(yùn)算來生成，把整個(gè)模型覆蓋系統(tǒng)生成任務(wù)分解為不同的子區(qū)域上覆蓋系統(tǒng)生成任務(wù)，然后不同處理器負(fù)責(zé)不同計(jì)算區(qū)域的覆蓋系統(tǒng)的生成，最后通過界面單元信息傳遞實(shí)現(xiàn)區(qū)域間的數(shù)據(jù)交換，實(shí)現(xiàn)三維NMM覆蓋系統(tǒng)的并行生成。子計(jì)算區(qū)域生成的具體算法實(shí)現(xiàn)過程如下。

SubDomain3D生成算法1具體步驟如下。

步驟1輸入體模型幾何數(shù)據(jù)。

步驟2根據(jù)模型幾何數(shù)據(jù)計(jì)算模型的問題域尺度。

步驟3用粗六面體網(wǎng)格覆蓋模型域。

步驟4檢查六面體網(wǎng)格是否至少有一個(gè)頂點(diǎn)在模型范圍內(nèi)，去除在模型邊界外的六面體網(wǎng)格。

步驟5對(duì)與模型邊界相交或在模型內(nèi)部的六面體網(wǎng)格進(jìn)行子區(qū)域劃分。

步驟6合并分配到不同處理器的網(wǎng)格，得到子區(qū)域。

圖4～圖6為算法1的過程說明。其中，圖4為一個(gè)邊坡問題的模型，圖5為用粗六面體網(wǎng)格覆蓋模型后的圖形，圖6為圖4與圖5疊加,然后去掉與問題域不相交的粗六面體網(wǎng)格后的圖形。粗六面體網(wǎng)格不同于數(shù)值流形法中的數(shù)學(xué)網(wǎng)格,它比數(shù)學(xué)覆蓋網(wǎng)格要大。用大小相等的粗六面體網(wǎng)格覆蓋問題域的目的是之后利用劃分工具得到負(fù)載基本均衡的子計(jì)算區(qū)域。步驟5中子計(jì)算區(qū)域劃分通過調(diào)用METIS庫(kù)的網(wǎng)格分區(qū)函數(shù)來實(shí)現(xiàn), Metis是由Karypis Lab公司開發(fā)，可用于劃分不規(guī)則圖、網(wǎng)格，具有高質(zhì)量的劃分結(jié)果。其命令行程序模式也方便集成到C++程序中。另外METIS具有很低的注入元(fill-in)，從而降低了存儲(chǔ)負(fù)載和計(jì)算量。該軟件能夠很好地滿足粗粒度模型級(jí)并行計(jì)算中區(qū)域劃分的基本約束條件，即處理器負(fù)載基本均衡和不同處理器之間通訊數(shù)據(jù)量最小的兩個(gè)條件[25]，是科學(xué)并行計(jì)算中的重要的分區(qū)工具。三維數(shù)值流形元的數(shù)學(xué)覆蓋是規(guī)則的六面體網(wǎng)格,每個(gè)網(wǎng)格大小相等,因此子區(qū)域的計(jì)算量與其單元數(shù)量近似成正比。使用函數(shù)METIS_PartMeshDual對(duì)粗網(wǎng)格進(jìn)行子計(jì)算區(qū)域劃分，即可得到基本計(jì)算量均衡的子計(jì)算區(qū)域。在METIS manual中可以了解該函數(shù)的詳細(xì)使用規(guī)則。

圖4 邊坡問題模型Fig.4 Boundary of the slope problem

圖5 粗六面體網(wǎng)格Fig.5 Coarse hexahedron grids

圖6 參與劃分的粗六面體網(wǎng)格Fig.6 Hexahedral mesh that participates in the partition

圖7為算法1中步驟5中使用METIS劃分后形成的4個(gè)子計(jì)算區(qū)域網(wǎng)格圖形的結(jié)果。各個(gè)子區(qū)域合并形成整體覆蓋區(qū)域(圖8)被子計(jì)算區(qū)域間共享的面稱為子計(jì)算區(qū)域間的相鄰界面, 相鄰界面在隨后的界面元素的確定及區(qū)域數(shù)據(jù)傳遞非常重要。將子計(jì)算區(qū)域幾何信息發(fā)送至各個(gè)處理器,每個(gè)處理器負(fù)責(zé)體模型各自計(jì)算區(qū)域范圍內(nèi)的覆蓋系統(tǒng)以及流形單元生成。

圖7 子區(qū)域劃分結(jié)果Fig.7 SubDomain3D interval partition results

圖8 由各個(gè)子區(qū)域形成的整體區(qū)域Fig.8 The whole region formed by each subdomain

圖9 子區(qū)域數(shù)學(xué)網(wǎng)格Fig.9 Mathematical grids for a subdomain

2.2 三維NMM子計(jì)算區(qū)域覆蓋系統(tǒng)生成算法

每個(gè)區(qū)域內(nèi)的數(shù)學(xué)覆蓋與串行相同，其生成可重復(fù)使用串行算法的代碼。但要注意在布置子區(qū)域數(shù)學(xué)網(wǎng)格時(shí)，要求所有子區(qū)域數(shù)學(xué)網(wǎng)格大小相同，并采用相同參照點(diǎn)，以免在子區(qū)域界面處出現(xiàn)網(wǎng)格不協(xié)調(diào)情況。

在子區(qū)域數(shù)學(xué)覆蓋系統(tǒng)生成過程中, 各個(gè)子計(jì)算區(qū)域的數(shù)學(xué)網(wǎng)格應(yīng)當(dāng)在完全覆蓋本子計(jì)算區(qū)域的同時(shí)外擴(kuò)一圈,如圖9所示。如果在布置子區(qū)域的數(shù)學(xué)網(wǎng)格時(shí)將數(shù)學(xué)覆蓋范圍完全限制在子計(jì)算區(qū)域內(nèi),則不便于后續(xù)三維NMM算法程序中界面單元的確定。另外，在與體模型進(jìn)行布爾交運(yùn)算生成各個(gè)子區(qū)域的流形元時(shí)，需要先判斷數(shù)學(xué)網(wǎng)格是否在子區(qū)域范圍內(nèi)，只有在子區(qū)域范圍內(nèi)的網(wǎng)格需要與體模型相互求交生成三維流形單元。除此以外,三維NMM覆蓋系統(tǒng)的并行生成算法代碼與串行生成算法代碼基本相同。圖10為邊坡模型覆蓋系統(tǒng)和流形單元的在并行算法下的生成結(jié)果。在覆蓋系統(tǒng)和三維流形單元生成后，即可根據(jù)覆蓋系統(tǒng)信息確定UML類圖(圖3)中SubDomain3D的類中成員：數(shù)學(xué)覆蓋(_mc3D)、物理覆蓋(_pc3D)和流形單元(_me3D)。

2.3 三維NMM子計(jì)算區(qū)域界面信息建立算法

三維NMM覆蓋系統(tǒng)并行算法數(shù)據(jù)通信交換中包括3個(gè)基本概念:一是子區(qū)域相鄰界面，指一個(gè)子區(qū)域與其他子區(qū)域間相鄰的邊界面,如圖11中直線所指的界面；二是界面物理覆蓋,指被多個(gè)子區(qū)域共享的物理覆蓋；三是界面流形單元,指包含界面物理覆蓋的流形元,這部分流形元與其他子區(qū)域流形元共享一些物理覆蓋。

界面物理覆蓋屬于2個(gè)或以上子計(jì)算區(qū)域。為實(shí)現(xiàn)計(jì)算過程中不同區(qū)域間數(shù)據(jù)傳遞，界面信息搜尋算法詳細(xì)過程見如下算法2。算法2中步驟1被標(biāo)記為INTERFACE_Node_notConfirmed的數(shù)學(xué)覆蓋部分僅是位于區(qū)域外部邊界處的數(shù)學(xué)覆蓋，因此在步驟2中通過處理器間相互通信確定真正的界面數(shù)學(xué)覆蓋。獲得的界面物理覆蓋和界面流形單元分別保存在子計(jì)算區(qū)域成員變量_intfpc3D和_intfme3D中。

界面信息生成算法2步驟如下。

步驟1對(duì)數(shù)學(xué)覆蓋循環(huán),依據(jù)數(shù)學(xué)覆蓋與子區(qū)域邊界幾何關(guān)系,搜尋界面數(shù)學(xué)覆蓋，標(biāo)記為INTERFACE_Node_notConfirmed。

步驟2子計(jì)算區(qū)域與相鄰子區(qū)域相互通信，通過數(shù)學(xué)覆蓋幾何信息，得到與其他計(jì)算區(qū)域相鄰界面處的真實(shí)界面數(shù)學(xué)覆蓋集合，更新標(biāo)記為INTERFACE_Node。

步驟3將狀態(tài)為INTERFACE_Node的界面數(shù)學(xué)覆蓋中的流形元標(biāo)記類型為界面流形單元。

步驟4在同一界面數(shù)學(xué)覆蓋中的界面流形單元，按照前述物理覆蓋生成辦法生成該數(shù)學(xué)覆蓋內(nèi)的物理覆蓋，并標(biāo)記狀態(tài)為界面物理覆蓋。

圖10 并行算法下生成的覆蓋系統(tǒng)和流行單元Fig.10 Cover systems and manifold elements generated by parallel algorithm

圖11 子區(qū)域界面Fig.11 Subdomain3D interfaces

本文算法2通過對(duì)圖10中子計(jì)算區(qū)域覆蓋系統(tǒng)和流形單元的進(jìn)一步處理,得到的界面流形單元如圖12所示。

圖12 區(qū)間界面流形單元Fig.12 Interface manifold elements between different regions

在本算例中，區(qū)域1生成流形單元1 056個(gè)，區(qū)域2生成流形單元1 040個(gè)，區(qū)域3生成流形單元1 064個(gè)，區(qū)域4生成流形單元1 024個(gè)，平均1 046個(gè)，各個(gè)區(qū)域內(nèi)流行單元數(shù)量與均值相差很小，區(qū)域間最大差值為40，相交于流形單元總體數(shù)量是十分小的數(shù)量。說明本并行算法的區(qū)域負(fù)載是基本均衡的。

3 算例

2.1節(jié)中給出了一個(gè)簡(jiǎn)易邊坡模型的算例。給出一個(gè)大型邊坡工程覆蓋系統(tǒng)的并行生成算例，幾何模型的示意圖如圖13所示。圖14為采用不同計(jì)算核心得到的模型和子區(qū)域覆蓋系統(tǒng)。

圖13 問題域模型Fig.13 Problem domain model

圖14 不同核心下生成的覆蓋系統(tǒng)和流形單元Fig.14 Covering systems and manifold elements produced under different number of processors

圖15為不同核心情況下至界面單元計(jì)算完成后的計(jì)算時(shí)間對(duì)比，通過比較可知，三維數(shù)值流形法并行算法的實(shí)際加速效果并不與核心數(shù)成線性關(guān)系，沒有完全達(dá)到理想加速效果。其主要原因有：①并行計(jì)算過程中，各個(gè)處理器計(jì)算量不均勻?qū)е缕渌幚砥鞯却龁栴}；②隨著核心數(shù)及劃分區(qū)域增多，界面單元數(shù)學(xué)增加，處理器之間數(shù)據(jù)通訊傳遞耗時(shí)增加；③目前本算法在進(jìn)行區(qū)域劃分時(shí)未考慮區(qū)域內(nèi)節(jié)理對(duì)計(jì)算效率的影響，導(dǎo)致含節(jié)理區(qū)域流形單元數(shù)目較其他區(qū)域多，這個(gè)因素將在后續(xù)并行算法研究中結(jié)合METIS網(wǎng)格權(quán)重功能對(duì)含節(jié)理區(qū)網(wǎng)格識(shí)別并增加劃分權(quán)重，進(jìn)一步實(shí)現(xiàn)區(qū)域劃分的平衡性。

圖15 不同核心情況下計(jì)算時(shí)間Fig.15 Computation time with different number of CPU

圖16為4種不同分區(qū)情況下下各子區(qū)域流形單元個(gè)數(shù)，可以看出，4核心下區(qū)域間流形元最大差值為144，6核心下區(qū)域間流形元最大差值為158，8核心下區(qū)域間流形元最大差值為106，10核心下區(qū)域間流形元最大差值為78，無論哪種劃分方式，各個(gè)子區(qū)域的流形元個(gè)數(shù)均差別較小，且隨著劃分區(qū)域的增多，其差值總體越來越小。說明本并行覆蓋生成方法具有較好的負(fù)載均衡性。

圖16 不同分區(qū)情況下各區(qū)域流形單元數(shù)Fig.16 Number of manifold elements in each region under different partition conditions

4 結(jié)論

三維NMM覆蓋系統(tǒng)并行生成算法只需要輸入體模型幾何數(shù)據(jù)，這些數(shù)據(jù)與串行算法過程中數(shù)據(jù)輸入方法完全相同。同時(shí),本文并行算法輸出的三維NMM覆蓋系統(tǒng)數(shù)據(jù)可以直接傳遞至后續(xù)三維NMM計(jì)算求解器計(jì)算，是高效的粗粒度模型級(jí)并行算法。

(1)在基于布爾運(yùn)算的三維NMM覆蓋系統(tǒng)生成算法上,研究了粗粒度并行下三維NMM覆蓋系統(tǒng)生成算法,并取得了預(yù)期的加速效果，結(jié)果表明，該并行計(jì)算策略加快了三維NMM覆蓋系統(tǒng)的生成速度，而且能夠適應(yīng)各種規(guī)模的問題。

(2)三維NMM覆蓋系統(tǒng)并行算法中保證各個(gè)處理器計(jì)算任務(wù)的負(fù)載基本均衡可以提高程序運(yùn)行效率，充分利用并行優(yōu)勢(shì)與計(jì)算機(jī)硬件資源。

(3) 三維NMM覆蓋系統(tǒng)生成算法中計(jì)算量最大的是流形單元生成，利用分區(qū)覆蓋生成方法可實(shí)現(xiàn)三維NMM覆蓋系統(tǒng)的并行化生成,是高效的基于粗粒度分布式內(nèi)存編程模式下的并行算法。

(4)如何設(shè)計(jì)能快速確定界面單元的算法至關(guān)重要，界面信息用于后續(xù)計(jì)算過程中數(shù)據(jù)交換和數(shù)據(jù)通信。

本文算法是針對(duì)計(jì)算模型進(jìn)行基于區(qū)域分解思想的粗粒度并行算法。針對(duì)三維NMM計(jì)算中方程組的求解進(jìn)行算法級(jí)的細(xì)粒度并行數(shù)值方程求解還需進(jìn)一步的研究。另外，云計(jì)算計(jì)術(shù)是當(dāng)今興起的技術(shù)熱點(diǎn)，可以為用戶提供彈性計(jì)算資源，用戶可以根據(jù)自身需求創(chuàng)建使用不同配置的虛擬主機(jī)或計(jì)算機(jī)節(jié)點(diǎn)集群來進(jìn)行計(jì)算。為了三維NMM的進(jìn)一步推廣應(yīng)用，結(jié)合云計(jì)算技術(shù)與三維NMM并行數(shù)值求解是下一步需要進(jìn)行的研究工作。