c - 为什么双链表中的指针追逐可以避免缓存抖动(自驱逐)？

Question

我试图理解 this paper关于缓存时序问题

在第 3.6 节中，作者解释了一种技术，该技术允许您填充连续的缓存区域并测量此填充过程的时间。他们提到:

“原始和探测步骤(即以固定步长扫描内存缓冲区)的天真实现由于现代 CPU 中实现的两个优化而产生了糟糕的结果:内存访问的重新排序和内存的自动预读“硬件预取器”。我们的攻击代码通过使用以下“指针追逐”技术绕过这两种中断。在初始化期间，攻击者的内存被组织成一个链表(可选，随机排列)；稍后，通过遍历此列表完成启动和探测(参见图 7)。为了最大限度地减少缓存抖动( self 驱逐)，我们使用双向链表并向前遍历它以进行启动，但向后遍历以进行探测。此外，为了避免“污染”自己的样本，探测代码将每个获得的样本存储到它刚刚完成测量的同一缓存集中。在某些平台上，可以通过使用写入而不是读取，或超过 W 次读取来改善时序差距。”

我对这一段有疑问:

链表如何避免硬件预取和重排序带来的时序变化？

Answer 1

当前实现的硬件预取器仅处理固定步幅访问模式，因此根据内存地址任意排序的访问不会被识别为可预取。这样的硬件预取器仍然可以检测和使用意外的步幅模式。例如，如果 address[X+5] = address[X] + N 和 address[x+7] = address[x+5] + 2N(请注意，地址不必由常量访问计数分隔)，预取器可能会预测 N 的步幅。这可能会适度减少明显的未命中延迟(某些预取是有效的)或引入一些缓存污染。

(如果检测到/预测的 N 很小，并且链表包含在相对于缓存大小适中的内存区域中(这样大部分步幅预取将指向即将使用的地址)，基于步幅预取可能会产生明显的积极影响。)

通过使用依赖于数据的访问(遍历链接需要访问数据)，可以防止访问重新排序。在前一个节点的下一个指针可用之前，硬件无法加载下一个节点。

已经有支持预取此类模式甚至通用相关性的学术建议(例如，参见 this Google Scholar search for Markov prefetching )，但(据我所知)尚未在商业硬件中实现。

作为旁注，通过以与启动访问相反的顺序遍历探测访问，对于常见的、面向 LRU 的替换，可以避免过多的未命中。