天下事一一责报，则必有大失望之时。
-- 曾国藩
随着工艺的提升，高速缓存的大小虽然不断在增加，但是远远不及主存的容量。众所周知，一旦发生缓存缺失，其代价（penalty）很大，要等待很多时钟周期把数据从主存搬移到缓存中。这期间CPU的流水线很可能要停下来。为了解决这个问题，行业大牛们想了很多办法，Cache预取（prefetch）技术就是其中之一。现在的高速缓存设计通常采用了预取机制。
顾名思义，预取就是预先把程序需要的数据搬移到缓存中，而不必等到缓存缺失时再去搬运。预取分为软件预取和硬件预取。有的处理器提供专门用于预取的指令，但是怎么使用和何时使用指令进行预取是由软件决定的。因此这种方式被称为软件预取（software prefetching）。首先实现预取指令的处理器是Motorola的88110处理器。软件预取指令可以由编译器自动加入，但是在很多场景，更加有效的方式是由程序员主动加入预取指令。这些预取指令在进行大规模向量运算时，可以发挥巨大的作用。在这一场景中，通常含有大规模的有规律的循环迭代（loop iteration）。这类程序通常需要访问处理较大规模的数据，从而在一定程度上破坏了程序的时间和空间的局部性（temporal and spatial locality），这使得数据预取成为提高系统效率的有效手段。
预取的另一种设计方式是设计对软件透明的硬件结构，动态观测程序的行为并产生相应的预取请求，这种方式称为硬件预取（hardware prefetching）。说简单些，就是用硬件根据某些规律去猜测处理器未来将要访问的数据地址。由于硬件预取技术是与高速缓存设计直接相关，我们不妨多看一些。根据可以应对的数据访问模式类型，顺序预取（sequential prefetching）检测并预取对连续区域进行访问的数据。顺序预取是最简单的预取机制，因为总是预取当前cache line的下一条line，硬件开销小，但是对访存带宽的需求高。步长预取（stride prefetching）检测并预取连续访问之间相隔s个缓存数据块的数据，其中s即是步长的大小。硬件实现需要使用访问预测表，记录访问的地址，步长以及访存指令的pc值。流预取（stream prefetching）对流访问特征进行预取，流访问特征是指一段时间内程序访问的cache行地址呈现的规律，这种访问规律在科学计算和工程应用中广泛存在。硬件实现时，需要使用流识别缓冲记录一段时间内访存的cache行地址。预取引擎识别到流访问则进行预取。关联预取（association based prefetching）利用访存地址之间存在的关联性进行预取。
采用硬件预取的优点是不需要软件进行干预，不会扩大代码的尺寸，不需要浪费一条预取指令来进行预取，而且可以利用任务实际运行时的信息（run time information）进行预测，这些是硬件预取的优点。硬件预取的缺点是预取结果有时并不准确，有时预取的数据并不是程序执行所需要的，比较容易出现缓存污染（cache pollution）的问题。更重要的是，采用硬件预取机制需要使用较多的系统资源。在很多情况下，耗费的这些资源与取得的效果并不成比例。
必须强调的是，预取对程序肯定是会有影响的。但并非所有程序在开启预取时都是性能增益的，预取对那些有规律的数据采集和指令执行过程中才会发挥最大功效，而在随机访问事务中，预取反而是有害的，因为随机事务中的数据都是随机的，预取进来的数据在接下去的执行中并不能有效利用，只是白白浪费了缓存空间和存储带宽。
通常有几个指标来评价预取机制的有效性：覆盖率（coverage），准确率（accuracy），及时性（timeliness）。覆盖率被定义为原始缓存缺失中被预取的比例，由于预取，缓存缺失变为缓存命中或部分缓存命中。准确率被定义为预取数据中有效的比例，也就是导致缓存命中的比例。及时性描述了预取的数据可以提前多久到达，进而决定了缓存缺失时时延是否可以被完全隐藏。
一个理想的预取机制应该是高覆盖率，最大程度消除缓存缺失；高准确率，不会增加过多的存储带宽消耗；及时性，完全隐藏缓存缺失时延。我们可以看出来，这三个指标在某种程度上是对立的。如果采取激进的预取，可以提高覆盖率，但是准确率就会下降；如果采取保守的预取，只对准确预测的数据进行预期，可以提高准确率，但是覆盖率会降低。对于及时性，如果预取启动过早，可能在处理器使用该数据前就被替换出缓存或者预取缓冲区，“污染”了高速缓存；如果启动过晚，可能就无法完全隐藏缓存缺失时延。
需要指出的是，预取可以在不同的地方启用并将预取数据放置到目的地址。预取可以在L1/L2/L3高速缓存，内存控制器，甚至是存储芯片中预加载DRAM行缓存时被启用。预取的数据通常被保存在启用预取的那一层，比如启用预取的高速缓存，或者在一个独立的预取缓冲区，从而避免预取数据“污染”缓存。
在多核处理器设计中，预取设计尤为困难。如果预取过早，那么在一个处理器在访问某数据块之前，可能会因为另一个处理器对该数据块的访问导致数据块无效。同时，被预取的数据块可能替换了更有用的数据块。即使加大高速缓存的容量也不能像单处理器那样解决这些问题。过早的预取会导致某处理器从其它处理器中“窃取”缓存块，而这些缓存块很可能又被其它处理器再“窃取”回去。极端情况下，不合适的预取会给多处理器设计带来灾难，缓存缺失更加严重，进而大大降低性能。
预取机制是一个很大的话题，我了解的也只是九牛一毛，希望这篇短文能起到一个抛砖引玉的作用。
作者：老秦谈芯
来源：https://mp.weixin.qq.com/s/ESmLMRcmOwL5\_aNREjrmqA
作者微信公众号
相关文章推荐
更多IC设计技术干货请关注IC设计技术专栏。
