CPU多级缓存架构

CPU的执行效率是内存读取效率的10倍左右，而内存的读取效率又是磁盘读取效率的几千倍到几百万倍，也就是说在执行效率上CPU >> 内存 >> 硬盘。因此，为了提升CPU的执行效率，尽量减少CPU与内存之间的交互以提升系统的运行效率，CPU上集成了多级缓存架构，一般是3级缓存架构。

对于3级缓存架构而言，CPU从内存当中读取数据的时候，并不会只读取自己想要的部分，而是会读取足够的字节来填入高速缓存行（Cache Line），不同的CPU的高速缓存行的大小不同。这样一来当CPU需要访问相邻数据的时候，就不必每次都从内存中读取，提升了CPU的执行效率。

如上图所示，现在的CPU一般是多核心结构，即存在多个内核可以执行程序。因此，计算机的前面2级缓存L1、L2缓存被设计为处于CPU每个核心的内部供单个核心使用，而L3缓存则是设置在CPU当中，供CPU内部的所有的核心使用。

具体来说，L1 Cache（一级缓存）通常被分为数据缓存和指令缓存，即L1 D-Cache、L1 I-Cache，而L2 Cache（二级缓存）和L3 Cache（三级缓存）则只是缓存数据。

L1 Cache（一级缓存）通常被分为数据缓存和指令缓存，即L1 D-Cache、L1 I-Cache，每个逻辑核都有自己独立的L1 Cache。数据缓存，用于存储最近被访问的数据，提供对数据的快速读取和写入。指令缓存， 用于存储处理器当前正在执行的指令，以提高指令的获取速度。

L2 Cache（二级缓存）比一级缓存大一些，一般大小在几百k的级别，如256k。 一般情况下，每个物理核拥有自己独立的L2 Cache，但逻辑核可能共享同一物理核的L2 Cache。 L2 Cache的容量比L1 Cache大，访问速度相对较快，但比L1 Cache慢。二级缓存就是一级缓存的缓冲期，一级缓存的制造成本高容量有限，二级缓存的作用就是存储那些CPU处理时需要用到，但是一级缓存又无法存储的数据。

L3 Cache（三级缓存）比二级缓存更大，一般大小在10几MB，如12MB。L3 Cache通常位于多个物理核之间，被它们共享， L3 Cache的容量相对较大，速度比L2 Cache慢一些。

从缓存的存储空间来说从大到小依次为：内存 > L3 Cache > L2 Cache > L1 Cache > 寄存器。从缓存的存取速度上来说，从快到慢依次为：寄存器 > L1 Cache > L2 Cache > L3 Cache > 内存，如下面得表所示：

这种层次结构有助于提高系统性能，因为它充分利用了局部性原理，并在速度和容量之间找到了平衡。较小但更接近CPU的缓存层次可以迅速提供处理器所需的数据，而较大但速度相对较慢的层次则提供了更大的存储容量。

缓存原理

缓存行（Cache Line）

Cache Line是缓存对数据进行存取的最小单元，根据局部性原理缓存每次读取数据的时候不会只读取单个数据，而是会读取相邻的一行数据，以提升数据的存取效率。每个Cache Line包含Flag、Tag和Data三个部分，Data的大小一般是64 Bytes，而Flag和Tag则与CPU型号相关。从内存向缓存读写数据的时候都是加载整个Cache Line，并且一个Cache Line和一块儿大小相同的内存区域相关联。

如上图所示，缓存是按照矩阵方式排列(M × N)，横向是组(Set)，纵向是路(Way)。每一个元素是缓存行(cache line)。那么给定一个虚拟地址 addr 如何在缓存中定位它呢？首先把它所在的组号找到，即：

1
2

//左移6位是因为 Block Offset 占 addr 的低 6 位，Data 为 64 字节
Set Index = (addr >> 6) % M;

然后遍历该组所有的路，找到 cache line 中的 Tag 与 addr 中 Tag 相等为止，所有路都没有匹配成功，那么缓存未命中。

1

整个缓存容量 = Set × Way × 缓存行大小

缓存行替换策略

