7

在模拟粒子相互作用时，我偶然发现了莫顿顺序（Z 顺序）（维基百科链接）的网格索引，它被认为可以提供有效的最近邻单元搜索。我读过的主要原因是内存中空间接近的单元的几乎顺序排序。

在第一次实现的过程中，我无法思考如何有效地实现最近邻居的算法，尤其是与基本的统一网格相比。

  1. 给定一个单元格 (x,y)，获取 8 个相邻单元格索引并计算相应的 z 索引是很简单的。尽管这提供了对元素的恒定访问时间，但必须计算或在预定义的表中查找 z-index（每个轴和 OR'ing 分开）。这怎么可能更有效率？是否真的，按 A[0] -> A 1 -> A[3] -> A[4] -> ...的顺序访问数组 A 中的元素比按 A[1023 的顺序访问更有效] -> A[12] -> A[456] -> A[56] -> ...？

  2. 我期望存在一种更简单的算法来以 z 顺序查找最近的邻居。类似的东西：找到邻居的第一个单元格，迭代。但这不可能是真的，因为这只能在 2^4 大小的块内很好地工作。但是有两个问题：当单元格不在边界上时，可以很容易地确定块的第一个单元格并遍历块中的单元格，但必须检查该单元格是否是最近邻。更糟糕的是，当单元格位于边界上时，必须考虑 2^5 个单元格。我在这里想念什么？是否有一种相对简单有效的算法可以满足我的需求？

第 1 点中的问题很容易测试，但我对所描述的访问模式生成的底层指令不是很熟悉，并且真的很想了解幕后发生的事情。

在此先感谢您的任何帮助、参考等...

编辑：
感谢您澄清第 1 点！因此，通过 Z 排序，相邻单元的缓存命中率平均增加，这很有趣。有没有办法分析缓存命中/未命中率？

关于第 2 点：我应该补充一点，我了解如何为 R^d 中的点云构建莫顿有序数组，其中索引 i = f(x1, x2, ..., xd) 是从逐位隔行扫描等获得的。我试图理解的是是否有比以下天真 ansatz 更好的方法来获取最近的邻居（这里在 d=2 中，“伪代码”）：

// Get the z-indices of cells adjacent to the cell containing (x, y) 
// Accessing the contents of the cells is irrelevant here
(x, y) \elem R^2    
point = (x, y)
zindex = f(x, y)     
(zx, zy) = f^(-1)(zindex)          // grid coordinates 
nc = [(zx - 1, zy - 1), (zx - 1, zy), (zx - 1, zy + 1),  // neighbor grid 
      (zx    , zy - 1),               (zx,     zy + 1),  // coordinates
      (zx + 1, zy - 1), (zx + 1, zy), (zx + 1, zy + 1)]

ni= [f(x[0], x[1]) for x in nc]    // neighbor indices
4

2 回答 2

10

在现代基于多级缓存的计算机系统中，空间局部性是优化数据元素访问时间的重要因素。

简而言之，这意味着如果您访问内存中的数据元素，那么访问内存中附近的另一个数据元素（地址接近第一个）可能比访问一个数据元素便宜几个数量级远处。

当顺序访问一维数据时，例如简单的图像处理或声音处理，或者迭代数据结构以相同的方式处理每个元素，然后在内存中排列数据元素以实现空间局部性 - 即因为您访问元素N+1 在访问元素 N 之后，这两个元素应该在内存中彼此相邻放置。

标准 c 数组（和许多其他数据结构）具有此属性。

Morton 排序的要点是支持二维而不是一维访问数据的方案。换句话说，在访问元素 (x,y) 之后，您可以继续访问 (x+1,y) 或 (x,y+1) 或类似的。

Morton 排序意味着 (x,y)、(x+1,y) 和 (x,y+1) 在内存中彼此靠近。在标准的 c 多维数组中，情况不一定如此。例如，在数组 myArray[10000][10000] 中，(x,y) 和 (x,y+1) 相距 10000 个元素 - 相距太远而无法利用空间局部性。

在 Morton 排序中，标准的 c 数组仍然可以用作数据的存储，但计算 (x,y) 的位置不再像 store[x+y*rowsize] 那样简单。

要使用 Morton 排序实现您的应用程序，您需要弄清楚如何将坐标 (x,y) 转换为商店中的地址。换句话说，您需要一个f(x,y)可用于访问商店的函数，如store[f(x,y)].

看起来你需要做更多的研究——按照维基百科页面的链接，特别是BIGMIN函数上的链接。

于 2010-11-23T20:18:38.000 回答
4

是的，按顺序访问数组元素确实更快。CPU 将内存从 RAM 分块加载到缓存中。如果按顺序访问，CPU 可以轻松预加载下一个块，而您不会注意到加载时间。如果你随机访问，它不能。这称为缓存一致性，这意味着访问您已经访问过的内存附近的内存更快。

在您的示例中，当加载 A[1]、A[2]、A[3] 和 A[4] 时，处理器可能会同时加载其中几个索引，这使得它们非常简单。此外，如果您继续尝试访问 A[5]，它可以在您对 A[1] 等操作时预加载该块，从而有效地减少加载时间。

但是，如果您加载 A[1023]，处理器必须加载该块。然后它必须加载 A[12]- 它尚未加载，因此必须加载一个新块。等等等等。但是，我不知道您的其余问题。

于 2010-11-23T19:45:15.097 回答