基于OpenMP的三维并行Delaunay网格生成算法及实现

针对大多数并行Delaunay网格生成算法无法充分利用多核共享内存结构的问题,在原有面向共享内存的二维并行算法基础上,根据三维问题的特点提出基于OpenMP的三维并行Delaunay网格生成算法。算法采用划分求解区域为方格的方法实现候选点集的划分和并行插点。使用OpenMP对算法进行实现,并利用多种实现技术避免线程间的同步等待,提升算法效率。实验结果表明,本文算法及所采用的实现技术可以在三维条件下快速生成大量网格单元,具有较高的并行效率,同时能够保证良好的网格质量。     

一种网格和节点同步生成的二维Delaunay网格划分算法

应用Lawson算法对网格的Delaunay性质进行维护,利用单元尺度场控制生成网格的疏密分布;找到任一不满足尺度场要求的单元,在其可插度最大的边上按一定法则插入新节点,加密网格,实现内节点的生成与网格划分同步进行.该算法避免了搜寻包含三角形的过程,提高了效率.通过多次划分实验表明,该算法的时间复杂度约为O(N1.2).同时,由于在不满足单元尺寸要求的单元边上插入新节点,直接对单元的边长进行控制,使得网格的质量和自适性更加良好.     

基于无锁原子操作的多线程并行Delaunay三角化算法

基于OpenMP实现了一种基于空腔交叠互斥准则与无锁原子操作的Delaunay三角化增量插点细粒度并行算法。在串行算法的基础上,对点集引入Hilbert排序,使相邻点在几何上亦相邻。引入互斥机制--仅当各空腔无公共单元及公共相邻边时,才可同时插入,根据Delaunay局部性准则可保证整个网格都具备Delaunay属性。每个单元用一个原子变量标记该单元是否已被占有,在计算Delaunay空腔时,各线程将试图写入该原子变量,但本竞争机制保证有且仅有一个线程能成功获得该单元的所有权,以保证算法的互斥性。经数值实验表明,对于107的点集,该算法在16核下加速比可达7.06倍。     

基于Delaunay三角形的三维数字地图生成算法

潜艇应用地形匹配技术是近年来导航技术领域的研究新方向，而海底数字地图的制作是潜艇海底地形匹配定位技术的基础。该文首先给出了电子海图水深数据的提取方法，然后基于处理大规模散乱数据的Delsunay三角形，提出了一种利用电子海图水深数据模拟形成三维数字高程模型(DEM)的算法，最后进行了数字仿真，仿真结果证明该算法是可行的。该文提出的新思路对海底数字地图的模拟具有重要的参考价值，为海底地形匹配定位技术的研究提供了必要的前提。     

Delaunay四面体网格并行生成算法研究进展

纵观近20年国内外Delaunay四面体网格并行生成算法的发展,依据其并行框架分为区域分解模式和基于节点模式,其中区域分解模式根据通信复杂程度进一步分为耦合的和非耦合的;对典型算法中网格质量传承性、串行代码嵌入率、扩展性、负载平衡和容错性等性能进行分析,结合数值测试结果总结了各类模式算法的优缺点.最后,针对各类模式算法的特点探讨了Delaunay四面体网格并行生成技术的发展趋势.     

KMAS网格自动生成系统

KMAS网格自动生成系统采用超限插值法和Delaunay三角剖分法,可对一般复杂覆盖件自动快速生成三角形或混合型有限元网格,网格质量较好,速度较快,还可根据用户需要消除孔洞,适合冲压分析的需要。     

Delaunay三角网生成算法的研究与实现

Delaunay三角网作为一种主要的数字地形模型表示法,经过二十多年来的研究,它的生成算法已趋于成熟。本文在简单回顾和评价了分割—归并法、逐点插入法、三角网生长法等三类主流算法的基础上,介绍并实现了一个融以上算法优点于一体,兼顾空间与时间性能的合成算法。     

