我正在开发一个利用卡上所有可用 RAM 的 CUDA 应用程序，并试图找出减少缓存未命中的不同方法。

问题域由一个大的 2 维或 3 维网格组成，具体取决于要解决的问题的类型。（对于那些感兴趣的人，它是一个 FDTD 模拟器）。每个元素依赖于“平行”数组（即另一个几乎相同维度的数组）中的两个或四个元素，因此内核必须访问三个或六个不同的数组。

问题

*希望这不是“过于本地化”。随意编辑问题

三个数组之间的关系可以可视化为（为平庸的ASCII艺术道歉）

由线连接的项目是耦合的。从上面可以看出，A[]取决于B[]和C[]，而B[]仅取决于A[]， 和 一样C[]。所有的A[]都在第一个内核中更新，所有的B[]和C[]都在第二遍中更新。

如果我将这些数组声明为简单的 2D 数组，我最终会进行跨步内存访问。对于非常大的域大小（上面网格中的 3x3 +- 1），这会导致占用率和性能不足。

所以，我考虑过在 Z 阶曲线中重新排列数组布局：

此外，将它们交错到一个数组中是相当简单的，这应该会提高获取性能，因为（取决于交错顺序）给定单元更新所需的至少一半元素将彼此接近。但是，我不清楚 GPU 在访问多个数组时是否使用多个数据指针。如果是这样，这种想象中的好处实际上可能是一个障碍。

问题

我读过 NVidia 在使用纹理内存或cudaArray. 如果不是这种情况，我是否应该期望在跨越大跨度时增加延迟（当 Z 曲线在高细分级别从右上角到左下角时）以消除较小网格中局部性的好处？

3. 将网格划分为可以放入共享内存的较小块肯定会有所帮助，而 Z 顺序使这变得相当简单。我应该有一个单独的内核通道来更新块之间的边界吗？与我预期的节省相比，启动另一个内核的开销会很大吗？

4. 使用 2D 与 1D 阵列有什么真正的好处吗？我希望内存是线性的，但不确定 CUDA 文献中经常使用的 2D 内存布局隐喻是否有任何实际意义。

哇 - 很长的问题。感谢您阅读和回答任何/所有这些。

我想知道我们是否可以用空间填充曲线解决最短路径，还是有更好的解决方案？与精确求解器相比，近似值有多好？该图不需要满足三角不等式。

对于我当前的输入数据，即 3D 点，我使用Morton 代码来提高访问点列表时的缓存一致性。

我还有一些其他数据是 6D 和 7D。对于这样的维度，莫顿代码仍然是一种很好的技术吗？或者有没有其他的技术？其他空间填充曲线技术在 3D 本身中的计算比 Morton 更复杂，我想知道人们是否使用 6D/7D 或更高的替代技术。

Hacker's Delight 2nd Edition 中的算法

移植到python

一个简单的希尔伯特曲线类。

所以我想要的是每次调用 next() 时都会给出 (x,y) 的东西。我自己尝试过这样做，但无法使其正常工作，因此将不胜感激。我是否必须重写它才能使用生成器？ 资源

我读过诸如Peano曲线之类的空间填充曲线对于在线性地址空间中维护缓存友好的数据结构很有用，因为它们维护了物理空间局部性。

但是，我不确定如何实际使用它们。这些曲线中是否有任何公式可以将线性地址快速转换为 (x,y) 坐标，反之亦然？否则，当查找某对坐标时，如何确定在内存中查找的位置？一个例子会很有帮助。

Space filling curves are a way to fill a grid with line that preserves locality - that is, two close points at the line are also 2 close points on space.

Is there any fast (O(1)) algorithm to map between an N-dimensional coordinate and the index on the corresponding N-dimensional space-filling curve?

我有点困惑，因为我测试了几种算法来计算 z 索引，对于 (8, 8, 8) 我得到 3584，对于 (7, 7, 7) 我得到 511，这是正确的。问题是 8*8*8 = 512，但 z-index 是 3584。这意味着如果我使用一维数组按 z-index 存储东西，我不会使用更多空间并且会有空阵列中的插槽？类似地，7*7*7 = 343，小于 511。如果您在维基百科页面上查看 z-indexing/Morton 编码，您会发现一个二维示例，它是 8*8，x 和 y 的索引从 0到 7。但是，最大的 z-index 是 111111，即 63，从 0 开始编号时正好是第 64 个元素，因此它不会使用超过存储 64 个元素所需的空间。这里有什么问题吗？

谢谢

我正在使用Z Order Curve写一个UB Tree来取乐。它目前能够以任意数量的维度存储点，当被查询时，它会在两个 Z 索引之间执行简单的搜索，过滤并丢弃任何误报。我想实现并尽量减少它遍历的误报的数量，但我似乎找不到任何关于如何以不限制我的树存储二维数据的方式实现这些的信息。例如，本白皮书和这篇博客文章都使用与使用 2D 值密切相关的术语来描述它们的实现。BIGMINLITMAX

是否有一种与维度无关的方法来实现此功能？

我有一个基于海龟图形的算法，用于生成二维空间填充希尔伯特曲线。它是递归的，如下所示：

Wa 想画一条有序的曲线n，在方向x（哪里x ∈ {L, R}），让y是与 的相反方向x。我们这样做：

• 转向y
• 画一条有序n-1、方向的希尔伯特曲线y
• 向前迈出一步
• 转向x
• 画一条有序n-1、方向的希尔伯特曲线x
• 向前迈出一步
• 画一条有序n-1、方向的希尔伯特曲线x
• 转向x
• 向前迈出一步
• 画一条有序n-1、方向的希尔伯特曲线y

我理解这一点，并能够实施一个可行的解决方案。但是，我现在正试图将其“升级”为 3D，这就是我基本上碰壁的地方；在 3D 中，当我们到达一个顶点时，我们可以转向不是两个，而是四个方向（直行或后退显然不是一种选择，因此是四个而不是六个）。直觉上，我认为我应该存储海龟“行走”的平面及其在世界中的大致方向，由enum具有六个值的 an 表示：

• 向上
• 下
• 剩下
• 正确的
• 在（从相机的角度来看，它进入了世界“内部”）
• 外（同上，外）

海龟，就像在 2D 中一样，具有包含上述信息的状态，当它到达顶点时（可以被认为是“交叉点”）必须根据该状态决定下一步要去哪里。而在二维中它相当简单，在三个方面，我很难过。

1. 我的方法正确吗？（即，这是我应该存储在海龟状态中的内容吗？）
2. 如果是，我如何使用这些信息来决定下一步去哪里？

因为填充希尔伯特曲线的 3D 空间有许多变体，所以我应该指定这是我用作参考并帮助我想象的：

我知道已经问过一个类似的问题，但是接受的答案链接到一个网站，这个问题是使用不同的方法解决的（即，不是海龟图形）。

我已经用 Python（来自 Matlab 的）编写了 Hilbert-Peano 空间填充曲线的实现来展平我的 2D 图像：

但是，经典的 Hilbert-Peano 曲线仅适用于形状为 2 的幂的多维阵列（例如：在二维阵列（图像）的情况下为 256*256 或 512*512）。

有人知道如何将其扩展到任意大小的数组吗？