向量式有限元桁架結(jié)構(gòu)并行程序節(jié)點(diǎn)分配技術(shù)

杜慶峰， 吳　瀚

(同濟(jì)大學(xué) 軟件學(xué)院， 上海 201804)

?

向量式有限元桁架結(jié)構(gòu)并行程序節(jié)點(diǎn)分配技術(shù)

杜慶峰， 吳瀚

(同濟(jì)大學(xué) 軟件學(xué)院， 上海 201804)

摘要：結(jié)合向量式有限元(VFIFE)的計(jì)算規(guī)則以及桁架結(jié)構(gòu)的特點(diǎn)，提出了一種并行程序節(jié)點(diǎn)分配機(jī)制.通過對桁架結(jié)構(gòu)模型數(shù)據(jù)的分析，定義模型數(shù)據(jù)的分解規(guī)則，動(dòng)態(tài)實(shí)現(xiàn)對模型數(shù)據(jù)的分解.依據(jù)分解的結(jié)果來動(dòng)態(tài)劃分并行計(jì)算的數(shù)據(jù)集，并且基于特定的并行計(jì)算框架完成并行計(jì)算.實(shí)例驗(yàn)證表明，該節(jié)點(diǎn)分配機(jī)制是有效的，并且極大地提高了計(jì)算效率.

關(guān)鍵詞：向量式有限元(VFIFE)； 桁架結(jié)構(gòu)； 并行算法

1　研究背景及問題的提出

1.1背景介紹

隨著計(jì)算機(jī)科學(xué)的迅速發(fā)展，計(jì)算科學(xué)、分析理論和物理實(shí)驗(yàn)構(gòu)成了現(xiàn)代科學(xué)發(fā)展的三大支柱.在建筑工程領(lǐng)域，結(jié)構(gòu)力學(xué)、有限元理論是目前主流的分析架構(gòu)，這種架構(gòu)主要包括兩部分：為了描述結(jié)構(gòu)體的性質(zhì)和物理行為設(shè)定一組描述參數(shù)；為了進(jìn)行數(shù)值分析而提出的一組行為變化準(zhǔn)則及簡化假設(shè).依據(jù)此架構(gòu)，工程師們可以通過數(shù)學(xué)方法來模擬一個(gè)結(jié)構(gòu)，規(guī)劃計(jì)算流程，得到結(jié)構(gòu)上任意一點(diǎn)的位置變化，以及其他力學(xué)參數(shù).

向量式有限元(VFIFE)[1-3]是由美國普渡大學(xué)丁承先教授提出的結(jié)構(gòu)行為分析的一個(gè)創(chuàng)新概念.VFIFE是求解結(jié)構(gòu)的大變形、大變位、彈塑性、碰撞、倒塌等非線性或不連續(xù)力學(xué)行為的新方法.以此理論為基礎(chǔ)，可以通過簡單的而系統(tǒng)化的計(jì)算程序?qū)Y(jié)構(gòu)的真實(shí)行為進(jìn)行仿真.

VFIFE的研究與應(yīng)用尚處于起步階段，對許多實(shí)際問題的模擬還比較初步.盡管如此，在許多方面的應(yīng)用尤其是涉及多個(gè)結(jié)構(gòu)體的系統(tǒng)動(dòng)力、大變形等問題的處理上，VFIFE已經(jīng)顯示出了獨(dú)特的優(yōu)越性，即程序的穩(wěn)定性、計(jì)算的收斂性與準(zhǔn)確性、程序編寫的簡潔性以及適合并行處理等一系列優(yōu)點(diǎn)，且無需集成整體剛度矩陣[4]，具有更高的程序開發(fā)效率.

空間桁架結(jié)構(gòu)是建筑工程領(lǐng)域常見的一種格構(gòu)化梁式結(jié)構(gòu).常用于大跨度的廠房、展覽館、體育館和橋梁等公共建筑中.本文將以桁架結(jié)構(gòu)為研究對象，實(shí)現(xiàn)VFIFE程式計(jì)算過程的并行化處理.

1.2VFIFE計(jì)算過程的不足及問題的提出

1.2.1VFIFE計(jì)算過程

VFIFE計(jì)算過程分可為3個(gè)模塊：前處理模塊、程式計(jì)算模塊、后處理模塊.結(jié)構(gòu)體的模型數(shù)據(jù)通過前處理模塊生成并解析，輸入到程式計(jì)算模塊進(jìn)行計(jì)算，最終輸出可由后處理模塊進(jìn)行展示的行為數(shù)據(jù).流程圖如圖1所示.

前處理模塊中，通過建模生成的數(shù)據(jù)即VFIFE程序計(jì)算的輸入數(shù)據(jù)，由第三方建模軟件SAP2000導(dǎo)出的模型文件轉(zhuǎn)換而來.以桁架結(jié)構(gòu)為例，桁架是一種由桿件在兩端用節(jié)點(diǎn)連接而成的結(jié)構(gòu)，因而模型數(shù)據(jù)主要包括三部分：node、element、force，分別包含了節(jié)點(diǎn)信息、桿件與節(jié)點(diǎn)的拓?fù)湫畔⒁约巴饬π畔?

圖1　VFIFE計(jì)算流程圖

模型數(shù)據(jù)的節(jié)點(diǎn)信息node每一行代表一個(gè)節(jié)點(diǎn)，包含了節(jié)點(diǎn)的編號值、節(jié)點(diǎn)的類型(鉸接點(diǎn)或剛節(jié)點(diǎn))、節(jié)點(diǎn)的坐標(biāo)信息以及節(jié)點(diǎn)的質(zhì)量，例如：

模型數(shù)據(jù)的桿件信息element每一行代表一個(gè)桿件，包含了桿件的編號值、桿件兩端節(jié)點(diǎn)編號值以及桿件的一些力學(xué)參數(shù)(楊氏模量、橫截面積、密度和極限力)，例如：