面向云计算环境的OpenFOAM网格生成服务

网格生成是计算流体力学仿真分析基础.由于网格生成的计算量大,适合利用服务器的高性能计算能力在服务器端运行,以云服务方式为用户提供高效的网格生成服务.提出了 一种面向云计算的网格生成服务模型,基于该模型能够对传统的单机版网格生成模块进行服务化封装,实现网格生成的云服务.采用该模型对OpenFOAM的网格生成模块进行服务化...     

Parallel divide‐and‐conquer scheme for 2D Delaunay triangulation

This work describes a parallel divide‐and‐conquer Delaunay triangulation scheme. This algorithm finds the affected zone, which covers the triangulation and may be modified when two sub‐block triangulations are merged. Finding the affected zone can reduce the amount of data required to be transmitted between processors. The time complexity of the divide‐and‐conquer scheme remains O(n log n), and the affected region can be located in O(n) time steps, where n denotes the number of points. The code was implemented with C, FORTRAN and MPI, making it portable to many computer systems. Experimental results on an IBM SP2 show that a parallel efficiency of 44–95% for general distributions can be attained on a 16‐node distributed memory system. Copyright © 2006 John Wiley & Sons, Ltd.     

基于分布式共享存储器的并行程序设计

本文概述了分布式并行系统和分布式共享存储器的一般概念，讨论了使用共享对象和可靠广播的并行程序设计模型，最后给出了我们的改进模型。     

松散耦合系统上的共享存贮并行计算

介绍工作站网络上并行计算的概念，意义，和计算模型，重点讨论了基于分布式共享存贮器的网络并行计算，提出了作者自己的思想方法和并行程序设计模型。     

一种基于共享存储的叠前深度偏移并行算法

为了解决叠前深度偏移计算量巨大这个问题,人们投入了很大精力来开发高效的并行算法.就此,在对一些相关并行算法进行分析之后,根据三维叠前Kirchhoff深度偏移的特点,提出了一种基于共享存储的简化并行算法.其中Slave进程直接存储和读取射线旅行时,消息传递总量显著减少;同时合理地结合"任务池"技术与粗粒度级并行,前者确保动态负载平衡,后者使得Slave与Master之间的通信开销尽可能小.实际数据的测试结果表明,此并行算法高效且可扩展性较好.     

Poisson-Boltzmann方程的并行有限元求解及网格自适应生成

说明如何利用并行自适应有限元软件平台PHG 求解生物分子溶液体系的非线性Poisson-Boltzmann方程,并介绍一种解决这类问题的方法,它将网格生成与自适应计算过程结合在一起,可自动产生合适的网格,避免复杂的曲面网格生成步骤.之前的网格生成工作有：（1） TMSmesh生成高斯曲面的三角网格; （2） TransforMesh删除自相交的三角网格; （3） ISO2Mesh提高表面网格质量3个步骤.而基于PHG的自适应加密模块可以在逐次调整网格的同时保持动态负载平衡,高效地得到计算网格用于近似求解非线性Poisson-Boltzmann方程.计算了小球模型和AChE系统,分别从误差指示子下降阶和溶剂化能收敛的角度验证了方法的有效性,并且还将网格生成算法成功地应用于gA离子通道.     

散乱点集Delaunay三角剖分的分布并行算法

为了加快大数据集Ｄｅｌａｕｎａｙ三角剖分的速度,提出了一种能对任意散乱点集进行Ｄｅｌａｕｎａｙ三角剖分的分布并行算法,算法具有容错性和自动负载平衡的能力,文中对其设计和实现方法进行了详细讨论,对算法的复杂性进行了分析,实验结果表明该算法的加速效果明显。     

网格结构上图象小波变换的并行算法

为提高大图象小波变换的速度,本文设计了一种网格结构上图象小波变换的并行算法,其特点是负载平衡,且通信只在少数几个处理机间进行,通信量小,因而算法效率高。