标签存档: k-d树

并行粒子追踪中使用基于带有约束的k-d树分解的动态负载平衡方法 (Dynamic Load Balancing Based on Constrained K-D Tree Decomposition for Parallel Particle Tracing)

粒子追踪是流场可视化中的一种非常基础的技术。很多应用,从最基本的流线,迹线的计算,到源汇分析和FTLE(有限时间李雅普诺夫指数)的计算,都需要追踪大量的粒子。粒子追踪本身计算量大,加之流场数据的规模往往也比较大,我们需要对其并行化处理。但是,无论是数据并行(对数据进行静态划分和分配)还是任务并行(对粒子进行静态分配),由于很难确保每个进程分配到均等的工作负载,并行粒子追踪往往存在着严重的负载不均问题。究其本质,造成这一问题的原因是在追踪过程中粒子的分布随时间变化,并且很可能分布非常不均。以图1(a)为例,粒子在追踪过程中的分布变化非常大,甚至在一段时间后有些进程(或数据)没有粒子。

继续阅读 »