模型數(shù)據(jù)的力學(xué)信息force每一行代表一個(gè)作用力，包含了力的編號值、類型(默認(rèn)為集中力)，力的作用位置、方向以及作用時(shí)間，例如：

程式計(jì)算模塊中，計(jì)算程序依據(jù)桁架結(jié)構(gòu)模型的位移迭代公式編寫，將前處理模塊生成的模型數(shù)據(jù)作為第一幀輸入，由節(jié)點(diǎn)當(dāng)前幀以及上一幀的位置計(jì)算出該點(diǎn)下一幀的位置.該位移迭代公式可簡寫為

(1)

式中：Xn+1、Xn及Xn-1依次為節(jié)點(diǎn)下一幀坐標(biāo)向量、節(jié)點(diǎn)當(dāng)前幀坐標(biāo)向量以及節(jié)點(diǎn)上一幀坐標(biāo)向量；C1、C2及C3均為與結(jié)構(gòu)模型本身相關(guān)的力學(xué)常量；Fn則表示節(jié)點(diǎn)當(dāng)前幀所受的外力、作用力等.

后處理模塊中，行為數(shù)據(jù)即程序計(jì)算的輸出數(shù)據(jù)，由程式計(jì)算程序直接導(dǎo)出，描述了外力作用下結(jié)構(gòu)模型的變形行為，分為兩部分：時(shí)間信息的幾何模型數(shù)據(jù)Node.txt和包含時(shí)間信息的拓?fù)淠Ｐ蛿?shù)據(jù)Element.txt.

行為數(shù)據(jù)中幾何模型數(shù)據(jù)包括了幀、節(jié)點(diǎn)編號值、節(jié)點(diǎn)的坐標(biāo)信息，例如：

行為數(shù)據(jù)中拓?fù)淠Ｐ蛿?shù)據(jù)包括了幀、桿件編號值、桿件兩端的節(jié)點(diǎn)編號值，例如：

后處理行為數(shù)據(jù)可直接用于展示結(jié)構(gòu)模型的動(dòng)畫效果，后處理模塊的程序可以根據(jù)每一幀的行為數(shù)據(jù)繪制出模型，并連續(xù)地展示出來.行為數(shù)據(jù)規(guī)模與結(jié)構(gòu)模型的大小、演示時(shí)間幀數(shù)量成正比.

1.2.2問題的提出

現(xiàn)階段，前處理模型數(shù)據(jù)均來源于傳統(tǒng)的有限元分析工具(SAP2000、ANSYS等)建模導(dǎo)出的模型數(shù)據(jù)文件，然而這些建模軟件封裝度高，沒接口支持，算法靈活性差，導(dǎo)出的模型數(shù)據(jù)文件無法直接用于VFIFE程序計(jì)算.

在程式計(jì)算模塊，程序代碼處理海量數(shù)據(jù)時(shí)，仍然是逐點(diǎn)依次進(jìn)行迭代運(yùn)算，需要等所有節(jié)點(diǎn)一次迭代完成，再進(jìn)行下一次迭代運(yùn)算，因而計(jì)算效率不高，且無法體現(xiàn)VFIFE適合并行處理等優(yōu)勢.

在后處理模塊，后期的數(shù)據(jù)讀取與行為分析顯示也已經(jīng)完成，通過調(diào)用OpenGL庫，整個(gè)有限元分析過程可以以三維動(dòng)畫的形式展示在用戶面前[5].此外，杜慶峰等[5-6]提出的壓縮模型及算法為數(shù)據(jù)文件的云端存儲提供了可能，具有很高的實(shí)用性.

針對以上不足，有必要進(jìn)行VFIFE行為數(shù)據(jù)的并行分布式處理研究，這對于推廣VFIFE這一新型結(jié)構(gòu)力學(xué)方法，實(shí)現(xiàn)高性能的并行有限元分析系統(tǒng)具有重要意義.本文以建筑工程中常見的大型復(fù)雜桁架結(jié)構(gòu)為例，通過分析VFIFE前處理模型數(shù)據(jù)結(jié)構(gòu)，在云計(jì)算環(huán)境下實(shí)現(xiàn)程序計(jì)算過程的并行分布式處理，并與傳統(tǒng)有限元處理方式[7-8]的結(jié)果進(jìn)行對比.

2　并行計(jì)算節(jié)點(diǎn)分配模型

2.1節(jié)點(diǎn)標(biāo)識規(guī)則及節(jié)點(diǎn)任務(wù)分配

2.1.1相關(guān)定義

在VFIFE分析中，空間幾何實(shí)體經(jīng)離散化處理，成為有限元模型[9]，然后按一定的規(guī)則將所有桿件和節(jié)點(diǎn)標(biāo)識賦予唯一的編號值，通過節(jié)點(diǎn)的運(yùn)動(dòng)狀態(tài)(位置、速度、加速度)來描述結(jié)構(gòu)的運(yùn)動(dòng)狀態(tài)[10]，并基于此進(jìn)行分析和計(jì)算.盡管標(biāo)識的順序原則上不影響計(jì)算結(jié)果，可以是任意的，但節(jié)點(diǎn)標(biāo)識的順序?qū)Σ⑿杏?jì)算節(jié)點(diǎn)分配起著決定性的作用.

節(jié)點(diǎn)編號值排序的大部分方法是將問題轉(zhuǎn)化為有限元網(wǎng)格所生成的各種圖的頂點(diǎn)排序問題[11].傳統(tǒng)有限元進(jìn)行節(jié)點(diǎn)標(biāo)識排序是為了保證有限元整體剛度矩陣的帶寬最小，向量式有限元雖然無需集成剛度矩陣，但為了方便并行計(jì)算前對整體結(jié)構(gòu)的劃分，應(yīng)該參照傳統(tǒng)有限元的節(jié)點(diǎn)標(biāo)識方式.