常用的缓存替换策略是最近最少使用算法（Least Recently Used ，LRU），可以给每个缓存行设置一个参数记录其访问次数，每次需要淘汰缓存行的时候使用频率最低的缓存行被淘汰。

LRU算法的实现方式很多，最常用的是——位矩阵。位矩阵会定义一个行、列都与缓存路数（way）相同的矩阵，当访问某个way对应的缓存行的时候，会讲该路对应的所有行置为1，再将该way对应的所有列都置为0。那么，最近最少使用的缓存行所对应的矩阵行当中的个数最少，就会最先被替换出去。

缓存缺失

缓存缺失就是缓存未命中，需要把内存中数据加载到缓存，所以运行速度会变慢。

程序局部性

程序局部性就是读写内存数据时读写连续的内存空间，目的是让缓存可以命中，减少缓存缺失导致替换的开销。

我电脑上运行下面代码

1
2
3
4
5

int M = 10000, N = 10000;
char (*a)[N] = (char(*)[N])calloc(M * N, sizeof(char));
for(int i = 0; i < M; i++)
    for(int j = 0; j < N; j++)
        a[i][j]++;

结果：循环 100000000 次，耗时 314 ms。利用了程序局部性原理，缓存命中率高。

修改上面的代码如下，并运行

1
2
3
4
5

int M = 10000, N = 10000;
char (*a)[N] = (char(*)[N])calloc(M * N, sizeof(char));
for(int j = 0; j < N; j++)
    for(int i = 0; i < M; i++)
        a[i][j]++;

结果：循环 100000000 次，耗时 1187 ms。没有利用程序局部性原理，缓存命中率低，所以耗时增加了 2 倍。

伪共享（false-sharing）

当两个线程同时各自修改两个相邻的变量，由于缓存是按缓存行来整体组织的，当一个线程对缓存行中数据执行写操作时，必须通知其他线程该缓存行失效，导致另一个线程从缓存中读取其想修改的数据失败，必须从内存重新加载，导致性能下降。

我电脑运行下面代码

1
2
3
4
5
6
7
8
9
10
11
12

struct S {
    long long a;
    long long b;
} s;
std::thread t1([&]() {
    for(int i = 0; i < 100000000; i++)
        s.a++;
});
std::thread t2([&]() {
    for(int i = 0; i < 100000000; i++)
        s.b++;
});

结果：耗时 512 ms，原因上面提到了，就是两个线程互相影响，使对方的缓存行失效，导致直接从内存读取数据。

解决办法是对上面代码做如下修改：

1
2
3
4
5

struct S {
    long long a;
    long long noop[8];
    long long b;
} s;

结果：耗时 181 ms，原因是通过 long long noop[8] 把两个数据（a 和 b）划分到两个不同的缓存行中，不再互相使对方的缓存失效，所以速度变快了。

寄存器和缓存区别

理论上的区别

寄存器（Registers）和缓存（Cache）是计算机体系结构中的两种不同的硬件结构，它们在功能和作用上有所区别。寄存器是位于CPU（中央处理器）内部的高速存储器，用于存储指令执行过程中的数据和中间结果。直接与CPU内部的执行单元相连，因此它们的访问速度非常快，可以在一个时钟周期内读取或写入数据。寄存器的容量有限，而且每个CPU架构都有特定的寄存器数量和功能。寄存器用于暂存指令的操作数、中间计算结果和程序计数器等。

缓存是位于CPU和主内存（RAM）之间的高速存储器，用于缓存常用的数据和指令，以提高数据访问的效率。缓存的容量通常比寄存器大，但仍然远远小于主内存的容量。缓存被分为多个级别（如L1、L2、L3缓存），每个级别的容量和访问速度逐渐降低。缓存的访问速度比主内存快得多，但比寄存器慢一些。缓存采用一定的替换策略和缓存块的管理机制，以提供高效的数据访问。区别总结如下：

1. 速度：寄存器是最快的存储器，可以在一个时钟周期内访问；缓存的访问速度比主内存快，但比寄存器慢一些。
2. 容量：寄存器容量有限，每个CPU架构都有特定的寄存器数量和功能；缓存的容量比寄存器大，但仍然远远小于主内存的容量。
3. 位置：寄存器位于CPU内部，直接与执行单元相连；缓存位于CPU和主内存之间。
4. 功能：寄存器用于存储指令执行过程中的数据和中间结果；缓存用于缓存常用的数据和指令，以提高数据访问效率。

