Level set函数快速步进重构的隐式分区并行

Implicit domain decomposition parallelization for the reconstruction of the level set function by the fast marching method

为进一步提高共享内存架构下level set函数重构并行效率,本文提出一种隐式分区并行重构方法,该方法无需提前进行区域分解,只需预先分割交界面,便可实现快速步进并行重构,且区域分解也同步进行。根据圆球、Zalesak球和哑铃等值面快速步进并行重构结果表明:隐式分区算法的计算耗时小于显式分区算法;相同线程数量下隐式并行算法带来的加速比与显式算法接近,8线程下隐式分区并行算法的加速比达到4;隐式分区算法中节点重演次数少于显式分区算法节点回滚次数。

To futher raise the shared-memory-based parallelization efficienty for reconstruction of level set function, an algorithm based on implicit domain decomposition is introduced. This method only separates the interface in advance rather than decomposing the domain beforehand and enables parallel fast marching reconstruction synchronized with domain decomposition. On the basis of the results of fast marching parallel reconstruction of isosurfaces, e.g., sphere, Zalesak′s sphere, and dumbbell, the runtime of the implicit domain decomposition method is shorter than that of the explicit partitioning method. Moreover, the speedup ratio of the implicit method is nearly similar to that of the explicit method, in which the speedup ratio of the implicit method can reach 4 under eight threads. Furthermore, the number of re-evolution operations of nodes in the implicit domain decomposition method is smaller than that of the rollback operations of nodes in the explicit method.