github

介绍

Pythia formulates hardware prefetching as a reinforcement learning task. For every demand request, Pythia observes multiple different types of program context information to take a prefetch decision. For every prefetch decision, Pythia receives a numerical reward that evaluates prefetch quality under the current memory bandwidth utilization. Pythia uses this reward to reinforce the correlation between program context information and prefetch decision to generate highly accurate, timely, and system-aware prefetch requests in the future.

运行

构建预取器

cd $PYTHIA_HOME
# ./build_champsim.sh <l1_pref> <l2_pref> <llc_pref> <ncores>
./build_champsim.sh multi multi no 1

source setvars.sh

目录：scripts、traces、experiments
工具：intel pinplay

实验

构造实验: scripts/create_jobfile.pl
开始实验: jobfile.sh

The top-level files for Pythia are prefetchers/scooby.cc and inc/scooby.h. These two files declare and define the high-level functions for Pythia (e.g., invoke_prefetcher, register_fill, etc.).
The released version of Pythia has two types of RL engine defined: basic and featurewise. They differ only in terms of the QVStore organization (please refer to our paper to know more about QVStore). The QVStore for basic version is simply defined as a two-dimensional table, whereas the featurewise version defines it as a hierarchichal organization of multiple small tables. The implementation of respective engines can be found in src/ and inc/ directories.
inc/feature_knowledge.h and src/feature_knowldege.cc define how to compute each program feature from the raw attributes of a deamand request. If you want to define your own feature, extend the enum FeatureType in inc/feature_knowledge.h and define its corresponding process function.
inc/util.h and src/util.cc contain all hashing functions used in our evaluation. Play around with them, as a better hash function can also provide performance benefits.

论文阅读

过去研究不足

• 单一的程序上下文信息（PC、Cache line Address等）
• 忽视了预取器的系统消耗或事后考虑（带宽消耗、Cache污染等）
• 不能适应不同的工作负载和运行环境

方案
将预取器作为强化学习代理。对于每个请求，Pytia都会观察多种不同类型的程序上下文信息，以做出预取决策。对于每个预取决策，Pythia都会收到一个数字奖励，该奖励将评估当前内存带宽使用情况下的预取质量。Pytia利用这种奖励来加强程序上下文信息和预取决策之间的相关性，以便在未来生成高度准确、及时且系统感知的预取请求。

目标：不同程序上下文信息 + 系统反馈 + 配置

Our goal in this work is to design a single prefetching frame-work that (1) can holistically learn to prefetch using both multiple different types of program features and system-level feedback information that is inherent to the design, and (2) can be easily customized in silicon via simple configuration registers to exploit different types of program features and/or to change the objective of the prefetcher (e.g., increasing/decreasing coverage, accuracy, ortimeliness) without any changes to the underlying hardware.

预取根据：program counter (PC), cacheline address (Address), page offset of a cacheline (Offset), or a simple combination of such features using simple operations like concatenation (+)
PC + Address, PC + Offset

强化学习

将Pythia定义为一个RL-agent，它通过与处理器和内存子系统交互来自主学习预取。对于每一个新的需求请求，Pythia都会提取一组程序特性。它将特征集作为状态信息，根据之前的经验进行预取操作。对于每一个预取动作(包括不预取)，在给定各种系统级反馈信息的情况下，Pythia都会收到一个数值奖励，评估预取动作的准确性和及时性。

首先，使用RL框架，Pythia可以整体地学习使用其设计固有的多个程序特性和系统级反馈信息进行预取。其次，通过简单的配置寄存器，可以很容易地在硅中定制Pythia，以利用不同类型的程序特性和/或改变预取器的目标。这给了Pythia一个独特的好处，可以为各种工作负载和更改系统配置提供更高的性能改进，而不需要对底层硬件进行任何更改。

Cache介绍

cache分成多个组set，每个组分成多个行way，linesize是cache的基本单位，从主存向cache迁移数据都是按照linesize为单位替换的。比如linesize为32Byte，那么迁移必须一次迁移32Byte到cache。 这个linesize比较容易理解，想想我们前面书的例子，我们从书架往书桌搬书必须以书为单位，肯定不能把书撕了以页为单位。书就是linesize。当然了现实生活中每本书页数不同，但是同个cache的linesize总是相同的。
所谓8路组相连（ 8-way set associative）的含义是指，每个组里面有8个行。

描述一个cache需要以下参数 ：
1、cache分级，L1 cache， L2 cache， L3 cache，级别越低，离cpu越近
2、cache的容量
3 、cache的linesize
4 、cache 每组的行个数

Cache基础知识

预取器介绍

根据程序上下文信息推测数据访问模式，在访问之前进行预取
程序上下文信息：PC、Cache line address、Page Offset 以及之间的组合如：PC+offset

预取评估

• 覆盖率：原始缓存缺失中被预取的比例，由于预取，缓存缺失变为缓存命中或部分缓存命中。
• 准确性：预取数据中有效的比例，也就是导致缓存命中的比例。
• 及时性：预取的数据要是过早到达，还没使用就有可能被踢出去；过晚到达则不能完全隐藏延迟。

