1

作为课堂项目的一部分，我正在寻找提高 CPU 架构中寻路算法性能的方法。该算法是用 C++ 实现的。基本操作是读取 x,y 坐标并对它们执行一些操作。

我现在的想法是将 x 和 y 坐标分别存储在两个缓存组中（设置关联）。为一个位置输入的两个坐标应存储在不同的存储库中，以便能够并行读取它们，并对 x 和 y 坐标进行单独操作并存储组合结果。通过使用矢量运算，该过程可以进一步加快，同时读取多达 4 个 x 坐标和 4 个 y 坐标。

例如，为了计算到目标节点的欧几里得距离，必须在每个位置读取 x 和 y 坐标并从目标坐标中减去以找出距离。

我想知道是否有一种有效的方法（缓存放置策略）将 x 和 y 坐标保持在不同的缓存行/块中以利用并行性。是否有任何坐标操作/编码可以用来实现它？

PS：我不是在寻找软件优化，而是在寻找修改后的缓存设计（理论上）来加速算法。

参考：这篇博文提到“如果 L1 缓存访问来自不同 bank 的缓存行，则它们可以并行处理两个访问，如果它们属于同一个 bank，则可以串行处理。”

4

1 回答 1

0

保存在如下结构中的坐标：

struct {
  int x;
  int y;
} coordinate;

将适合单个缓存行。事实上，在具有 32 字节高速缓存行的典型 MIPS 处理器上，8 个实例coordinate将适合一个高速缓存行。CPU 将从数据缓存中的单个存储体或路径一次读取整行，并且所有 32 字节或所有 4 个坐标将从那时起在 32 字节填充/存储缓冲区(FSB) 中以零延迟到流水线可用. 具有高速缓存的 MIPS 处理器通常具有多个 FSB。

具有分块或组关联缓存的 MIPS 处理器通常使用LRU算法来选择在缓存未命中时将新数据放入哪个库/路径。通常不可能确保来自某个位置的数据始终以特定方式放置在缓存中。

所有这一切都是说，您将 x 和 y 坐标存储在单独的缓存组中的方案不会比幼稚方案提高性能，因为 FSB 对幼稚方案的积极影响以及由于方式选择算法的不可预测的影响缓存。

于 2012-12-08T02:09:55.400 回答