并行平面Delaunay网格生成  

Parallel planar Delaunay mesh generation

作　　者：梁义[1] 陈建军[1] 陈立岗[1] 郑耀[1] 

机构地区：[1]浙江大学工程与科学计算研究中心

出　　处：《浙江大学学报（工学版）》2008年第4期558-564,共7页Journal of Zhejiang University：Engineering Science

基　　金：浙江省自然科学基金资助项目(Y607429);国家杰出青年基金资助项目(60225009);国家自然科学基金青年基金资助项目(10702064)

摘　　要：基于一个通用的并行平面网格生成框架,实现了高效、可扩展的并行平面Delaunay网格生成器PDMG-2D,它能利用中等规模并行资源在几分钟内生成包含上亿三角形单元的平面网格.针对传统并行网格生成方法在将子域映射到多个处理器上进行处理的过程中不考虑子域间邻接关系,从而导致生成的各处理器网格之间共享节点数过多,通信量巨大,而必须进行大规模网格重划分的问题,根据子域邻接关系定义了子域图(SDG),提出了子域负载预估和动态图划分方法,在并行网格生成的同时得到了高划分质量的分布式网格,有效降低了网格重划分所引起的性能代价.实验证明,PDMG-2D具备很好的可扩展性、有效性和稳定性,与传统方法相比,在大幅减少时间消耗的同时,生成了高划分质量的分布式网格.A parallel planar Delaunay mesh generator, PDMG-2D, was built based on a general and modularized parallel framework, which could generate hundreds of millions of elements in minutes with medium sized parallel resources. Traditionally, a mesh repartitioning procedure is required to balance the loads and minimize the communications of the succeeding parallel solution process, in which a large number of elements are migrated among processors, and intensive I/O operations are involved. In order to overcome the bottleneck, a subdomain graph （SDG） was defined to represent the subdomain connections, which helps to generate distributed meshes with high partitioning quality simultaneously with parallel mesh generation. Experimental results show that PDMG-2D is scalable, efficient and stable, and it can generate distributed meshes with high partitioning quality at much lower time cost compared to traditional approaches.

关 键 词：网格生成 并行算法 DELAUNAY三角化 子域图 网格重划分 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]