存储器分级结构图_多级存储器体系结构

计算机系统：存储器分级 　　1、为什么会有存储器分级策略？ 　　从需求上讲，我们希望存储器速度快、体积小、空间大、能耗低、散热好、断电数据不丢失。但在现实中，我们往往无法把所有需求都实现。 　　下面我们举几个例子，带你深入体会一下，比如：如果一个存储器的体积小，那它存储空间就会受到制约。如果一个存储器电子件密度很大，那散热就会有问题。因为电子件都会产生热能，所以电子件非常集中的 CPU，就需要单独的风扇或者水冷帮助电子件降温。如果一个存储器离 CPU 较远，那么在传输过程中必然会有延迟，因此传输速度也会下降。 　　​ 大多数人的认知里，光速是很快的，而信号又是以光速传输的。既然光速这么快，那信号的延迟应该很小才对。但事实并不是这样，比如时钟信号是 1GHz 的 CPU，1G 代表 10 个亿，因此时钟信号的一个周期是 1/10 亿秒。而光的速度是 3×10 的 8 次方米每秒，就是 3 亿米每秒。所以在CUP的一个时钟周期内，光只能前进 30 厘米。 　　

　　2、存储器分级策略 　　因为不能用一块存储器来解决所有需要，于是就把需求分级 　　​ 一种可行的方案，就是根据数据的使用频率使用不同的存储器：高频使用的数据，读写越快越好，因此用最贵的材料，放到离 CPU 最近的位置；使用频率越低的数据，我们放到离 CPU 越远的位置，用越便宜的材料。 　　通常把存储器分为这个几个等级：寄存器；L1-Cache；L2-Cache；L3-Cahce；内存；硬盘/SSD。 　　2.1、寄存器 　　​ 寄存器在CPU之内，紧挨着 CPU 的控制单和逻辑计算单，它所使用的材料速度也是最快的。因为，存储器的速度越快、能耗越高、产热越大，而且花费也是最贵的，因此其数量不能很多。 　　寄存器的数量通常在几十到几百之间，每个寄存器可以用来存储一定字节（byte）的数据。比如：32 位 CPU 中大多数寄存器可以存储 4 个字节；64 位 CPU 中大多数寄存器可以存储 8 个字节。 　　寄存机的访问速度非常快，一般要求在半个 CPU 时钟周期内完成读写。比如一条要在 4 个周期内完成的指令，除了读写寄存器，还需要解码指令、控制指令执行和计算。如果寄存器的速度太慢，那 4 个周期就可能无法完成这条指令了。 　　2.2、L1-Cache 　　​ L1- 缓存在 CPU 中，相比寄存器，虽然它的位置距离 CPU 核心更远，但造价更低。通常 L1-Cache 大小在几十 Kb 到几百 Kb 不等，读写速度在 2~4 个 CPU 时钟周期。 　　2.2、L2-Cache 　　​ L2- 缓存也在 CPU 中，位置比 L1- 缓存距离 CPU 核心更远。它的大小比 L1-Cache 更大，具体大小要看 CPU 型号，有 2M 的，也有更小或者更大的，速度在 10~20 个 CPU 周期。 　　2.3、L3-Cache 　　​ L3- 缓存同样在 CPU 中，位置比 L2- 缓存距离 CPU 核心更远。大小通常比 L2-Cache 更大，读写速度在 20~60 个 CPU 周期。L3 缓存大小也是看型号的，比如 i9 CPU 有 512KB L1 Cache；有 2MB L2 Cache； 有16MB L3 Cache。 　　2.4、内存 　　​ 内存的主要材料是半导体硅，是插在主板上工作的。因为它的位置距离 CPU 有一段距离，所以需要用总线和 CPU 连接。因为内存有了独立的空间，所以体积更大，造价也比上面提到的存储器低得多。现在有的个人电脑上的内存是 16G，但有些服务器的内存可以到几个 T。内存速度大概在 200~300 个 CPU 周期之间。 　　2.5、SSD和硬盘 　　​ SSD 也叫固态硬盘，结构和内存类似，但是它的优点在于断电后数据还在。内存、寄存器、缓存断电后数据就消失了。内存的读写速度比 SSD 大概快 10~1000 倍。以前还有一种物理读写的磁盘，我们也叫作硬盘，它的速度比内存慢 100W 倍左右。因为它的速度太慢，现在已经逐渐被 SSD 替代。 　　