一个理想的预取机制应该是高覆盖率，最大程度消除缓存缺失；高准确率，不会增加过多的存储带宽消耗；及时性，完全隐藏缓存缺失时延。我们可以看出来，这三个指标在某种程度上是对立的。如果采取激进的预取，可以提高覆盖率，但是准确率就会下降；如果采取保守的预取，只对准确预测的数据进行预期，可以提高准确率，但是覆盖率会降低。对于及时性，如果预取启动过早，可能在处理器使用该数据前就被替换出缓存或者预取缓冲区，“污染”了高速缓存；如果启动过晚，可能就无法完全隐藏缓存缺失时延。

分类

• 硬件预取与软件预取
• 指令预取与数据预取

硬件预取分类

步长预取（stride prefetching）检测并预取连续访问之间相隔s个缓存数据块的数据，其中s即是步长的大小。硬件实现需要使用访问预测表，记录访问的地址，步长以及访存指令的pc值。流预取（stream prefetching）对流访问特征进行预取，流访问特征是指一段时间内程序访问的cache行地址呈现的规律，这种访问规律在科学计算和工程应用中广泛存在。硬件实现时，需要使用流识别缓冲记录一段时间内访存的cache行地址。预取引擎识别到流访问则进行预取。关联预取（association based prefetching）利用访存地址之间存在的关联性进行预取。

启用时机

预取可以在不同的地方启用并将预取数据放置到目的地址。预取可以在L1/L2/L3高速缓存，内存控制器，甚至是存储芯片中预加载DRAM行缓存时被启用。预取的数据通常被保存在启用预取的那一层，比如启用预取的高速缓存，或者在一个独立的预取缓冲区，从而避免预取数据“污染”缓存。

多核预取

在多核处理器设计中，预取设计尤为困难。如果预取过早，那么在一个处理器在访问某数据块之前，可能会因为另一个处理器对该数据块的访问导致数据块无效。同时，被预取的数据块可能替换了更有用的数据块。即使加大高速缓存的容量也不能像单处理器那样解决这些问题。过早的预取会导致某处理器从其它处理器中“窃取”缓存块，而这些缓存块很可能又被其它处理器再“窃取”回去。极端情况下，不合适的预取会给多处理器设计带来灾难，缓存缺失更加严重，进而大大降低性能。

预取需要考虑的点

1. 预取哪块数据：必须能准确地判断所需预取的数据，这个很好理解，无效数据对我们毫无用处，只会白白耗费电源
2. 何时开始预取：如果预取不及时，甚至晚于需要相关数据的节点，那么这个策略毫无帮助，浪费硬件资源，预取过早亦同理
3. 数据存放在哪：如果相关预取数据存放不合理，将会将后续需要用到的数据踢出CPU，造成性能下降

指令预取 and 数据预取

ITLB，DTLB，L1I，L1D来分别服务指令和数据的访问。指令访问内存的模式比较好琢磨，毕竟只有读取没有写入，读取也比较规规矩矩，无法就顺序执行，不开心了就条件判断一下，跳转一下，所以目前CPU的指令预取策略都做得比较成熟，正确率甚至达到了大于99%的水平。相对来说，数据预取就难以摸透了很多，更少规律性地读写操作，当然也意味着对预测策略设计者来说更具有挑战性。

指令预取
需要考虑分支与循环

• Next-line prefetching：顺序预取
• Branch-predictor-directed prefetchers：分支预取
• ……

数据预取
可以将数据预取简单分为四类：

1. 第一类就是简单根据Cache Line的访问步幅来进行下一个Cache Line的预取，可以简单认为就是指令预取中的Next-line预取。
2. 第二类是针对重复遍历的序列进行记录，以发现重复模式时进行预取，这种对指针的数据比较有效。
3. 第三类时针对常规的数据结构进行针对性地设计相关预取策略。
4. 第四类在CPU的乱序阶段前就进行预取相应的识别和预取，故不依赖内存地址访问的规律性和重复性

具体预取器

• Stride and stream prefetchers：每次会记录最后一次访问的地址，并且还会记录最后两次访问地址直接的间距。只要该模块连续两次观察到相同的间距时，便会用最后一次访问的地址加上相应的部分作为要预取的地址进行提前的预取。
• Address-correlated prefetching：该策略等于维护了一个地址访问记录日志，把某个地址后续可能会访问的地址记录下来，当然出于资源的限制，只能记录少数的地址和少数的候选人。
• Spatially correlated prefetching：利用数据访问的规律性和重复性
• DELTA-CORRELATED LOOKUP：GHB（global history buffer），维护一个全局历史信息的Buffer，然后设计者可以根据自己的喜好，比如选择用Delta值进行索引，再结合Miss的数据地址，得到要进行预取的地址进行预取。
• Execution-based prefetching：不依赖于数据规律性/重复性，也不依赖于数据结构布局的基于执行的预取策略。这种策略会尝试在执行数据存取操作之前进行预取操作，利用CPU中的Stall周期和空闲的硬件资源，提前在执行之前把将要之前存取的指令地址提前在Cache中准备好，有点提前找打考试内容并打小抄的感觉。

https://zhuanlan.zhihu.com/p/491673969