optimization - 稀疏几何的 3d 希尔伯特曲线

Question

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

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

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

上下文是优化内存绑定(bind) 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]];
}

Answer 1

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

A Morton ordering然而，它是合理的，并且具有一些与空间填充曲线相同的优良特性。还有一个随机访问程序，用于查找 N 维点的莫顿数。

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

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

2. 使用他们的 Morton indices as the sorting key 对压缩后的数据进行排序.

你可以使用 thrust用于流压缩和键值排序。

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