logo标签列表

稀疏几何的3D Hilbert 曲线

optimizationcudaopenclhilbert-curve
3
我有一个包含稀疏几何体非立方边界框的三维数组。
如果(x,y,z)是计算域的一部分，则数组geometry[x][y][z]包含值0，否则为1。
为了重新排序计算，我想使用希尔伯特曲线遍历这个空间。
上下文是优化内存受限GPU程序中的全局内存访问。
我该如何实现？
更新： 我只想遍历非空单元格，因为我将仅与邻接列表(其中记录元素的19个相邻节点)一起将其存储在数组中。
计算只是在两个数组之间进行复制：
dst[i] = src[adjacency_map[i]]

这是一种稀疏Lattice Boltzmann方法的传播阶段，物理上解释为从相邻位置流动“流体粒子”。

邻接映射中数值越连续，我们就能获得更多合并内存访问的希望。

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]];
}
你想遍历整个体积的所有单元格，还是只遍历非空单元格？你希望对这些单元格应用什么计算？ - Jared Hoberock
我想遍历只有非空单元格，因为它们将稍后存储在数组中。我已经更新了原始问题，并提供了更多信息。 - kyrre
2个回答
3

构造一个希尔伯特曲线可能会很困难。似乎很难找到一种公式，使得可以随机访问曲线上点的索引。

然而，Morton ordering 是可行的，并且具有类似的良好性质，因为它也是一条填充空间的曲线。还有一种随机访问过程可以找到 N 维点的 Morton number。

您可以考虑以下两步处理：

  1. 对数据进行一步流压缩，选择要处理的容积元素

  2. 使用其Morton indices作为排序关键字，对这些压缩数据进行排序。

您可以使用thrust同时进行流压缩和键-值排序。

这应该会生成一个按顺序排列的容积元素列表，从而提高连续性。尽管如此，重新组织数据的开销可能会占据原始不规则访问模式的成本。

1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接