本文針對復(fù)雜桁架結(jié)構(gòu)分析提出的節(jié)點(diǎn)標(biāo)識方式參考了姜濤等[12]提出的優(yōu)化算法.相關(guān)定義如下：

定義1相鄰節(jié)點(diǎn)、節(jié)點(diǎn)的度與節(jié)點(diǎn)熵

在桁架結(jié)構(gòu)中，由若干桿件圍成的封閉圖形稱為一個(gè)單元r，在同一單元r內(nèi)的所有節(jié)點(diǎn)互稱為相鄰節(jié)點(diǎn).

假設(shè)任一節(jié)點(diǎn)u的所有相鄰節(jié)點(diǎn)總數(shù)為d個(gè)，稱為節(jié)點(diǎn)u的度，則節(jié)點(diǎn)u的相鄰節(jié)點(diǎn)集合表示為Su={s1,s2,s3,…,sd}.

節(jié)點(diǎn)u所在的單元均稱為該節(jié)點(diǎn)的相關(guān)單元，假設(shè)節(jié)點(diǎn)u的所有相關(guān)單元總數(shù)為j個(gè)，則節(jié)點(diǎn)u的相關(guān)單元集合表示為Ru={r1,r2,r3,…,rj}，該節(jié)點(diǎn)u的節(jié)點(diǎn)熵δ=d/j.

定義2桁架結(jié)構(gòu)層次展開樹

定義3直徑端點(diǎn)

假設(shè)在定義2的桁架結(jié)構(gòu)層次展開樹LP中，其首結(jié)點(diǎn)為P，尾節(jié)點(diǎn)為Q，可使展開樹樹寬wp最小，則稱P和Q為該結(jié)構(gòu)的直徑端點(diǎn).

定義4合成展開樹

假設(shè)構(gòu)造以直徑端點(diǎn)P和Q為根的桁架結(jié)構(gòu)層次展開樹LP={LP1,LP2,LP3,…,LPG}以及LQ={LQ1,LQ2,LQ3,…,LQF}，然后按照姜濤等[12]提出的算法合并樹LP和LQ形成新的合成展開樹L={D1,D2,D3,…,Dk}[13]，記樹LP和LQ的寬度分別為wp和wq，則合成展開樹L的樹寬滿足條件w≤min{wp,wq}.

定義5模型文件節(jié)點(diǎn)數(shù)據(jù)集

以桁架結(jié)構(gòu)為例，前處理模型文件中，將節(jié)點(diǎn)信息表示為數(shù)據(jù)集node(N,T,ρ,M)，簡稱為節(jié)點(diǎn)數(shù)據(jù)集，其構(gòu)成元素含義為：N={n0,n1,n2,…,nn}表示節(jié)點(diǎn)的編號值集合，集合中的ni表示每個(gè)節(jié)點(diǎn)的編號值(Id)，是由0至n的整型數(shù)據(jù)；T={a0,a1,a2,…,an}表示節(jié)點(diǎn)的類型集合，集合中的元素ai表示每個(gè)節(jié)點(diǎn)的類型，ai=0表示該節(jié)點(diǎn)類型為自由點(diǎn)，即無約束的點(diǎn)，ai=1表示該節(jié)點(diǎn)的約束類型為鉸接，ai=2表示該節(jié)點(diǎn)的約束類型為剛接；ρ={ρnx,ρny,ρnz}表示節(jié)點(diǎn)坐標(biāo)信息集合，其中ρn={ρn0,ρn1,ρn2,…,ρnn}，集合中的ρni表示每個(gè)節(jié)點(diǎn)的三維空間坐標(biāo)值；M={m0,m1,m2,…,mn}表示節(jié)點(diǎn)的質(zhì)量集合，集合中的mi表示每個(gè)節(jié)點(diǎn)的質(zhì)量.

定義6模型文件桿件數(shù)據(jù)集

以桁架結(jié)構(gòu)為例，前處理模型文件中，桿件信息表示為數(shù)據(jù)集element(E,NA,NB,C)，其構(gòu)成元素含義為：E={e0,e1,e2,…,eH}表示桿件的編號值集合，集合中的ei表示每個(gè)桿件的編號值；NA={An0,An1,An2,…,AnH}，集合中的元素Ani表示每個(gè)桿件某一端的節(jié)點(diǎn)編號值，顯然Ani∈N；NB={Bn0,Bn1,Bn2,…,BnH}中的元素Bni表示桿件另一端的節(jié)點(diǎn)編號值，同理有Bni∈N；數(shù)據(jù)集中的C表示該桿件的一些力學(xué)常數(shù)，包括楊氏模量、桿件的截面積及密度，以及桿件的極限應(yīng)力，這些力學(xué)常量均為程式計(jì)算過程中所需參數(shù).將桿件數(shù)據(jù)集element中的任一行表示為le(e,Na,Nb,C)，即編號為e的桿件.

2.1.2節(jié)點(diǎn)標(biāo)識及分配規(guī)則

假設(shè)在任一桁架結(jié)構(gòu)模型文件中，首先依據(jù)定義3選取模型文件節(jié)點(diǎn)數(shù)據(jù)集中距離最遠(yuǎn)的2個(gè)點(diǎn)P和Q作為直徑端點(diǎn)，然后以這2個(gè)端點(diǎn)作為首節(jié)點(diǎn)生成該桁架結(jié)構(gòu)的層次展開樹LP和LQ.依據(jù)定義4合并為合成展開樹L.對于合成展開樹L={D1,D2,D3,…,Dk}，標(biāo)識連續(xù)的正整數(shù)給D1上的節(jié)點(diǎn)，用最小編號值0標(biāo)識展開樹的起點(diǎn)P，設(shè)μ為D1中已標(biāo)識節(jié)點(diǎn)中最小的，則按照節(jié)點(diǎn)熵δ增加的順序?qū)Ζ痰南噜徆?jié)點(diǎn)進(jìn)行標(biāo)識.迭代上一步驟完成本層大部分節(jié)點(diǎn)標(biāo)識，對于本層的剩余節(jié)點(diǎn)，選擇最小的節(jié)點(diǎn)編號值重復(fù)迭代過程，直到本層所有節(jié)點(diǎn)都被標(biāo)識.從根節(jié)點(diǎn)層到最后一層依次重復(fù)上述算法，完成整體桁架結(jié)構(gòu)的節(jié)點(diǎn)標(biāo)識.

