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

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

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

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

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