多線程并行四面體網(wǎng)格優(yōu)化算法.pdf

1、有限元法廣泛應(yīng)用于科學(xué)研究與工程設(shè)計(jì)計(jì)算，其關(guān)鍵環(huán)節(jié)之一是輸入數(shù)據(jù)的準(zhǔn)備，即有限元網(wǎng)格生成。一方面，網(wǎng)格生成涉及的人工工作量通常占據(jù)完成數(shù)值模擬全過(guò)程人工工作總量的絕大部分，是主要性能瓶頸。另一方面，網(wǎng)格質(zhì)量是影響數(shù)值模擬計(jì)算精度和計(jì)算效率至關(guān)重要的因素。
　　四面體網(wǎng)格適應(yīng)任意復(fù)雜外形，自動(dòng)生成和自適應(yīng)更新能力強(qiáng)，在有限元分析中得到廣泛采用。因邊界約束和網(wǎng)格生成算法內(nèi)在的原因，主流算法生成的初始四面體網(wǎng)格都會(huì)包含一定數(shù)量的低質(zhì)量

2、單元，需結(jié)合光滑化與拓?fù)渥儞Q等局部網(wǎng)格編輯操作予以優(yōu)化調(diào)整后，才能滿足后續(xù)有限元分析的要求。為盡可能提高網(wǎng)格質(zhì)量，網(wǎng)格優(yōu)化需循環(huán)迭代調(diào)用局部網(wǎng)格編輯操作，非常耗時(shí)。有數(shù)據(jù)表明，優(yōu)化過(guò)程比利用快速Delaunay三角化算法生成同等規(guī)模網(wǎng)格的過(guò)程要慢5倍以上。大規(guī)模四面體網(wǎng)格生成實(shí)踐中，網(wǎng)格優(yōu)化已成為主要的性能瓶頸。
　　為此，本文針對(duì)典型四面體網(wǎng)格優(yōu)化算法包含的光滑化和拓?fù)渥儞Q等2類不同的局部編輯操作，開(kāi)發(fā)了對(duì)應(yīng)的任務(wù)分解策略以及相

3、應(yīng)的多線程并行算法。并行光滑化算法的任務(wù)分解策略采用經(jīng)典的圖著色算法，首先基于網(wǎng)格節(jié)點(diǎn)鄰接關(guān)系構(gòu)建鄰接關(guān)系圖，再通過(guò)對(duì)鄰近關(guān)系圖著色將待光滑點(diǎn)分解為多個(gè)獨(dú)立點(diǎn)集。因每個(gè)點(diǎn)集中的點(diǎn)相互之間均不相鄰，多個(gè)線程可同時(shí)移動(dòng)對(duì)應(yīng)點(diǎn)集中的點(diǎn)以優(yōu)化鄰接單元質(zhì)量。
　　并行拓?fù)渥儞Q算法的任務(wù)分解策略是本文的主要?jiǎng)?chuàng)新，其主要步驟如下:
　　(1)計(jì)算待執(zhí)行變換操作涉及到的四面體單元的特征點(diǎn)坐標(biāo);
　　(2)基于特征點(diǎn)位置利用希爾伯特曲線

4、對(duì)所有操作進(jìn)行線性化排序;
　　(3)將排序后的操作按序等分成與線程數(shù)相等的子集。
　　拓?fù)渥儞Q算法的操作定義在四面體單元形成的空腔上執(zhí)行。網(wǎng)格優(yōu)化時(shí)，單個(gè)線程按序處理所分配子集中的局部操作。如不同線程同時(shí)執(zhí)行的局部操作涉及的空腔出現(xiàn)干涉，只允許其中1個(gè)線程執(zhí)行操作，其余線程放棄執(zhí)行本次操作。因不同線程同時(shí)執(zhí)行的操作在希爾伯特曲線上相距足夠遠(yuǎn)，這些操作對(duì)應(yīng)的空腔相互干涉的概率非常低，上述處理干涉情形的策略既易于實(shí)現(xiàn)，引起的性