cache原理以及相关计算

一、cache存在的意义

介绍cache之前, 大家需要先知道局部性原理:

局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。

• 时间局部性（Temporal Locality）：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。
  程序循环、堆栈等是产生时间局部性的原因
• 空间局部性（Spatial Locality）：在最近的将来将用到的信息很可能与正在使用的信息在空间地址上是临近的。
• 顺序局部性（Order Locality）：在典型程序中，除转移类指令外，大部分指令是顺序进行的。顺序执行和非顺序执行的比例大致是5:1。此外，对大型数组访问也是顺序的。
  指令的顺序执行、数组的连续存放等是产生顺序局部性的原因

因此, 既然CPU对于Main Memory中不论是数据(data
)还是指令(instruction)的访问都是趋于集中的, 那么我们是不是可以开辟另外一个区域来存放这些连续的内容呢?

于是cache就诞生了, 暂存可能要访问的内容, 从而能够快速访问局部内容, 大大提高访问速度.

CPU对于存储访问的分层: Cache<–>Main Memory<–>External Memory

二、cache的特点

• 位于普通主内存和CPU之间
• 可能位于CPU芯片或模块上
• 与主内存的大小相比，Cache相对较小
• 运行速度接近处理器
• 和主存比非常贵
• 存储的是主存中一部分内容的 副本(copy)

三、cache中存储的内容

Cache将Memory中的一个Block(由K个字构成)作为一个Line来存储, 一个Line中的内容和对应的Block内容是一样的.

每个Line中都有几位的内容来标记其对应的Block号, 称之为Tag位, 存在开头的位置.

每个Block对应着K个Word(s), 因此需要logK(向上取整)位来标记一个字存在Block中的位置.

四、cache的命中率

通过命中率 (hit ratio) 来衡量
命中率 = (cache命中的次数)/(cache命中的次数 + 访问memory的次数)

五、cache的性能度量

从命中率计算公式可以看出, 如果一个cache的Line数越大、命中率越高, 那么理论上来说效果就越好, 但是cache的尺寸变大也会带来其他问题

• 小尺寸
  – 便宜：缓存的价格接近主内存的价格
  – 命中率低，访问速度可能比访问主内存慢
• 大尺寸
  – 命中率高：接近100%，访问速度可能接近缓存访问
  – 非常昂贵
  – 需要更多的门来实现, 比小cache来得慢
  – CPU占用面积更大

因此, 需要对容量、价格、速度进行权衡.

六、cache的映射方式

典型的有三种: 直接映射(direct mapping)、关联映射(associate mapping)、集合关联映射(set associative mapping)

1.直接关联映射

主存中每个块, 都分配到了一个特定的line上.

那么最终要查询的字, 对应的字地址是:

Line位标识: 处在哪一个line号
Tag位标识: 在对应的line的号下, 对应的block号是多少
Word位标识: 在对应的block号下, 对应的字号是多少

直接映射cache组织方式图

总结:

• 优点: 设计简单、易于实现
• 缺点: 对应关系固化, 所以有可能出现颠簸

2.关联映射

特殊情况: 全关联映射(Fully Associative Mapping)

一个主存块可以被存放到任何一个line中.
Tag 唯一标识内存块
每一个Line的Tag都要被检查是否匹配

总结:

• pros: 降低了颠簸出现的频率
• cons: 需要大量的比较, 即在设计上需要并联比较电路, 因此很昂贵复杂

3.集合关联映射

集合关联映射是前两者的结合, 通过增加set(集合)给line进行分组; 每个block号对于set号先进行直接关联; 再通过全关联的方式, 在set中寻找一个Line放置数据.

集合关联映射例题:

Suppose a computer, its main memory is 4MB，Cache’s capacity is 16KB，block size is 8 words，word length is 32bit，addressed by word, please design a cache organization of 4-way set associative mapping, require:

1. draw the structure of main memory address and mark the bits of each segment；
2. initially, Cache is empty，CPU fetches 100 words from memory unit0, unit1, … unit99 in sequence, repeat this sequence 8 times. How much is the hit rate of Cache ？
3. if the speed of cache is 6 time that of main memory, introducing cache, how many times is the speed of CPU accessing memory improved？

解题思路:
(1)
首先: 计算机按字寻址, 那么计算机为每个字分配地址, 即字地址需要: 4MB/32bit = 1M = 2^20, 需要20字地址位.
其次: 主存中是按照块存储的, 一个块有8个字, 因此需要log(8)=3位来确定字相对于块的位置, 所以word位为3位.
再者: 要把所有的块通过direct mapping的方式放入set, 而set包含4个line, 本题中已经给出了cache的存储大小, 直接算出line位: 16KB/(8*32bit) 为9位, 其中line存储结构与block存储结构完全相同, 9位再分成set后, 即除4后, 得到set位为7位.
最后: tag位长 = 总地址长 - set位长 - word位长

综上: Tag位 10位, Set位7位, Word位2位.

(2)
Cache向CPU传输是按字传输, 而主存向Cache传输是按照Block传输, 考虑到题目中所需要的内存单元是连续存储。
那么CPU拿unit0的时候, cache中会先未命中一次, 此时Cache会从主存那里拿一个block的数据, 也就是unit0~unit7, 一共八个字, 随后CPU拿unit1时, 在cache中就命中了。
同时, Cache的容量能够放的下这100个词, 因此, 第一轮CPU拿完之后, 100个字全在Cache中存有了, 随后的所有CPU拿数据, Cache都会命中.
综上: Cache未命中次数为100/8 向下取整 +1 = 13次, 其他全部命中, 命中率为(800-13)/800 约等于 98%
(3)
假设访问一次Cache需要时间t, 那么访问内存时间为6t
根据第二问命中率算出效率优化了:
6t/(98%*t+2%*7t)=5.3倍

七、Cache替换算法

(1)直接关联映射情况下

直接替换, 因为没得选, 只能替换固定对应的那个line

(2)关联映射情况下

• 硬件实现算法
• 最近最少使用（LRU）
• 先进先出（FIFO) —— 替换cache中待了最长的block
• 最不常用(Least frequently used) —— 替换命中最少的block
• 随机：性能几乎与LRU相同

八、Cache 写操作

与读不同，缓存写入更为复杂, 因为需要保持缓存、内存和其他缓存之间的数据一致性.

两种通常用于单CPU系统的高速缓存写入策略：

• 写直达 write through:

所有的写操作直接进入内存和cache

缺点:

1. 大量的写入流量，可能会导致总线瓶颈
2. 降低了写入的速度。

• 写回 write back写回：

不仅写缓存，还将修改标志放在写入的行中，当该行被替换时，将该行写回内存。
适用于迭代操作和I/O模块直接连接到缓存的系统

缺点：

1. 内存中的部分内容无效
2. 电路很复杂
3. 缓存可能成为瓶颈

• 缓存一致性方法—多CPU

1. 写直达总线监控
   高速缓存控制器监视地址行，如果某个位置写入共享内存，而数据在缓存中，则使缓存项无效。
2. 硬透明
   使用额外的硬件。当一个缓存写入内存时，其他缓存中的相应项也会更新
3. non-cache 内存
   许多CPU共享一剂主内存，共享的内容从不复制到缓存中