Cache为什么能提升性能

1. Cache的容量设计

上篇文章中介绍到CPU Cache是分级的,L1 Cache是集成在Core内部的,L2则是紧贴着Core,而L3是多个Core共享的。离Core(流水线)越近的分级速度越快,但容量也更小,并且造价愈贵。Cache的实现采用了高速的SRAM电路 (静态随机存取存储器: Static Random-Access Memory),SRAM相对DRAM (动态随机存取存储器: Dynamic Random Access Memory)要复杂和庞大的多,即使不考虑成本能做到无限增大,但因为电路复杂度的提升其性能即访问速度必然会下降,另外也会使得CPU的面积急速膨胀。最终,CPU的每一级Cache的容量都是在设计之初考虑各方面因素折中后的结果(trade-off)。下图是AMD Zen的CCX的die shot[来源:1. Zen - Microarchitectures - AMD],从图中我们就能看中L2及L3 Cache占据了很大一部分的面积:

一般而言L1 Cache约几十K,L2则是几百K,L3是几M或几十、几百M,但相比较内存动不动几十G的大小来说还是小了太多,根本不在一个数量级上。那么问题来了:Cache容量比内存小了太多,为什么根本不在一个数据量级的Cache能够大副度提升系统性能?

2. 局部性原理 (Principle of Locality)

简言之,程序倾向于访问(或执行)刚刚访问过的数据(执行过的指令)或与之相临近的数据(指令)

2.1 时间局部性 (Temporal locality):

刚刚被访问的地址(数据)在未来有很大的可能性被再次访问,即用过的数据可能会再次被用到

2.2 空间局部性 (Spatial locality):

刚刚被访问的地址的临近位置在未来有很大的可能被访问,以数组D[]为例,当前访问的是D[i],那么D[i+1]有很大的可能将被访问

2.3 算法局部性:

程序代码也遵守2/8法则,即帕累托法则(Pareto principle,亦称关键少数法则),80%的时间都是在执行20%的代码

正是因为局部性原理,少量的Cache大大减少了数据的访问延迟,从而提升了整体性能。

3. Cache的放大效应

先来考虑一个问题:Cache命中率(Cache Hit) 99%与98%的差别会有多大?从数值上来看二者本身仅相差1%,性能上最终能有多大差别呢?

假设命中L1的延时为4 cycles,不命中的话需要从内存中读取数据的延时为150 cycles,那么:
99%命中率的情况: 0.99 * 4 + 0.01 * 150 = 5.46
98%命中率的情况: 0.98 * 4 + 0.02 * 150 = 6.92

后者比前者的延时多了(6.92 - 5.46) / 5.46 = 26.7% 之多。换成95%的命中率的话,延时将高达99%命中率时的一倍之多。由此看来,不命中(Cache Miss)所带的性能惩罚巨大,这也预示了未来Cache发展的趋势,即容量将越来越大,拥有GB级Cache容量的CPU将指日可待,另外增加L4分级也将是不可避免的,有兴趣的读者可进一步参阅 [2. The Next Platform: Cache Is King]。

4. Cache Miss的原因

前面说了Cache Miss的惩罚,下面说一下会导致Cache Miss的因素,可以简单归纳为3C:
1. Cold (Compulsory) Miss: 第一次访问数据时,数据根本不在Cache中
2. Conflict Miss: 因冲突导致Cache Line被驱逐出Cache,上一篇文章中提到了相关的方法,如Evict(驱逐)、Prime(装填)等,当然冲突所导致的Cache Miss只针对组相联的Cache结构(直接映射可以认为是单路组相联),而全相联的Cache结构是没有Conflict Miss的,后续还会针对此课题做详细的介绍
3. Capacity Miss: Cache的容量毕竟有限,如果程序确实需要密集访问大量内存时,Cache必然是不够的

在指定的CPU硬件上如果想提升Cache Hit的话就要从这几个因素上着手,如通过硬件预取以减少Cold Miss,通过程序算法改进及结构重组可减少2和3所带来的Cache Miss的发生概率,本文先点到为止,后面将进行详细拆解。

5. 参考资料

1. wikichip: Zen - Microarchitectures - AMD
2. The Next Platform: Cache Is King

Continue reading » · Written on: 08-30-20 · No Comments »

Leave a Reply