计算科学 - 用于并行化有限元模拟的简单快速图形聚类 - 吾爱随笔录

计算科学并行计算图论非结构化网格分区

2021-12-01 17:38:47

我正在学习使用 OpenCL 来优化我的一些模拟。我意识到我需要某种图形聚类或图形分区来有效地利用本地内存来处理无序网格。

示例：我使用 4 键顶点的规则网格实现了弹性布料模拟，我可以手动将其分离为本地化批次。现在我想转到一般不规则网格，其中每个节点可以有任意数量的边。

通过快速搜索，我找到了一些资源，但我不确定它是否能很好地满足我的需求（我在离散数学和图论领域没有经验）。

我想要的是：

将网格分割成批次，这样
1. 所有批次都具有大致相同的大小（节点和边的数量），例如 16 个节点，每个节点对应于local_size我的 OpenCL kernell
2. 不同批次之间的边数最少 - 最大限度地减少每个工作组加载的节点之间的重叠
简洁且易于由我自己实现的算法 - 对我来说，这只是次要问题而不是主要话题。即使它是开源的，我也不会对某些 3rd 方软件或库产生依赖。
- 它不必导致最优解，它可以是随机的和粗略的启发式的
- 它应该很快 - $O(n)$ 带有小的前置因子

1个回答

对于一个简单的（但不是最佳的，见下文）网格划分算法，您可以执行以下操作：

1) sort all the cells of the mesh using Hilbert sort
2) partition the sorted list of cells into chunks of the desired size

空间希尔伯特排序在我的 GEOGRAM 库 [1,2] 和 CGAL [3] 中实现。std::nth_element()使用STL的功能，实现起来相当容易。另请参阅 [3] 以获得对空间排序的一个很好的解释。

该解决方案不是最佳的，因为它完全忽略了块之间的连接，因此不会最小化进程之间的通信，但我认为这是一个有趣的替代方案，因为它非常快（但它是 O(n log(n) ) 而不是 O(n) 所要求的）。它可以在几行代码中实现，而 METIS 使用一定数量的内存并且处理时间有时会抵消它在通信上的增益。

为了完成这个答案，我还提到了 SCOTCH [4]，它具有有趣的替代图形分区算法（但如果您不想像问题中所说的那样具有外部依赖关系，它对您来说并不完全令人满意）。

其它你可能感兴趣的问题