對于桿件的標(biāo)識，同樣依照節(jié)點(diǎn)編號值順序來進(jìn)行編號，從編號值最小的節(jié)點(diǎn)P開始，在其相鄰節(jié)點(diǎn)中查找節(jié)點(diǎn)編號值最小的點(diǎn)，將最小編號0分給連接這2個(gè)點(diǎn)的桿件，然后再按照節(jié)點(diǎn)編號值增加的順序分配連續(xù)正整數(shù)到以節(jié)點(diǎn)Q為端點(diǎn)的桿件.依次對其他節(jié)點(diǎn)進(jìn)行上述過程，若遇到已經(jīng)被標(biāo)識的桿件則保留原編號，繼續(xù)查找其他相鄰點(diǎn)，直到結(jié)構(gòu)中所有桿件均被標(biāo)識.

在不考慮斷裂的情況下，桿件與節(jié)點(diǎn)的拓?fù)鋽?shù)據(jù)，即模型文件中的桿件數(shù)據(jù)集element不會隨時(shí)間變化發(fā)生改變，因而在并行計(jì)算前，只需對桁架結(jié)構(gòu)的節(jié)點(diǎn)數(shù)據(jù)集node進(jìn)行分配即可.結(jié)合以上特點(diǎn)，針對并行計(jì)算過程中節(jié)點(diǎn)分配模型，提出以下定義：

定義7基準(zhǔn)節(jié)點(diǎn)與分區(qū)

定義8分割桿件與分割節(jié)點(diǎn)

在程序計(jì)算的位移迭代公式中，是以各個(gè)節(jié)點(diǎn)為單位，迭代計(jì)算出節(jié)點(diǎn)在每一幀的位置，迭代公式(1)中，除了節(jié)點(diǎn)合力Fn中的節(jié)點(diǎn)內(nèi)力fn需要根據(jù)當(dāng)前幀的桿件長度計(jì)算外，其他數(shù)據(jù)均來源于定義5中的節(jié)點(diǎn)數(shù)據(jù)集node.而計(jì)算某一節(jié)點(diǎn)的內(nèi)力fn需要先計(jì)算所有與該節(jié)點(diǎn)相連的桿件的長度變化，即需要桿件另一端節(jié)點(diǎn)的位置信息.在并行計(jì)算過程對輸入數(shù)據(jù)進(jìn)行劃分時(shí)，應(yīng)保證各個(gè)分區(qū)的整體性，即各個(gè)分區(qū)中的節(jié)點(diǎn)是連續(xù)的，而相鄰的分區(qū)通過若干桿件相連，這種桿件定義為分割桿件，顯然分割桿件的數(shù)量越少，并行計(jì)算時(shí)需要在各個(gè)分區(qū)外獲取的數(shù)據(jù)量越小.分割桿件兩端的節(jié)點(diǎn)均稱為分割節(jié)點(diǎn).

在上述節(jié)點(diǎn)重新標(biāo)識的基礎(chǔ)上，依據(jù)定義7和8，得出節(jié)點(diǎn)分配應(yīng)遵循的原則：為了保證并行計(jì)算時(shí)負(fù)載的均衡，需盡量保證各個(gè)分區(qū)中分配到的子節(jié)點(diǎn)數(shù)據(jù)集大小相近.為了使程式計(jì)算的迭代過程順利進(jìn)行，需標(biāo)記出各個(gè)分區(qū)中包含在分割桿件中的點(diǎn)，這些點(diǎn)需要隨著每一次迭代而更新，并運(yùn)用于2個(gè)或以上的分區(qū).

2.2節(jié)點(diǎn)分配模型

根據(jù)第2.1節(jié)中的相關(guān)定義，本節(jié)給出具體的節(jié)點(diǎn)分配模型.

假設(shè)有一個(gè)桁架結(jié)構(gòu)模型文件θ需要分配到k個(gè)分區(qū)中參與并行計(jì)算，基于定義5中的節(jié)點(diǎn)數(shù)據(jù)集node及定義6中的桿件數(shù)據(jù)集element，模型數(shù)據(jù)文件的構(gòu)成可以表示為θ(F,node,element)，其中F(IdF,W,T)為模型數(shù)據(jù)文件中的外力元素，此集合中的元素IdF表示此外力的編號值，是由0至n的整型數(shù)據(jù).元素W表示集中外力作用的3個(gè)要素信息，即力的大小、力的作用點(diǎn)及力的方向.集合中元素T表示力的斜坡加載時(shí)間參數(shù)，包括斜坡加載的開始時(shí)間、結(jié)束時(shí)間等，T的大小直接關(guān)系到程式計(jì)算生成的后處理行為數(shù)據(jù)文件大小.

基于以上分析，節(jié)點(diǎn)分配模型邏輯如下：

步驟1應(yīng)依據(jù)定義4的合成展開樹以及標(biāo)識規(guī)則對模型的節(jié)點(diǎn)以及桿件進(jìn)行重新標(biāo)識，得到重新標(biāo)識后的節(jié)點(diǎn)數(shù)據(jù)集node與桿件數(shù)據(jù)集element.

