文章目录
  1. 1. 为什么要有CPU Cache
  2. 2. 为什么要有多级CPU Cache
  3. 3. Cache Line
  4. 4. CPU Cache 是如何存放数据的
    1. 4.1. Fully Associative(全关联映射)
    2. 4.2. 直接映射
    3. 4.3. 组相连映射
  5. 5. 替换策略
    1. 5.1. 随机
    2. 5.2. 先进先出
    3. 5.3. LRU(最近最少使用)
  6. 6. 写模式
    1. 6.1. Write-through(直写模式)
    2. 6.2. Write-back(回写模式)

本文主要转载自卢钧轶(cenalulu)
原文地址:http://cenalulu.github.io/linux/all-about-cpu-cache/

为什么要有CPU Cache

随着工艺的提升最近几十年CPU的频率不断提升,而受制于制造工艺和成本限制,目前计算机的内存主要是DRAM并且在访问速度上没有质的突破。因此,CPU的处理速度和内存的访问速度差距越来越大,甚至可以达到上万倍。同时又由于内存数据访问的热点集中性,在CPU和内存之间用较为快速而成本较高的SDRAM做一层缓存,就显得性价比极高了。

为什么要有多级CPU Cache

随着科技发展,热点数据的体积越来越大,单纯的增加一级缓存大小的性价比已经很低了。因此,就慢慢出现了在一级缓存(L1 Cache)和内存之间又增加一层访问速度和成本都介于两者之间的二级缓存(L2 Cache)。下面是一段从What Every Programmer Should Know About Memory中摘录的解释:

Soon after the introduction of the cache the system got more complicated. The speed difference between the cache and the main memory increased again, to a point that another level of cache was added, bigger and slower than the first-level cache. Only increasing the size of the first-level cache was not an option for economical reasons.

此外,又由于程序指令和程序数据的行为和热点分布差异很大,因此L1 Cache也被划分成L1i (i for instruction)和L1d (d for data)两种专门用途的缓存。 下面一张图可以看出各级缓存之间的响应时间差距,以及内存到底有多慢!

CPU包含多个核,每个核又有独自的一级缓存和二级缓存,各个核心之间共享三级缓存,并统一通过总线与内存进行交互。

Cache Line

整个Cache被分成多个Line,每个Line通常是32byte或64byte。
Cache Line是Cache和内存交换数据的最小单位。

每个Cache Line包含三个部分:

  • Valid:当前缓存是否有效
  • Tag:对应的内存地址
  • Block:缓存数据

了解Cache Line的概念对我们程序猿有什么帮助? 我们来看下面这个C语言中常用的循环优化例子 下面两段代码中,第一段代码在C语言中总是比第二段代码的执行速度要快。具体的原因相信你仔细阅读了Cache Line的介绍后就很容易理解了。

1
2
3
4
5
6
7
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
int num;
//code
arr[i][j] = num;
}
}
1
2
3
4
5
6
7
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
int num;
//code
arr[j][i] = num;
}
}

CPU Cache 是如何存放数据的

假设我们有一块4MB的区域用于缓存,每个缓存对象的唯一标识是它所在的物理内存地址。每个缓存对象大小是64Bytes,所有可以被缓存对象的大小总和(即物理内存总大小)为4GB。那么我们该如何设计这个缓存?

Fully Associative(全关联映射)

Fully Associative 字面意思是全关联。在CPU Cache中的含义是:如果在一个Cache集内,任何一个内存地址的数据可以被缓存在任何一个Cache Line里,那么我们成这个cache是Fully Associative。从定义中我们可以得出这样的结论:给到一个内存地址,要知道他是否存在于Cache中,需要遍历所有Cache Line并比较缓存内容的内存地址。而Cache的本意就是为了在尽可能少得CPU Cycle内取到数据。那么想要设计一个快速的Fully Associative的Cache几乎是不可能的。

直接映射

和Fully Associative完全相反,使用Direct Mapped模式的Cache给定一个内存地址,就唯一确定了一条Cache Line。设计复杂度低且速度快。那么为什么Cache不使用这种模式呢?直接映射方式的缺点是不够灵活,因每个主存只能固定地对应某个缓存快,即使缓存内还空着许多位置也不能占用,使缓存的存储空间得不到充分的利用。此外,如果程序恰好重复要访问对应同一缓存位置的不同主存块,就要不停地进行替换,从而降低命中率。

组相连映射

为了避免以上两种设计模式的缺陷,N-Way Set Associative缓存就出现了。他的原理是把一个缓存按照N个Cache Line作为一组(set),缓存按组划为等分。这样一个64位系统的内存地址在4MB二级缓存中就划成了三个部分(见下图),低位6个bit表示在Cache Line中的偏移量,中间12bit表示Cache组号(set index),剩余的高位46bit就是内存地址的唯一id。这样的设计相较前两种设计有以下两点好处:(16路组相连)

  • 给定一个内存地址可以唯一对应一个set,对于set中只需遍历16个元素就可以确定对象是否在缓存中(Full Associative中比较次数随内存大小线性增加)
  • 每2^18(512K)*64=32M的连续热点数据才会导致一个set内的conflict(Direct Mapped中512K的连续热点数据就会出现conflict)

替换策略

随机

随机确定要替换的块

先进先出

选择最先调入的块进行替换

LRU(最近最少使用)

根据块的使用情况,选择最近最少使用的块进行替换,反映了程序的局部性规律

写模式

Write-through(直写模式)

在数据更新时,同时写入缓存Cache和后端存储(如下一级cache或者内存)。此模式的优点是操作简单;缺点是因为数据修改需要同时写入存储,数据写入速度较慢。

Write-back(回写模式)

在数据更新时只写入缓存Cache。只在数据被替换出缓存时,被修改的缓存数据才会被写到后端存储。此模式的优点是数据写入速度快,因为不需要写存储;缺点是一旦更新后的数据未被写入存储时出现系统掉电的情况,数据将无法找回。


参考资料:

  1. 关于CPU Cache – 程序猿需要知道的那些事
  2. CPU Cache结构
  3. 《计算机组成原理》(第2版) 唐朔飞 编著
  4. Cache写机制:Write-through与Write-back
  5. 7个示例科普CPU CACHE
文章目录
  1. 1. 为什么要有CPU Cache
  2. 2. 为什么要有多级CPU Cache
  3. 3. Cache Line
  4. 4. CPU Cache 是如何存放数据的
    1. 4.1. Fully Associative(全关联映射)
    2. 4.2. 直接映射
    3. 4.3. 组相连映射
  5. 5. 替换策略
    1. 5.1. 随机
    2. 5.2. 先进先出
    3. 5.3. LRU(最近最少使用)
  6. 6. 写模式
    1. 6.1. Write-through(直写模式)
    2. 6.2. Write-back(回写模式)