　　​ 当CPU 需要内存中某个数据的时候，如果寄存器中有这个数据，我们可以直接使用；如果寄存器中没有这个数据，我们就要先查询 L1 缓存；L1 中没有，再查询 L2 缓存；L2 中没有再查询 L3 缓存；L3 中没有，再去内存中拿。 　　下面是三级缓存的处理速度参考表：从CPU到大约需要的CPU时钟周期大约需要的时间(单位ns)寄存器1 cycleL1 Cache~2-4 cycles~0.5-1 nsL2 Cache~10-20 cycles~3-7 nsL3 Cache~40-60 cycles~15 ns跨槽传输~20 ns内存~200-300 cycles~60-120ns 　　时钟周期（cycles）：是CPU主频的倒数，比如2GHZ主频的CPU，一个时钟周期是0.5ns； 　　3、 高速缓存CPU的执行过程 　　程序以及数据被加载到主内存指令和数据被加载到CPU的高速缓存CPU执行指令，把结果写到高速缓存高速缓存中的数据写回主内存 　　下图是Intel Core i5-4285U的CPU三级缓存示意图： 　　

Intel Core i5-4285U的CPU三级缓存 　　​ 根据上图给的现代CPU结构图可以看到，一个 CPU 里通常会有多个 CPU 核心，比如上图中的 1 号和 2 号 CPU 核心，并且每个 CPU 核心都有自己的 L1 Cache 和 L2 Cache，而 L1 Cache 通常分为 Data Cache（数据缓存） 和 Instruction Cache（指令缓存），L3 Cache 则是多个核心共享的，这就是 CPU 典型的缓存层次。 如果数据和指令都存储在 L1- 缓存中，如果数据缓存覆盖了指令缓存，就会产生非常严重的后果。因此，L1- 缓存通常会分成两个区域，一个是指令区，一个是数据区。那么 L2/L3 需不需要这样分呢？其实，是不需要的。因为 L2 和 L3，不需要协助处理指令预读的问题。 　　上面提到的都是 CPU 内部的 Cache，放眼外部的话，还会有内存和硬盘，这些存储设备共同构成了金字塔存储层次。如下图所示 　　

　　从上图也可以看到，从上往下，存储设备的容量会越大，而访问速度会越慢。至于每个存储设备的访问延时，你可以看下图的表格： 　　

　　​ 你可以看到， CPU 访问 L1 Cache 速度比访问内存快 100 倍，这就是为什么 CPU 里会有 L1~L3 Cache 的原因，目的就是把 Cache 作为 CPU 与内存之间的缓存层，以减少对内存的访问频率。 　　CPU 从内存中读取数据到 Cache 的时候，并不是一个字节一个字节读取，而是一块一块的方式来读取数据的，这一块一块的数据被称为 CPU Cache Line（缓存块），所以 CPU Cache Line 是 CPU 从内存读取数据到 Cache 的单位。 　　至于 CPU Cache Line 大小，可以通过CPU-Z查看，我的电脑 L1 Cache Line 大小是 32字节，也就意味着 L1 Cache 一次载入数据的大小是 32字节。 　　