步驟2計(jì)算出節(jié)點(diǎn)數(shù)據(jù)集node的k個(gè)基準(zhǔn)節(jié)點(diǎn)，依據(jù)定義7對基準(zhǔn)節(jié)點(diǎn)的定義，得到基準(zhǔn)節(jié)點(diǎn)的集合B{b1,b2,b3,…,bk}.

步驟5依據(jù)迭代式(1)，在程序計(jì)算過程中，外力元素?cái)?shù)據(jù)集F只隨迭代次數(shù)而發(fā)生變化，而桿件數(shù)據(jù)集element僅表示模型中桿件與節(jié)點(diǎn)的拓?fù)潢P(guān)系.故數(shù)據(jù)集F以及element不會依據(jù)每一次迭代的結(jié)果而更新數(shù)據(jù)，無需參與分塊過程，僅需對節(jié)點(diǎn)數(shù)據(jù)集node進(jìn)行分塊.并行計(jì)算過程中，各計(jì)算節(jié)點(diǎn)共享數(shù)據(jù)集F與element.

步驟6在計(jì)算過程中需要將分割節(jié)點(diǎn)數(shù)據(jù)集nodeξ(N,T,ρ,M,ξ)儲存在共享緩存中，依據(jù)分割節(jié)點(diǎn)的分區(qū)編號值對ξ(τ,ω)來選擇計(jì)算時(shí)需要獲取數(shù)據(jù)所在的分區(qū)，并隨計(jì)算過程的每一次迭代而更新當(dāng)前幀的數(shù)據(jù).

3　分配模型算法及并行處理驗(yàn)證

根據(jù)第2.2節(jié)中節(jié)點(diǎn)分配模型的邏輯，本節(jié)將在Spark這一云計(jì)算平臺下實(shí)現(xiàn)VFIFE復(fù)雜桁架結(jié)構(gòu)程序計(jì)算的并行化，并使用資源管理器YARN進(jìn)行任務(wù)的調(diào)度.Spark的編程模型與Hadoop的MapReduce編程模型非常類似，但是Spark中的容錯(cuò)并行數(shù)據(jù)結(jié)構(gòu)(RDD)模型使得Spark可以實(shí)現(xiàn)數(shù)據(jù)集的相互轉(zhuǎn)化和緩存等操作，這在處理迭代計(jì)算方面具有非常大的優(yōu)勢，因而成為本實(shí)驗(yàn)的首選.

3.1分配模型算法

并行處理以桁架結(jié)構(gòu)的模型數(shù)據(jù)文件θ(F,node,element)為對象，其存儲方式為多維數(shù)組，每一個(gè)數(shù)組元素表示一個(gè)外力元素信息或是節(jié)點(diǎn)、桿件的位置信息.首先對模型文件中的節(jié)點(diǎn)數(shù)據(jù)集node(N,T,ρ,M)按照本文的節(jié)點(diǎn)標(biāo)識規(guī)則進(jìn)行重新標(biāo)識，在重新標(biāo)識后即依據(jù)需要分成的分區(qū)數(shù)對節(jié)點(diǎn)進(jìn)行分塊，并將每個(gè)分區(qū)中的分割節(jié)點(diǎn)信息保存到RDD中，在每一次迭代完成后，需將上一幀中的節(jié)點(diǎn)信息同步到各個(gè)分區(qū)中，進(jìn)行下一步迭代計(jì)算.

在Spark的編程模型中，核心計(jì)算部分引入了RDD的基于內(nèi)存的MapReduce，底層依賴于Hadoop分布式文件系統(tǒng)(HDFS)和YARN/Mesos，因而本文中程序計(jì)算的并行分布式處理大致劃分為2個(gè)階段執(zhí)行：Map和Reduce.Spark提供了一種共享變量——廣播變量，可供所有機(jī)器獲取其中數(shù)據(jù)，利用這個(gè)機(jī)制可以在所有Slave節(jié)點(diǎn)上共享只讀數(shù)據(jù).結(jié)合第2.2節(jié)的分析，本實(shí)驗(yàn)將輸入文件中的數(shù)據(jù)集放入到廣播變量中，以供所有Slave節(jié)點(diǎn)讀取.

Spark的RDD可提供2種操作，即轉(zhuǎn)換以及動(dòng)作.轉(zhuǎn)換可從RDD生成新的RDD，動(dòng)作則能夠?qū)DD數(shù)據(jù)集的執(zhí)行結(jié)果寫入存儲系統(tǒng)或者傳回驅(qū)動(dòng)程序.在本實(shí)驗(yàn)的各個(gè)分區(qū)中，將并行地執(zhí)行程序計(jì)算中的位移迭代公式，對各個(gè)分區(qū)中的模型文件節(jié)點(diǎn)數(shù)據(jù)集進(jìn)行計(jì)算，而在計(jì)算當(dāng)前幀時(shí)，會將當(dāng)前幀和上一幀的節(jié)點(diǎn)位置信息保存到RDD中，并且對各幀的RDD進(jìn)行緩存，以便下一步迭代的執(zhí)行，同時(shí)還要寫到輸出的行為數(shù)據(jù)中作為記錄.緩存的RDD一般存儲在內(nèi)存中，如果內(nèi)存不夠，可以寫到磁盤上[14].

綜上所述，基于Spark的向量式有限元復(fù)雜桁架結(jié)構(gòu)并行分布式計(jì)算流程大致如圖2所示.

圖2　并行計(jì)算的流程圖

結(jié)合上圖，向量式有限元并行處理的步驟如下：

Driver：基于Spark的底層驅(qū)動(dòng)類，可通過方法函數(shù)setMapper()、setCombiner()和setReducer()驅(qū)動(dòng)Mapper類、Combiner類和Reducer類，從而在相應(yīng)的類中實(shí)現(xiàn)Map、Combine以及ReduceByKey等操作函數(shù)對數(shù)據(jù)集進(jìn)行處理.

