稀疏几何的三维希尔伯特曲线

Question

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

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

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

上下文正在优化内存受限GPU程序中的全局内存访问。

我如何实现这个?

:我只想遍历非空单元格，因为我只会将它们(在数组中)与邻接表存储在一起，邻接表跟踪元素的19个相邻节点。

计算只是在两个数组之间进行复制:

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

这是稀疏晶格玻尔兹曼方法的传播阶段，其物理解释是从邻近位置流动的"流体粒子"。

邻接ency_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

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

然而，Morton排序是合理的，并且具有一些相同的良好性质，因为它也是一个空间填充曲线。还有一个随机存取程序用于查找n维点的莫顿数。

你可以考虑一个两步的过程:

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

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

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

这将产生一个卷元素的列表，其顺序促进了相邻性。也就是说，重新组织数据的开销可能会超过原始不规则访问模式的成本。

Answer 2

听起来很不可能。

你已经排除了三叉树或八叉树吗?

数值配方中kdtree(第21.2章)和octree(第21.8章)的描述是很容易理解的:http://apps.nrbook.com/rollover/index.html