基于多核环境下受限voronoi图的研究和实现

《基于多核环境下受限voronoi图的研究和实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学硕士学位论文多核环境下受限Voronoi图的研究和实现姓名：吴媛申请学位级别：硕士专业：计算机软件与理论指导教师：董兰芳20100401摘要Voronoi图作为空间离散划分的基本几何结构单元，是计算几何领域重要的研究方向之一。Voronoi图因其垂直平分的特性，特别适用于利用有限体积法求解如液体间流动、热传导等具有某种守恒性质的物理问题，但是在这些应用中，对Voronoi图的生成有特殊的限定条件，以油藏模拟为例，生成的Voronoi网格单元不能跨越边界、断层等物理障碍，对于一些特殊的点，如水平井点和垂直井点必须为Voronoi网格的中

2、心点。由于实际应用中对受限Voronoi图的需求，以及受限情况下构造高质量的Voronoi网格需要进行大规模数据的计算处理，因此有必要对受限Voronoi网格的构造及其并行化算法进行研究和实现。在现有的单机单核的计算能力下，处理大规模数量的网格生成，算法效率低下，计算时间无法接受，而在大型并行处理机进行数据处理，成本高，用户操作不便。随着硬件处理器的快速发展，以异构多核为特征的众核处理器已成为目前高性能计算的主流趋势，因此，结合实际需求，本文提出了在多核环境下利用MPI并行编程语言实现高效、可用的网格生成并行算法，具体研究成果和内容包括以下几个方面：

3、(1)根据Delaunay图是Voronoi图的对偶图的性质，使用间接法实现Voronoi图构造算法，生成网格结构饱满，质量高，但运行速度较慢。(2)基于算法并行化考虑，采用最优算法一分治法来实现带有限定情况的受限Voronoi图的生成。根据两个限定条件(限定点和限定线原则)，对各种限定情况做了分析处理，为后期生成高质量的网格进行合理布点。(3)利用分治法构造大规模点集的Voronoi网格，同时设计修改了数据结构．双向循环链表(Doubly-connectededgelist，Dcel)，使之符合并行处理和限定Voronoi复杂边界的特点。(4)使用

4、MPI和C语言，采取逐步合并的整体并行方案，对合理布点的点集生成和Voronoi构造做了并行化处理，在大型惠普并行机和异构多核单机上分别进行了运算，得到实验结果。(5)Voronoi对偶图Delaunay的转换实现，最终对数据进行处理实现图形的实时显示。摘要(6)最后，本文对基于Voronoi图技术未来的研究方向，进行了展望。本文的研究成果可应用于模拟流体流动，建模绘制等领域，结合多核处理器和并行计算高速发展的时代特点，用于各种模拟问题的实时计算。关键词：受限Voronoi、Delaunay三角剖分、分治算法、并行计算、MPI、异构多核Abstrac

5、tABSTRACTAsabasicdatastructureelementofdiscretespacedivision，Voronoimeshisanimportantresearchdirectioninthefieldofcomputationalgeometry．Becauseofthecharacteristicofperpendicularbisector,Voronoimeshespeciallysuitableforsolvingsomephysicalproblemsrelatedtoconservationnaturebythem

6、ethodoffinitevolume，suchasfluidflow,heatconductionandSOon．However,intheseapplicationareas，thegenerationoftheVoronoidiagramhasaspecialqualification，taketheexampleofreservoirsimulation，theVoronoimeshCannotcrosssomephysicalbarriers，liketheborderandfaults．Forsomeparticularpoints，su

7、chashorizontalwellandverticalwellmustbethecenteroftheVoronoimesh．ConsidertherequirementofconstructinglimitedVoronoimeshinsomepracticalapplicationsandtheproblemofconstructinghigh—qualityVoronoimeshunderthecomplexconstrainedconditionsthroughlarge—scaledataprocessing，researchandim

8、plementationoflimitedVoronoimeshgenerationanditsparall