Combiner：將節(jié)點(diǎn)上的Mapper輸出進(jìn)行規(guī)約操作，輸出的對通過網(wǎng)絡(luò)送到Reducer階段，這里的Key與Mapper輸出的Key相同，即各個(gè)節(jié)點(diǎn)的編號值N，Value為本次迭代得到的新一輪子節(jié)點(diǎn)數(shù)據(jù)集.

Reducer：這個(gè)過程執(zhí)行的操作跟Combiner類似，將Combiner輸出的具有相同Key值的Value進(jìn)行整合，得到最終的結(jié)果，并以鍵值對的形式輸出，這里的鍵值對格式為：Key<節(jié)點(diǎn)坐標(biāo)>、Value<新的節(jié)點(diǎn)數(shù)據(jù)集>，即依據(jù)節(jié)點(diǎn)的編號值次序生成節(jié)點(diǎn)信息文件，輸出的文件可直接用于后處理模塊.輸出的格式應(yīng)參照后處理階段的文件格式.

由于本并行算法是在對模型文件的節(jié)點(diǎn)數(shù)據(jù)集進(jìn)行分塊的基礎(chǔ)上實(shí)現(xiàn)的，各個(gè)塊的程式計(jì)算理論仍與串行計(jì)算一致，因而時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度亦為O(n).

分配算法將集成到整個(gè)并行處理系統(tǒng)中進(jìn)行驗(yàn)證.依據(jù)第1.2.1節(jié)的示例，后處理行為數(shù)據(jù)是程序計(jì)算輸出的結(jié)果也是以數(shù)組形式存儲的，每一幀的數(shù)據(jù)結(jié)構(gòu)與模型文件數(shù)據(jù)結(jié)構(gòu)類似.通過比較行為數(shù)據(jù)文件來驗(yàn)證算法的準(zhǔn)確性.

3.2算法驗(yàn)證環(huán)境及數(shù)據(jù)準(zhǔn)備

本文的Spark集群實(shí)驗(yàn)平臺由3臺普通PC機(jī)搭建，選擇其中性能較高的1臺PC作為主節(jié)點(diǎn)(Master)，運(yùn)行Master節(jié)點(diǎn)守護(hù)進(jìn)程，用于管理其他數(shù)據(jù)節(jié)點(diǎn)，其余2臺作為從節(jié)點(diǎn)(Slave)，運(yùn)行Slave節(jié)點(diǎn)守護(hù)進(jìn)程，作為MapReduce任務(wù)運(yùn)行的工作節(jié)點(diǎn).所有主機(jī)處于同一局域網(wǎng)中，在配置局域網(wǎng)IP后，Master與Slave節(jié)點(diǎn)之間通過安全外殼協(xié)議(SSH)方式驗(yàn)證.程序計(jì)算代碼由python實(shí)現(xiàn)，而且Spark平臺有針對python的接口，即pyspark，因而本實(shí)驗(yàn)采用Spark on YARN的運(yùn)行方式.

通過選取不同大小的模型文件進(jìn)行節(jié)點(diǎn)標(biāo)識及分配，并采用不同的分區(qū)個(gè)數(shù)，同時(shí)考慮劃分的分區(qū)個(gè)數(shù)對實(shí)驗(yàn)結(jié)果的影響.

本文通過4個(gè)空間桁架系統(tǒng)計(jì)算模型來驗(yàn)證并行算法的有效性和加速效果.前2個(gè)模型model1與model2采用桁架節(jié)點(diǎn)數(shù)目較小的結(jié)構(gòu)，后2個(gè)模型model3與model4則參照具體的工程實(shí)例，分別為鋼結(jié)構(gòu)桁架橋梁與單層鋼結(jié)構(gòu)廠房.

其中鋼結(jié)構(gòu)桁架橋梁的一些基本工程參數(shù)如表1所示.

表1　鋼結(jié)構(gòu)桁架橋梁結(jié)構(gòu)參數(shù)

鋼結(jié)構(gòu)廠房的基本參數(shù)如表2所示.

表2　鋼結(jié)構(gòu)廠房結(jié)構(gòu)參數(shù)

在創(chuàng)建以上2個(gè)工程實(shí)例模型時(shí)，外力作用均模擬橫向風(fēng)荷載.在本實(shí)驗(yàn)中，將桁架結(jié)構(gòu)模型的復(fù)雜程度按照模型中的節(jié)點(diǎn)數(shù)目以及桿件數(shù)目作為依據(jù)進(jìn)行分級，其中model1、model2、model3以及model4的節(jié)點(diǎn)數(shù)目和桿件數(shù)目分別如表3所示.

表3　測試模型信息

綜上所述，實(shí)驗(yàn)中用于測試的桁架結(jié)構(gòu)模型按照復(fù)雜程度由低到高依次為model1，model2，model3以及model4，在驗(yàn)證環(huán)節(jié)將通過對不同復(fù)雜程度的數(shù)據(jù)實(shí)驗(yàn)結(jié)果的對比，得出桁架結(jié)構(gòu)模型復(fù)雜程度與VFIFE串行計(jì)算和并行計(jì)算效率的關(guān)系，從而歸納出VFIFE復(fù)雜桁架結(jié)構(gòu)并行分布式處理技術(shù)的適用范圍.

3.3驗(yàn)證過程及結(jié)果分析

VFIFE復(fù)雜桁架結(jié)構(gòu)并行分布式處理實(shí)驗(yàn)包括并行計(jì)算實(shí)驗(yàn)與對照實(shí)驗(yàn)兩大部分.并行計(jì)算實(shí)驗(yàn)的目的是通過控制Spark計(jì)算平臺的分區(qū)數(shù)目來控制數(shù)據(jù)集的分區(qū)數(shù)目，從而研究分區(qū)數(shù)目與模型復(fù)雜程度的關(guān)系，尋找出各個(gè)模型的最佳分區(qū)數(shù)目.將最佳分區(qū)數(shù)目作為依據(jù)，與串行計(jì)算效率和傳統(tǒng)有限元分析效率進(jìn)行對比.根據(jù)第3.2節(jié)所描述的4種不同復(fù)雜程度的桁架結(jié)構(gòu)模型以及實(shí)驗(yàn)環(huán)境限制，將并行計(jì)算實(shí)驗(yàn)的分區(qū)數(shù)目劃分為4、8、12這3種.

