發(fā)布時間：2018-01-09 12:22

  本文關(guān)鍵詞：多線程并行四面體網(wǎng)格優(yōu)化算法　出處：《浙江大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 網(wǎng)格生成 網(wǎng)格優(yōu)化 非結(jié)構(gòu)網(wǎng)格 并行算法 多線程

【摘要】：有限元法廣泛應(yīng)用于科學(xué)研究與工程設(shè)計計算,其關(guān)鍵環(huán)節(jié)之一是輸入數(shù)據(jù)的準(zhǔn)備,即有限元網(wǎng)格生成。一方面,網(wǎng)格生成涉及的人工工作量通常占據(jù)完成數(shù)值模擬全過程人工工作總量的絕大部分,是主要性能瓶頸。另一方面,網(wǎng)格質(zhì)量是影響數(shù)值模擬計算精度和計算效率至關(guān)重要的因素。四面體網(wǎng)格適應(yīng)任意復(fù)雜外形,自動生成和自適應(yīng)更新能力強(qiáng),在有限元分析中得到廣泛采用。因邊界約束和網(wǎng)格生成算法內(nèi)在的原因,主流算法生成的初始四面體網(wǎng)格都會包含一定數(shù)量的低質(zhì)量單元,需結(jié)合光滑化與拓?fù)渥儞Q等局部網(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)化算法包含的光滑化和拓?fù)渥儞Q等2類不同的局部編輯操作,開發(fā)了對應(yīng)的任務(wù)分解策略以及相應(yīng)的多線程并行算法。并行光滑化算法的任務(wù)分解策略采用經(jīng)典的圖著色算法,首先基于網(wǎng)格節(jié)點鄰接關(guān)系構(gòu)建鄰接關(guān)系圖,再通過對鄰近關(guān)系圖著色將待光滑點分解為多個獨立點集。因每個點集中的點相互之間均不相鄰,多個線程可同時移動對應(yīng)點集中的點以優(yōu)化鄰接單元質(zhì)量。并行拓?fù)渥儞Q算法的任務(wù)分解策略是本文的主要創(chuàng)新,其主要步驟如下:(1)計算待執(zhí)行變換操作涉及到的四面體單元的特征點坐標(biāo);(2)基于特征點位置利用希爾伯特曲線對所有操作進(jìn)行線性化排序;(3)將排序后的操作按序等分成與線程數(shù)相等的子集。拓?fù)渥儞Q算法的操作定義在四面體單元形成的空腔上執(zhí)行。網(wǎng)格優(yōu)化時,單個線程按序處理所分配子集中的局部操作。如不同線程同時執(zhí)行的局部操作涉及的空腔出現(xiàn)干涉,只允許其中1個線程執(zhí)行操作,其余線程放棄執(zhí)行本次操作。因不同線程同時執(zhí)行的操作在希爾伯特曲線上相距足夠遠(yuǎn),這些操作對應(yīng)的空腔相互干涉的概率非常低,上述處理干涉情形的策略既易于實現(xiàn),引起的性能損失也被證明可以接受。本文有針對性地提出了多項加速算法并行性能的技術(shù),基于共享內(nèi)存并行編程語言O(shè)penMP開發(fā)了一套集成上述并行拓?fù)渥儞Q與并行光滑化算法在內(nèi)的多線程并行四面體網(wǎng)格優(yōu)化算法,選取典型輸入研究了該算法的并行性能,初步驗證了算法的有效性和適用性。
[Abstract]:Finite element method is widely used in scientific research and engineering design, one of the key links is the input data for the finite element mesh generation. On the one hand, the workload of artificial mesh generation involved usually occupy complete numerical simulation for the whole process of artificial work most of the total, is the main performance bottleneck. On the other hand, the grid quality is the simulation factors influencing the calculation accuracy and efficiency of the critical value. The tetrahedral mesh to arbitrary complex shape, automatic generation and adaptive updating ability, has been widely used in finite element analysis. Due to boundary constraints and grid generation algorithm inside, low quality unit mainstream algorithm to generate the initial tetrahedral mesh will contain a certain the number should be combined with local mesh smoothing and topology editing to be optimized, to satisfy the needs of finite element analysis For as much as possible to improve the quality of the grid, grid optimization iteration called local mesh editing operations, very time-consuming. Data show that during the optimization process than using fast Delaunay triangulation algorithm to generate the same size grid was 5 times slower. Large tetrahedral mesh generation practice, mesh optimization has become the main performance bottleneck for this. In this paper, the typical tetrahedral mesh optimization algorithm includes smoothing and topological transformation for 2 different local editing operations, developed the corresponding task decomposition strategy and multi thread parallel algorithm. And the corresponding line smoothing algorithm for task decomposition strategy using graph coloring algorithm, based on the grid node adjacency adjacency relation construction map through the neighborhood graph coloring to smooth point is decomposed into several independent sets. For each point between the points are not. Next, multiple threads can also move the corresponding point of concentration to optimize adjacent element quality. Parallel topology transform algorithm of task decomposition strategy is the main innovation of this paper, the main steps are as follows: (1) to compute feature points perform tetrahedron transform operation involving the coordinates; (2) the feature point location the linear order of all operations by using the Hilbert curve based on; (3) after the operation will be sorted into subsets and thread is equal to the number of sequential execution. Equal operational definition of topological transformation algorithm of cavity formation in tetrahedral mesh optimization. When the local operation of a single thread in order processing sub concentrated. The local cavity operation at the same time to perform different threads to interference, allowing only 1 threads operate the remaining threads to give up the implementation of this operation. Because of simultaneous execution of different threads operating in the Hilbert song The line is far enough, the probability of interference between the cavity corresponding to these operations is very low, the interference strategy is easy to implement, the performance loss caused also proved acceptable. This paper puts forward several accelerated algorithm of parallel performance technology, shared memory parallel programming language OpenMP to develop a set of integrated above parallel topological transformation and parallel smoothing algorithm, multi thread parallel tetrahedral mesh optimization algorithm based on the parallel performance of the algorithm selects the typical input, verify the validity and applicability of the algorithm.

【學(xué)位授予單位】：浙江大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TB115

【共引文獻(xiàn)】

相關(guān)期刊論文 前3條

1 王曉偉;胡慧芳;;錳摻雜鋸齒型石墨烯納米帶電磁學(xué)特性研究[J];材料導(dǎo)報;2014年24期

2 黃向前;林陳f ;尹秀麗;趙汝光;王恩哥;胡宗海;;一維石墨烯超晶格上的氫吸附[J];物理學(xué)報;2014年19期

3 王森;戴振宏;劉兵;徐雷;;氧鈍化圓形孔缺陷石墨烯的電學(xué)特性[J];煙臺大學(xué)學(xué)報(自然科學(xué)與工程版);2014年03期

，

本文編號：1401389