　　4、缓存条目结构 　　4.1、缓存中的数据结构和算法 　　​ 无论是缓存，还是内存，它们都是一个线性存储器，也就是数据一个挨着一个的存储。如果我们把内存想象成一个只有 1 列的表格，那么缓存就是一个多列的表格，这个表格中的每一行叫作一个缓存条目。 　　​ 缓存本质上是一个 Key-Value 的存储，它的 Key 是内存地址，值是缓存时刻内存地址中的值。 　　先思考一种简单的方案，一个缓存条目设计 2 列： 内存的地址； 缓存的值。 　　​ CPU 读取到一个内存地址，我们就增加一个条目。当我们要查询一个内存地址的数据在不在 L1- 缓存中的时候，可以遍历每个条目，看条目中的内存地址是否和查询的内存地址相同。如果相同，我们就取出条目中缓存的值。 　　这个方法需要遍历缓存中的每个条目，因此计算速度会非常慢，在最坏情况下，算法需要检查所有的条目，所以这不是一个可行的方案。 　　以上方案改造： 　　​ 上面的方案无法快速确定一个内存地址缓存在哪一行。因此我们想要找到一个更好的方法，让我们看到一个内存地址，就能够快速知道它在哪一行。 　　这里，我们可以用一个数学的方法。比如有 1000 个内存地址，但只有 10 个缓存条目。内存地址的编号是 0、1、2、3，…，999，缓存条目的编号是 0~9。我们思考一个内存编号，比如 701，然后用数学方法把它映射到一个缓存条目，比如 701 整除 10，得到缓存条目 1。 　　用这种方法，我们每次拿到一个内存地址，都可以快速确定它的缓存条目；然后再比较缓存条目中的第一列内存地址和查询的内存地址是否相同，就可以确定内存地址有没有被缓存。 　　延伸一下，这里用到了一种类似哈希表的方法：，其实就构成了一个简单的哈希函数。 　　4.2、指令预读 　　​ CPU 顺序执行内存中的指令，CPU 执行指令的速度是非常快的，一般是 2~6 个 CPU 时钟周期；而内存的读写速度其实是非常慢的，大概有 200~300 个时钟周期。 所以CPU 是不能从内存中一条条读取指令再执行的，如果是这样做，那每执行一条指令就需要 200~300 个时钟周期了。 　　​ 一个解决办法就是 CPU 把内存中的指令预读几十条或者上百条到读写速度较快的 L1- 缓存中，因为 L1- 缓存的读写速度只有 2~4 个时钟周期，是可以跟上 CPU 的执行速度的。 　　​ 这里又产生了另一个问题：如果数据和指令都存储在 L1- 缓存中，如果数据缓存覆盖了指令缓存，就会产生非常严重的后果。因此，L1- 缓存通常会分成两个区域，一个是指令区，一个是数据区。L2/L3 不需要分区。因为 L2 和 L3，不需要协助处理指令预读的问题。 　　4.3、缓存的命中率 　　所谓命中就是指在缓存中找到需要的数据。和命中相反的是穿透，也叫 miss，就是一次读取操作没有从缓存中找到对应的数据。 　　

