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 回答