針對(duì)求解有限元分析的特征值問(wèn)題,提出了一種隱式重啟動(dòng)Arnoldi/Lanczos方法的子區(qū)域并行算法。隱式重啟動(dòng)Arnoldi/Lanczos利用重啟動(dòng)技術(shù)以提高所需譜的收斂性,并能有效處理Krylov基形成問(wèn)題、存儲(chǔ)所需的內(nèi)存問(wèn)題、計(jì)算成本問(wèn)題。并行算法中采取子區(qū)域接子區(qū)域方法、重疊和非重疊網(wǎng)格劃分技術(shù)。采用壓縮數(shù)據(jù)結(jié)構(gòu)來(lái)儲(chǔ)存系數(shù)矩陣。對(duì)Krylov的數(shù)值線性代數(shù)運(yùn)算和隱式重啟動(dòng)法中的數(shù)值線性代數(shù)運(yùn)算的并行化進(jìn)行了研究。數(shù)值算例表明:該算法具有良好的適用性和效率,適合分布式儲(chǔ)存體系的機(jī)群。 

【文章來(lái)源】：應(yīng)用力學(xué)學(xué)報(bào). 2017,34(02)北大核心

【文章頁(yè)數(shù)】：8 頁(yè)

【部分圖文】：

非重疊網(wǎng)格劃分方式

226應(yīng)用力學(xué)學(xué)報(bào)第34卷(N1)，位于劃分界面上的節(jié)點(diǎn)分為主邊界節(jié)點(diǎn)(N2)和從屬邊界節(jié)點(diǎn)(N3)，界面節(jié)點(diǎn)在第i個(gè)子區(qū)域中為主邊界節(jié)點(diǎn)，而在共享該節(jié)點(diǎn)的所有其它子區(qū)域中為從屬邊界節(jié)點(diǎn)。不包含邊界節(jié)點(diǎn)的單元為內(nèi)部單元，而包含邊界節(jié)點(diǎn)的單元為邊界單元。區(qū)域劃分如圖3所示。圖3非重疊網(wǎng)格劃分方式Fig.3Anon-overlappingmeshpartitioningscheme圖4重疊網(wǎng)格劃分方式Fig.4Anoverlappingmeshpartitioningscheme3.2重疊劃分對(duì)重疊區(qū)域劃分，定義一組由其它分區(qū)的節(jié)點(diǎn)組成新節(jié)點(diǎn)，稱為虛節(jié)點(diǎn)(N4)，由主邊界節(jié)點(diǎn)N2和虛節(jié)點(diǎn)N4構(gòu)成共享單元，將一組共享單元加到非重疊區(qū)域的網(wǎng)格形成重疊區(qū)域。圖4表示重疊區(qū)域劃分。3.3壓縮數(shù)據(jù)結(jié)構(gòu)壓縮數(shù)據(jù)結(jié)構(gòu)，如壓縮稀疏行格式是基于圖的數(shù)據(jù)結(jié)構(gòu)。在有限元方法中，關(guān)聯(lián)到網(wǎng)格的圖總是無(wú)指向的，即，如果元素0ijk≠，那么元素0jik≠。文獻(xiàn)[16]提出了一個(gè)CSR的變化格式，稱為壓縮稀疏行列格式(CSRC)。在CSRC格式中，對(duì)角線以下的非零元素存儲(chǔ)在CSR格式，而對(duì)角線以上的非零元素存儲(chǔ)在壓縮稀疏列格式(CSC)。對(duì)角線的元素存儲(chǔ)在一個(gè)單獨(dú)的數(shù)組ad中、數(shù)組au存儲(chǔ)上半部分，數(shù)組al存儲(chǔ)下半部分。第i行的第一個(gè)元素用ia(i)定位，另一個(gè)數(shù)組ja存儲(chǔ)元素ijk的列號(hào)。CSRC格式的主要優(yōu)點(diǎn)是只需要存儲(chǔ)數(shù)組ja所需內(nèi)存的一半；用來(lái)存儲(chǔ)非對(duì)角元素的兩個(gè)數(shù)組能更快地進(jìn)行內(nèi)存訪問(wèn)。采取CSRC格式，算法3描述非對(duì)稱情況下矩陣向量積的算法。doi=1，n/循環(huán)(loopover)ui=u(i)t=ad(i)*uidok=ia(i)，ia(i+1)－1/對(duì)方程i的下部非零項(xiàng)循環(huán)(loopoverthelowernonzeroentriesofequationi)jak=ja(k)t=t+al(k)*u(jak)p(jak)=p(jak)+au(k)*ui/上部列(uppercolumn)enddop(i)=tenddo圖5非對(duì)稱

，需要進(jìn)行三級(jí)運(yùn)算。Hk=QTHkQ，Tk=QTTkQ，Vk=VkQ(18)矩陣Q是Hk或Tk的一個(gè)因子，由于這些矩陣已復(fù)制，因而不需要進(jìn)行通信。4數(shù)值算例本文數(shù)值計(jì)算是在DELL工作站機(jī)群上進(jìn)行。該機(jī)群由4臺(tái)雙CPU的DELL工作站通過(guò)100.0Mbps以太網(wǎng)連接而成，共有8個(gè)CPU(2.4GHzXeonchips，512KBcache)，每個(gè)節(jié)點(diǎn)內(nèi)存1.0GB。每臺(tái)工作站都有真實(shí)的IP地址，使用消息傳遞接口(MPI)。操作系統(tǒng)為RedHatLinux9.0。4.1對(duì)稱問(wèn)題算例為測(cè)試算法的性能，以壩體及地基的二維平面應(yīng)變模型作為算例，如圖9所示，計(jì)算其特征值和特征向量。采用兩個(gè)隱式重啟動(dòng)，建立一個(gè)50步的Lanczos分解，特征值收斂容許值取為1×10-10。進(jìn)行重疊和非重疊區(qū)域劃分，整個(gè)區(qū)域劃分為與處理器數(shù)相等的子區(qū)域，每個(gè)子區(qū)域有大約相等的單元數(shù)。每個(gè)子區(qū)域映射到各相應(yīng)的處理器。各處理器得到子區(qū)域單元數(shù)據(jù)后，相應(yīng)子區(qū)域中的計(jì)算在各處理器中進(jìn)行。劃分的網(wǎng)格包含273827個(gè)8節(jié)點(diǎn)二次單元、1647436個(gè)自由度。圖9壩體及其地基的計(jì)算模型Fig.9Themodelofdamandfoundation為評(píng)價(jià)并行性能，分別用1個(gè)、2個(gè)、4個(gè)、6個(gè)、8個(gè)處理器對(duì)所求問(wèn)題進(jìn)行求解。圖10和圖11分別顯示了非重疊和重疊劃分的算法加速比和效率，可見(jiàn)非重疊劃分較重疊劃分的加速比要大，計(jì)算性能更好。從中也可發(fā)現(xiàn)，隨著處理器數(shù)的增加，計(jì)算性能變差，這是由于出現(xiàn)大部分?jǐn)?shù)據(jù)通信和同步的PCG迭代部分增加，以及問(wèn)題的粒度減小而造成，因而通信開(kāi)銷增加。圖10對(duì)稱問(wèn)題算例的并行加速比Fig.10Parallelspeedupforsymmetriccase圖11對(duì)稱問(wèn)題算例的并行效率Fig.11Parallelefficiencyforsymmetriccase圖12非對(duì)稱問(wèn)題算例的并行加速比Fig.12Parallelspeedupfornon-symme


本文編號(hào)：2998082