0

我有一个我正在尝试解决的问题，它涉及一个 7 点计算模板。对于那些可能不知道的人，这将是一个 3D 网格，这 7 个点是第 n 个点，相邻点在 x、y 和 z 方向上各一个点，正负（或东边的邻居） /west/north/south 和上/下）。

所以这 6 个点加上我正在处理的 1 个附加点用于计算，并且都存储在一个一维数组中。

假设 nx 是立方体的宽度，ny 是高度。那么，在内存中，当我访问数组 All_Points 中的一个点时，例如 All_points[n]，那么要获取它在每个方向上的邻居，我也想访问 All_points[n-1]、All_points[n+1] 、All_points[n-nx]、All_points[n+nx]、All_points[n-nx ny] 和 All_points[n+nx ny]。

所以我的问题是我得到了大量的缓存未命中。我似乎找不到任何代码示例来演示如何避免这个问题。理想情况下，我想将此数组拆分回它的 x、y 和 z 坐标，例如 All_x_points[] 但后来我在尝试保持更新时遇到了问题，因为 All_points[n] 发生了变化，当它发生变化时，这意味着对于其他一些 All_points[n'] 我的 x、y 或 z 值将需要用它来更新。

以前有人见过这种事情吗？

4

2 回答 2

1

使用 7 点模板的访问模式是什么？如果您遇到缓存一致性问题，这是第一个要问的问题——如果您的中心 (x,y,z) 坐标的访问模式是完全随机的，那么您可能不走运。

如果您对访问模式有一定的控制权，则可以尝试将其调整为对缓存更友好。如果不是，那么您应该考虑期望什么样的访问模式；您也许可以安排数据，使这种访问模式更加良性。这两者的结合有时会非常有效。

有一种特殊的数据排列通常对这种事情有用：位交错阵列布局。假设（为简单起见）每个坐标的大小是 2 的幂。然后，“正常”布局将通过连接每个坐标的位来构建索引。但是，位交错布局将以循环方式为每个维度分配位：

3D index coords: (xxxx, yyyy, zzzz)

normal index:    data[zzzzyyyyxxxx]  (x-coord has least-significant bits, then y)
bit-interleaved: data[zyxzyxzyxzyx]  (lsb are now relatively local)

实际上，成本很小：您需要使用查找表来查找偏移量，而不是将坐标乘以它们的步长值。但是由于您可能只需要非常短的查找表（尤其是对于 3D 数组！），它们都应该很好地适合缓存。

3D coords:  (x,y,z)

normal index:      data[x + y*ystep + z*zstep]  where:
  ystep= xsize (possibly aligned-up, if not a power of 2?)
  zsetp= ysize * ystep

bit-interleaved:   data[xtab[x] + ytab[y] + ztab[z]]  where:
  xtab={  0,  1,  8,  9, 64, 65, 72, 73,512...}   (x has bits 0,3,6,9...)
  ytab={  0,  2, 16, 18,128,130,144,146,1024...}  (y has bits 1,4,7,10...)
  ztab={  0,  4, 32, 36,256,260,288,292,2048...}  (y has bits 2,5,8,11...)

最终，这是否有用完全取决于您算法的要求。但是，再次请注意，如果您的算法对缓存的要求太高，您可能需要考虑调整算法，而不仅仅是布局。

于 2009-12-12T13:05:49.120 回答
0

7分？六个定义空间坐标，一个定义长度？这些是……星门坐标吗？

为什么不将结构数组 (AOS) 转换为数组结构 (SOA)？

int point = points_all[i]; // the point you want
Vec2 points_x[point]; // x and y are the neighbours left and right
Vec2 points_y[point]; // x and y are the neighbours up and down
Vec2 points_z[point]; // x and y are the neighbours front and back
于 2009-12-10T19:28:41.727 回答