总体而言，寄存器和缓存在计算机体系结构中扮演不同的角色。寄存器用于快速存取和处理数据，而缓存则用于提供更快的数据访问速度，减少CPU对主内存的访问次数，提高计算机系统的整体性能。

逻辑电路上区别

寄存器逻辑电路结构：

• 寄存器是存储器件，通常由触发器（flip-flop）构成，每个触发器可以存储一个位或多个位的数据。
• 寄存器的逻辑电路结构相对简单，主要包括数据输入端、数据输出端、时钟信号和控制信号。
• 寄存器的主要功能是存储和暂存数据，它们在CPU内部用于保存指令执行过程中的数据和中间结果。

缓存逻辑电路结构：

• 缓存是高速缓存存储器，通常由多级缓存组成。每个级别的缓存都有自己的逻辑电路结构。
• 缓存的逻辑电路结构更加复杂，包括标签（Tag）、索引（Index）、块（Block）和数据存储器等组成部分。
• 缓存的逻辑电路结构还涉及到替换策略、缓存一致性协议和高速缓存的映射方式（如直接映射、全相联映射和组相联映射）等。
• 缓存的主要功能是通过在CPU和主内存之间提供快速的数据访问，减少对主内存的访问次数，提高数据访问效率。

总结起来，寄存器的逻辑电路结构相对简单，主要由触发器构成，用于存储和暂存数据。而缓存的逻辑电路结构更加复杂，包括标签、索引、块和数据存储器等组成部分，用于提供快速的数据访问和有效的缓存策略。

总线和总线锁

总线（Bus）从它的英文名字可以看出，就像个巴士一样，用来运输计算机各个硬件设备之间的数据。 实际上总线是计算机内部用于传输数据、地址和控制信号的硬件设备，连接了计算机内部的各个部件，如中央处理器（CPU）、内存、输入输出设备等。总线主要分为数据总线、地址总线和控制总线几类：

1. 数据总线（Data Bus）： 用于传输数据信号，指示数据在各个组件之间的传送方向。例如，32位数据总线可以一次传输32位的数据。
2. 地址总线（Address Bus）： 用于传输内存地址或I/O（输入/输出）设备的物理地址，地址总线的宽度决定了计算机的寻址能力，即能够寻址的内存或设备的数量。
3. 控制总线（Control Bus）： 用于传输控制信号，指导和同步计算机内部各个部件的操作，控制总线传输的信号包括读、写、中断、时钟等。

总线锁（Bus Lock）是一种处理器级别的锁机制，用于实现多处理器系统中的原子操作或互斥访问共享资源（如内存，L3缓存）。

在多处理器系统中，多个处理器共享同一条系统总线（Bus）。当多个处理器需要同时访问共享资源或进行原子操作时，为了保证操作的原子性和正确性，需要使用总线锁来进行同步。

总线锁的原理是通过在总线上发送锁信号来实现互斥访问。当一个处理器需要访问共享资源时，它会首先发送一个请求总线锁的信号，如果锁是可用的（没有其他处理器正在使用），那么该处理器获得总线锁，可以执行相应的操作。其他处理器在收到总线锁请求信号后，会等待锁释放。一旦处理器完成了对共享资源的访问，它会释放总线锁，允许其他处理器获取锁并执行相应的操作。

总线锁的优点是实现简单，适用于小规模的多处理器系统。然而，总线锁也存在一些缺点。首先，当多个处理器竞争总线锁时，会导致处理器之间的争用，降低系统的并行度。此外，总线锁是对整个总线进行加锁，可能导致其他处理器的访问被阻塞，从而影响整个系统的性能。

随着计算机体系结构的发展，现代处理器通常采用更高级的锁机制，如缓存行锁（Cache Line Locking）或基于硬件的原子操作指令（如CAS指令），以提供更细粒度的锁定和更好的性能。这些机制通常在缓存层或处理器内部进行锁定，减少了对总线的竞争，提高了并发性能。因此，总线锁在现代处理器中的应用已经相对较少。