RnR: A Software-Assisted Record-and-Replay Hardware Prefetcher
RnR: A Software-Assisted Record-and-Replay Hardware Prefetcher
复制标题
DOI：
10.1109/micro50266.2020.00057
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Chao Zhang;Yuan Zeng;J. Shalf;Xiaochen Guo
中科院分区：
文献类型：
--
作者：
Chao Zhang;Yuan Zeng;J. Shalf;Xiaochen Guo
具有不规则内存访问模式的应用程序不能像具有良好局部性的应用程序那样很好地从内存层次结构中受益。相对较高的未命中率和较长的存储器访问延迟会导致处理器停止并降低系统性能。预取可以通过预测哪些内存地址将在不久的将来被访问并提前发出内存请求来帮助隐藏未命中惩罚。然而，软件预取器增加了指令开销，而硬件预取器不能有效地预测具有高精度的不规则存储器访问序列。幸运的是，在许多重要的非常规应用中（例如，迭代求解器、图形算法和稀疏矩阵-向量乘法），存储器访问序列在多次迭代或编程阶段上重复。当模式很长时，传统的时空预取器不能达到很高的预取精度，但这些重复的模式可以被程序员识别。在这项工作中，我们提出了一个软件辅助的硬件预取器，专注于重复不规则的存储器访问模式的数据结构，不能受益于传统的硬件预取器。其关键思想是提供一个编程接口，在第一次出现内存访问模式时记录缓存未命中序列，并通过在随后的重复中重播模式来预取。所提出的记录和重放（RnR）预取器提供轻量级软件接口，使得程序员可以在应用代码中指定：1）哪些数据结构具有不规则的存储器访问，2）何时开始记录，以及3）何时开始重放（预取）。这项工作评估了三个不规则的工作量与不同的投入。对于评估的工作负载和输入，所提出的RnR预取器可以实现平均2.16倍的加速比的图形应用程序和2.91倍的加速比的迭代求解器与稀疏矩阵向量乘法内核。通过利用程序员的知识，所提出的RnR预取器可以实现超过95%的预取准确率和未命中覆盖率。
Applications with irregular memory access patterns do not benefit well from the memory hierarchy as applications that have good locality do. Relatively high miss ratio and long memory access latency can cause the processor to stall and degrade system performance. Prefetching can help to hide the miss penalty by predicting which memory addresses will be accessed in the near future and issuing memory requests ahead of the time. However, software prefetchers add instruction overhead, whereas hardware prefetchers cannot efficiently predict irregular memory access sequences with high accuracy. Fortunately, in many important irregular applications (e.g., iterative solvers, graph algorithms, and sparse matrix-vector multiplication), memory access sequences repeat over multiple iterations or program phases. When the patterns are long, a conventional spatial-temporal prefetcher can not achieve high prefetching accuracy, but these repeating patterns can be identified by programmers.In this work, we propose a software-assisted hardware prefetcher that focuses on repeating irregular memory access patterns for data structures that cannot benefit from conventional hardware prefetchers. The key idea is to provide a programming interface to record cache miss sequence on the first appearance of a memory access pattern and prefetch through replaying the pattern on the following repeats. The proposed Record-and-Replay (RnR) prefetcher provides a lightweight software interface so that the programmers can specify in the application code: 1) which data structures have irregular memory accesses, 2) when to start the recording, and 3) when to start the replay (prefetching). This work evaluated three irregular workloads with different inputs. For the evaluated workloads and inputs, the proposed RnR prefetcher can achieve on average 2.16× speedup for graph applications and 2.91× speedup for an iterative solver with a sparse matrix-vector multiplication kernel. By leveraging the knowledge from the programmers, the proposed RnR prefetcher can achieve over 95% prefetching accuracy and miss coverage.