對照實(shí)驗(yàn)的驗(yàn)證過程針對上一節(jié)中不同復(fù)雜程度的桁架結(jié)構(gòu)模型進(jìn)行，可分為橫向?qū)φ张c縱向?qū)φ?，橫向?qū)φ占磳φ詹煌瑥?fù)雜程度的桁架結(jié)構(gòu)模型在相同條件下的計(jì)算結(jié)果，目的是研究模型復(fù)雜程度對實(shí)驗(yàn)結(jié)果的影響.縱向?qū)φ談t針對各個(gè)模型比較，縱向?qū)φ諏?shí)驗(yàn)主要是桁架結(jié)構(gòu)VFIFE并行分布式處理與VFIFE程序串行計(jì)算效率的對照，將根據(jù)程序計(jì)算的迭代次數(shù)進(jìn)行分類，進(jìn)一步探尋桁架結(jié)構(gòu)VFIFE程序計(jì)算中迭代次數(shù)與并行分布式處理效率的關(guān)系.

在對照實(shí)驗(yàn)中，向量式有限元的串行和并行等不同計(jì)算方式的計(jì)算效率則通過比較加速比ζ=t3/t4來分析，其中t3為串行計(jì)算時(shí)程序執(zhí)行時(shí)間，t4則為相同任務(wù)量的前提下，采用并行計(jì)算算法時(shí)程序執(zhí)行時(shí)間.

在所有上述實(shí)驗(yàn)中，最后都會將生成的行為數(shù)據(jù)輸入到后處理模塊中進(jìn)行展示，得到更直觀的結(jié)果.

對于第3.2節(jié)中創(chuàng)建的4個(gè)不同復(fù)雜程度的桁架結(jié)構(gòu)模型進(jìn)行并行計(jì)算，迭代次數(shù)設(shè)定為10 000次，將實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)并整理后得到圖3.

圖3　不同桁架結(jié)構(gòu)模型在不同分區(qū)數(shù)目下的計(jì)算時(shí)間

根據(jù)上述分析，由于硬件環(huán)境限制，本文的集群能運(yùn)行的最大分區(qū)約為12，當(dāng)繼續(xù)增加分區(qū)數(shù)量時(shí)只會增加排隊(duì)等待時(shí)間的開銷，而不能繼續(xù)大幅度提升計(jì)算效率.因此，可以選取分區(qū)數(shù)=8作為計(jì)算各個(gè)模型的分區(qū)數(shù)目來進(jìn)行對照實(shí)驗(yàn).

圖4為對照實(shí)驗(yàn)中，不同模型在不同迭代次數(shù)下并行計(jì)算相對串行計(jì)算的加速比.

圖4　　　　不同規(guī)模桁架模型在不同迭代次數(shù)下并行相對串行的計(jì)算加速比

Fig.4Speedup of parallel computing compared to serial computing dealing with different scales of models in different iterations

對比以上結(jié)果，分析VFIFE復(fù)雜桁架結(jié)構(gòu)并行分布式處理相對串行計(jì)算的加速比，可以得到以下結(jié)論：

(1) 相對于串行計(jì)算，隨著計(jì)算規(guī)模的增加，即桁架結(jié)構(gòu)模型復(fù)雜程度的增加，并行計(jì)算能發(fā)揮出更好的性能.

(2) 在同一個(gè)復(fù)雜模型中，進(jìn)行的迭代次數(shù)越多，并行計(jì)算的加速效果也更明顯.這種加速效果在model1和model2中并不明顯，但對于復(fù)雜程度較高的模型model3和model4，數(shù)據(jù)分塊后并行計(jì)算帶來的效益越高.

(3) model1以及model2的數(shù)據(jù)量相對較小，并行計(jì)算耗時(shí)略多于串行計(jì)算耗時(shí)，這可能是由于時(shí)間消耗在每一次迭代開始前，各個(gè)分區(qū)中的分割桿件兩端節(jié)點(diǎn)需依據(jù)RDD中的數(shù)據(jù)同步.但總的來說，隨著計(jì)算量的增加，并行計(jì)算的效率也越來越高，且與并行計(jì)算時(shí)分配的計(jì)算分區(qū)數(shù)目成一定正比關(guān)系.

4　結(jié)論與展望

(1) 本文針對節(jié)點(diǎn)數(shù)據(jù)集node采用的節(jié)點(diǎn)分配機(jī)制不會對計(jì)算結(jié)果產(chǎn)生影響，因?yàn)榉峙浜蟮拿總€(gè)分區(qū)仍采用相同的計(jì)算流程.

(2) 對于數(shù)據(jù)量較大的桁架結(jié)構(gòu)模型的計(jì)算，如節(jié)點(diǎn)數(shù)超過1 000，采用并行計(jì)算可使計(jì)算效率實(shí)現(xiàn)大幅提升.

(3) 在計(jì)算量較大的情況下，并行計(jì)算的效率與節(jié)點(diǎn)分配劃分成的分區(qū)個(gè)數(shù)成一定正比關(guān)系，即分區(qū)的塊越多，計(jì)算效率的提升越明顯.

此后的研究應(yīng)考慮劃分更多塊進(jìn)行計(jì)算，找到最佳分塊個(gè)數(shù).完善程式計(jì)算理論，實(shí)現(xiàn)并行算法的通用性.

參考文獻(xiàn):

[1]Ting E C, Shih C, Wang Y K. Fundamentals of a vector form intrinsic finite element. Part I: basic procedure and a plane frame Element[J]. Journal of Mechanics, 2004, 20(2):113.

