[Paper] 负载均衡并行节点生成用于无网格数值方法

Source: arXiv - 2602.16347v1

请提供您希望翻译的具体文本内容，我将按照要求保留源链接并进行简体中文翻译。

概述

本文提出了一种生成网格无关数值求解器节点分布的新方法——这些技术在不构建传统网格的情况下近似求解偏微分方程。通过为现代多核 CPU 重新设计经典的泊松盘采样算法，作者实现了高性能、负载均衡的节点创建，能够在多个线程上扩展，同时保持准确模拟所需的质量保证。

关键贡献

• 为 n 维域且节点密度可变的 并行 Poisson‑disc 采样。
• 基于 Hypertree 的工作分配，将域预先划分为平衡的叶单元，使线程能够在无需大量锁定的情况下获取工作。
• 仅使用叶层互斥锁实现 无冲突插入，显著降低同步开销。
• 全面的性能评估，与之前的并行尝试对比，展示在共享内存系统上接近线性的加速。
• 扩展讨论，面向分布式内存环境（如 MPI 集群）。

方法论

1. 基础算法 – 作者从已有的 Poisson‑disc 采样器开始，该采样器放置点，使得任意两点之间的距离不小于指定半径，半径可以在域内变化以编码自适应分辨率。
2. 空间超树构建 – 在采样开始之前，根据密度函数构建一个层次空间索引（类似 k‑d 树的超树）。每个叶节点大致对应填充该区域所需的工作量。
3. 线程工作分配 – 每个工作线程推进其自己的“前沿”候选点。当需要更多工作时，它会原子性地从超树中声明一个未处理的叶节点。由于叶节点与已声明的叶节点不相邻，线程永不竞争相同的空间区域。
4. 冲突处理 – 当线程提出一个新点时，它只需锁定该点所在的叶节点以检查已有邻居，避免对整棵树的全局锁。
5. 动态负载均衡 – 如果线程完成了当前叶节点的工作，它只需获取下一个可用的叶节点，即使密度函数高度非均匀，也能保持所有核心忙碌。

结果与发现

• 可扩展性：该算法在所测试的物理核心数范围内保持 >90 % 的并行效率。
• 质量保持：最小距离约束被精确满足，输出与顺序采样器完全一致。
• 锁争用：每次插入的互斥锁获取从朴素并行版本的 O(N) 降至总运行时间的 <0.5 %。
• 对比：相较于之前锁开销大的并行泊松盘实现，在相同核心数下新方法快 3–5 倍。

实际意义

• 更快的预处理 用于无网格求解器（例如平滑粒子流体动力学、径向基函数配点）——以前需要几分钟的节点生成现在可以在工作站上几秒钟完成。
• 实现即时自适应细化：由于超树反映了密度图，开发者可以在不重新构建整个索引的情况下动态调整分辨率。
• 简化集成：该算法仅依赖标准 C++ 线程原语和轻量级空间索引，便于直接嵌入现有仿真流水线。
• 通向分布式计算的路径：叶层工作划分自然对应域分解策略，为大规模云或高性能计算部署打开了大门。

限制与未来工作

• 仅共享内存：当前实现假设单一地址空间；将其扩展到多节点集群需要显式通信来处理叶子所有权和幽灵点。
• 内存开销：预构建超树在非常高维或高度异质的密度场中可能消耗大量 RAM。
• GPU 加速：作者指出，无锁叶子声明机制可以适配 GPU 工作队列，但这仍未被探索。
• 动态密度更新：虽然该方法支持静态密度函数，但处理运行时变化（例如移动边界）需要增量式超树更新。

总体而言，本文提供了一个稳健、对开发者友好的解决方案，针对网格无关模拟工作流中的瓶颈之一，并为将该方法扩展到单个多核机器之外的规模化提供了明确的路线图。

作者

• Jon Vehovar
• Miha Rot
• Matjaž Depolli
• Gregor Kosec

论文信息

• arXiv ID: 2602.16347v1
• Categories: cs.DC
• Published: 2026年2月18日
• PDF: 下载 PDF