3

我有一个包含稀疏几何的非立方边界框的 3d 数组。

如果 (x,y,z) 是计算域的一部分，则数组 geometry[x][y][z] 包含值 0，否则为 1。

为了重新排序计算，我想使用希尔伯特曲线遍历这个空间。

上下文是优化内存绑定 GPU 程序中的全局内存访问。

我该如何实施？

更新：我只想遍历非空单元格，因为我只会将这些单元格（在数组中）与一个跟踪元素的 19 个相邻节点的邻接列表一起存储。

计算只是在两个数组之间复制：

dst[i] = src[adjacency_map[i]]

这是稀疏格子玻尔兹曼方法的传播阶段，其中物理解释是从相邻站点流式传输“流体粒子”。

adjacency_map 中的值越连续；我们希望得到的合并内存访问越多。

OpenCL 内核：

__kernel void propagation(__global double *dst, __global double *source,
                          __global const int *adjacency_map, const uint max_size)
{
    size_t l = get_global_id(0);

    if( l > max_size ) 
        return;

    dst[l] = src[adjacency_map[l]];
}
4

2 回答 2

3

希尔伯特曲线将是一项艰巨的任务。似乎很难找到一个允许随机访问曲线上点的索引的公式。

然而，莫顿排序是合理的，并且具有一些与空间填充曲线相同的良好属性。还有一个随机访问过程可以找到 N 维点的莫顿数。

您可能会考虑一个两步过程：

  1. 对您的数据应用流压缩步骤以选择您希望处理的卷元素

  2. 使用它们的Morton 索引作为排序键对这些压缩数据进行排序。

您可以将推力用于流压缩和键值排序。

这应该会产生一个按顺序排列的卷元素列表，以促进连续性。也就是说，重组数据的开销可能会主导原始不规则访问模式的成本。

于 2011-08-02T18:33:52.640 回答
1

这听起来很不可能。

您是否已经排除了 kdtree 或八叉树？

数值配方中对kdtree（第21.2章）和octree（第21.8章）的描述很好理解： http ://apps.nrbook.com/rollover/index.html

于 2011-07-31T00:10:29.193 回答