张衍涛. 物质点并行算法研究. 清华大学硕士学位论文，2011.6

物质点法采用物质点与背景网格双重离散。与拉格朗日有限元法相比,它 避免了因网格畸变而产生的数值困难;与欧拉法相比,它避免了因非线性对流 项而产生的数值困难,且容易处理自由表面和材料界面,因此适合于求解流固 耦合,以及涉及大变形的问题。然而,普通电脑的计算能力限制了可以研究的 问题的规模。模拟大规模问题时,离散常常不够密致,模拟结果也常常失真。 为了扩大计算规模,有必要研究物质点法的并行算法。同时,为了避免浪费计 算资源,要求并行算法具有良好的负载平衡。
与所有的网格质点类方法如 PIC 方法相似,物质点法中的质点在网格内是 自由移动的,相对欧拉格式和有限元格式而言更难以实现负载平衡。本文主要 针对常用的两种并行计算模型 MPI 和 OpenMP,研究了物质点并行算法中的一 些问题,并讨论了如何进一步改进负载平衡。
MPI 模型使用一个丰富的函数库实现进程间消息传递。它功能强大、灵活, 但实现 MPI 并行的工作量比较大。本文基于静态分区思想利用 MPI 模型将三维 物质点法软件 MPM3D(计算机软件著作权登记号 2009SRBJ4761)并行化,编 制了并行物质点程序 MPM3D_MPI,并验证了其正确性与稳定性,极大地提高 了物质点程序的计算规模。OpenMP 是基于线程的并行模型,主要通过指导性语 句实现并行。使用 OpenMP 时,在背景网格更新阶段我们提出了网格交替更新 法以避免数据竞争。该方法适用范围广、实施简单、易于实现负载平衡且不浪 费内存。在此基础上本文利用 OpenMP 将 MPM3D 并行化,编制了 MPM3D_OMP。算例表明 MPM3D_OMP 具有良好的并行效率。

Material Point Method discretizes material domains by both regular grid and particles. Compared with Lagrangian FEM, MPM avoided numerical difficulty induced by grid distortion which is common in FEM. And compared with Eulerian method, there is no numerical difficulty caused by nonlinear convective term, and it’s easy for MPM to handle free surface and the material interface. As a result of these advantages, MPM is widely used in coupled fluid-solid problem and other dynamic problems that involve large deformation. However, the computing capablity of common PCs greatly restrains the scale of problem that can be solved. When solving large scale problems, the bodies are often discretized with insufficient particles and the results will definitely be very inaccurate. To enlarge the problem scale, parallelization of MPM is required. Meanwhile, load balance strategy also needs to be raised to avoid wasting computing resources.
Similar to all methods in which bodies are discretized by both grid and particles, such as PIC method, the particles of MPM are free to move anywhere within the grid. This feature will cause great difficulty in achieving load balance. This article addressed some issues in the parallel algorithm of MPM using MPI or OpenMP and discussed how to furthur improve load balance.
MPI provides a lot of funtions to pass messages between processes. It is powerful, flexible but requires a lot of work to implement. In this article, the 3D explicit material point method code, MPM3D, is parallelized employing static decomposition strategy and is named MPM3D_MPI. The article also verifies the correctness and stability of MPM3D_MPI. The parallel program greatly increases the scale of problems that can be solved.
OpenMP is a parallel model based on threads, which mainly uses directives to realize parallelism. We proposed an alternated grid updating method to avoid data races when OpenMP is used in the stage of grid updating. This method can be widely used, easy to implement, easy to realize load balance and wastes no memory. Based on this method, MPM3D_OMP is developed. Some examples show that the efficiency of MPM3D_OMP is very good.