　　​ 据统计，L1 缓存的命中率在 80% 左右，L1/L2/L3 加起来的命中率在 95% 左右。因此，CPU 缓存的设计还是相当合理的。只有 5% 的内存读取会穿透到内存，95% 都能读取到缓存。 这也是为什么程序语言逐渐取消了让程序员操作寄存器的语法，因为缓存保证了很高的命中率，多余的优化意义不大，而且很容易出错。 　　4.3.1： 数据缓存命中率 　　抛出一个问题：假设有一个二维数组，总共有1M个条目，如果我们要遍历这个二维数组，应该逐行遍历还是逐列遍历呢？ 　　​ 经过测试，形式一 执行时间比形式二 快好几倍。 　　​ 之所以有这么大的差距，是因为二维数组 所占用的内存是连续的，形式一用 访问数组素的顺序，正是和内存中数组素存放的顺序一致。当 CPU 访问 时，由于该数据不在 Cache 中，于是会「顺序」把跟随其后的 3 个素从内存中加载到 CPU Cache，这样当 CPU 访问后面的 3 个数组素时，就能在 CPU Cache 中成功地找到数据，这意味着缓存命中率很高，缓存命中的数据不需要访问内存，这便大大提高了代码的性能。 　　而如果用形式二的 来访问，则访问的顺序就是： 　　​ 你可以看到，访问的方式跳跃式的，而不是顺序的，那么如果 N 的数值很大，那么操作 时，是没办法把 也读入到 CPU Cache 中的，既然 没有读取到 CPU Cache，那么就需要从内存读取该数据素了。很明显，这种不连续性、跳跃式访问数据素的方式，可能不能充分利用到了 CPU Cache 的特性，从而代码的性能不高。 　　​ 那访问 素时，CPU 具体会一次从内存中加载多少素到 CPU Cache 呢？这个问题，在前面我们也提到过，这跟 CPU Cache Line 有关，它表示 CPU Cache 一次性能加载数据的大小，根据以上我的电脑 L1 Cache Line 大小是 32字节，也就意味着 L1 Cache 一次载入数据的大小是 32字节。 　　​ 也就是说，当 CPU 访问内存数据时，如果数据不在 CPU Cache 中，则会一次性会连续加载 64 字节大小的数据到 CPU Cache，那么当访问 时，由于该素不足 64 字节，于是就会往后顺序读取 到 CPU Cache 中。顺序访问的 因为利用了这一特点，所以就会比跳跃式访问的 要快。 　　4.3.2、指令缓存的命中率 　　​ 提升数据的缓存命中率的方式，是按照内存布局顺序访问，那针对指令的缓存该如何提升呢？ 　　我们以一个例子来看看，有一个素为 0 到 100 之间随机数字组成的一维数组： 　　第一个操作，循环遍历数组，把小于 50 的数组素置为 0；第二个操作，将数组排序； 　　那么问题来了，你觉得先遍历再排序速度快，还是先排序再遍历速度快呢？ 　　​ 在回答这个问题之前，我们先了解 CPU 的分支预测器。对于 if 条件语句，意味着此时至少可以选择跳转到两段不同的指令执行，也就是 if 还是 else 中的指令。那么，如果分支预测可以预测到接下来要执行 if 里的指令，还是 else 指令的话，就可以「提前」把这些指令放在指令缓存中，这样 CPU 可以直接从 Cache 读取到指令，于是执行速度就会很快。 　　​ 当数组中的素是随机的，分支预测就无法有效工作，而当数组素都是是顺序的，分支预测器会动态地根据历史命中数据对未来进行预测，这样命中率就会很高。 　　​ 因此，先排序再遍历速度会更快，指令的命中率会更高这是因为排序之后，数字是从小到大的，那么前几次循环命中 的次数会比较多，于是分支预测就会缓存 里的 指令到 Cache 中，后续 CPU 执行该指令就只需要从 Cache 读取就好了。 　　4.3.3 、多核 CPU 的缓存命中率 　　​ 在单核 CPU，虽然只能执行一个线程，但是操作系统给每个线程分配了一个时间片，时间片用完了，就调度下一个线程，于是各个线程就按时间片交替地占用 CPU，从宏观上看起来各个线程同时在执行。 　　​ 而现代 CPU 都是多核心的，线程可能在不同 CPU 核心来回切换执行，这对 CPU Cache 不是有利的，虽然 L3 Cache 是多核心之间共享的，但是 L1 和 L2 Cache 都是每个核心独有的，如果一个线程在不同核心来回切换，各个核心的缓存命中率就会受到影响，相反如果线程都在同一个核心上执行，那么其数据的 L1 和 L2 Cache 的缓存命中率可以得到有效提高，缓存命中率高就意味着 CPU 可以减少访问 内存的 频率。 　　​ 当有多个同时执行「计算密集型」的线程，为了防止因为切换到不同的核心，而导致缓存命中率下降的问题，我们可以把线程绑定在某一个 CPU 核心上，这样性能可以得到非常可观的提升。 　　4.4、缓存置换问题 　　​ L1- 缓存条目已经存满了，接下来 CPU 又读了内存，需要把一个新的条目存到 L1- 缓存中，既然有一个新的条目要进来，那就有一个旧的条目要出去。所以，这个时候我们就需要用一个算法去计算哪个条目应该被置换出去。这个问题叫作缓存置换问题。有关缓存置换问题，后面详细讨论。 　　总结： 　　存储器分级策略，讨论了 L1/L2/L3 缓存的工作原理，是所有缓存知识的源头。所有缓存系统的设计，都是存储资源的分级。我们在设计缓存的时候，除了要关心整体架构外，还需要注意细节，比如：条目怎么设计？算法怎么设计？命中率怎么提高？缓存怎么置换等？ 　　​