[2]Ting E C, Shih C, Wang Y K. Fundamentals of a vector form intrinsic finite element. Part Ⅱ: plane solid elements[J]. Journal of Mechanics, 2004, 20(2):123.

[3]Ting E C, Shih C, Wang Y K. Fundamentals of a vector form intrinsic finite element. Part Ⅲ: convected material frame and examples[J]. Journal of Mechanics, 2004, 20(2):133.

[4]盧哲剛，姚諫.向量式有限元：一種新型的數(shù)值方法[J].空間結(jié)構(gòu), 2012,18(1): 85.

LU Zhegang, YAO Jian. Vector form intrinsic finite element:a new numerical method [J]. Spatial Structures, 2012, 18(1): 85.

[5]杜慶峰，周曉瑋，謝濤，等. 大規(guī)模向量式有限元行為數(shù)據(jù)壓縮模型及算法[J]. 同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2014, 42(11): 14.

DU Qingfeng, ZHOU Xiaowei, XIE Tao,etal. Massive vector form intrinsic finite element behavior data compression model and algorithm[J]. Journal of Tongji University: Natural Science, 2014, 42(11): 14.

[6]杜慶峰，周雪非，謝濤，等. 大規(guī)模向量式有限元行為數(shù)據(jù)無損壓縮模型[J]. 同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2015, 43(1): 19.

DU Qingfeng, ZHOU Xuefei, XIE Tao,etal. Massive vector form intrinsic finite element behavior data lossless compression model[J]. Journal of Tongji University: Natural Science, 2015, 43(1): 19.

[7]劉耀儒，周維垣，楊強(qiáng). 三維有限元并行EBE方法[J].工程力學(xué)，2006，23(3): 27.

LIU Yaoru, ZHOU Weiyuan, YANG Qiang. Parallel 3D finite element analysis based on EBE method[J]. Engineering Mechanics,2006, 23(3): 27.

[8]符偉. 云計(jì)算環(huán)境下的線性有限元方法研究[D]. 武漢：華中科技大學(xué), 2013.

FU Wei. Study on linear finite element method in cloud computing[D]. Wuhan: Huazhong University of Science and Technology, 2013.

[9]江雄心, 萬平榮. 三維有限元網(wǎng)格節(jié)點(diǎn)編號優(yōu)化[J]. 工程圖學(xué)學(xué)報(bào), 2008, 29(4): 22.

JIANG Xiongxin, WAN Pingrong. Optimization of node numbering in 3D finite element[J]. Journal of Engineering Graphics, 2008,29(4):22.

[10]倪秋斌，丁從潮，高博青，等.基于向量式結(jié)構(gòu)力學(xué)的空間桁架非線性靜力分析[J].空間結(jié)構(gòu), 2013, 19(3): 33.

NI Qiubin, DING Congchao, GAO Boqing,etal. Nonlinear static analysis of space truss using vector mechanics of structure[J]. Spatial Structures, 2013, 19(3): 33.

[11]荊國強(qiáng), 陳德偉. 一種基于代數(shù)圖論的有限元模型節(jié)點(diǎn)排序方法[J]. 同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版, 2010, 38(6): 929.

JING Guoqiang, CHEN Dewei. A finite element nodal ordering with algebraic graph theory[J]. Journal of Tongji University: Natural Science, 2010, 38(6): 929.

[12]姜濤, 王安麟, 朱燈林. 有限元結(jié)點(diǎn)編號的綜合帶寬優(yōu)化算法[J]. 機(jī)械設(shè)計(jì), 2005, 22(11): 3.

JIANG Tao, WANG Anlin, ZHU Denglin. Synthetic bandwidth optimization algorithm of finite element node numbering[J]. Journal of Machine Design,2005, 22(11): 3.

[13]賈建軍, 彭穎紅. 三種基于圖論的有限元結(jié)點(diǎn)編號優(yōu)化算法[J]. 機(jī)械科學(xué)與技術(shù), 1998, 17(5): 725.

JIA Jianjun, PENG Yinghong. Three graph theory based algorithms on FEM node ordering optimization[J]. Mechanical Science & Technology, 1998, 17(5): 725.

[14]梁彥. 基于分布式平臺Spark和YARN的數(shù)據(jù)挖掘算法的并行化研究[D]. 中山：中山大學(xué), 2014.

LIANG Yan. Research on parallelization of data mining algorithm based on distributed platform Spark and YARN[D]. Zhongshan: Zhongshan University, 2014.

收稿日期：2015-09-27

基金項(xiàng)目：國家自然科學(xué)基金(41171303)

中圖分類號：TN919

文獻(xiàn)標(biāo)志碼：A

Node Distributing Technology for Parallel Computing of Spatial Truss Structure Using Vector Form Intrinsic Finite Element

DU Qingfeng, WU Han

(School of Software Engineering, Tongji University, Shanghai 201804, China)

Abstract：After studying the computation rules in vector form intrinsic finite element(VFIFE) and the feature of spatial truss structure, a node distributing mechanism for parallel computing was proposed. According to the defined rules of decomposing, the model data of spatial truss structure were dynamically decomposed. Based on the results of decomposition, the data sets of nodes were dynamically decomposed, and the parallel computing was accomplished in the specific frame. The numerical experiments indicate that, the node distributing mechanism greatly improves the speed of spatial truss structure analysis, in contrast with those based on serial computing or classical finite element method.

Key words：vector form intrinsic finite element(VFIFE); spatial truss structure; parallel computing

第一作者： 杜慶峰(1968—)，男，教授，博士生導(dǎo)師，工學(xué)博士，主要研究方向?yàn)檐浖y試、計(jì)算機(jī)相關(guān)學(xué)科交叉領(lǐng)域.

E-mail：du_cloud@#edu.cn