Day.8 Cache 的基本原理

为甚麽我们需要 Cache?

在思考为甚麽需要 Cache 之前，先思考程序是如何运行起来的 ?

我们知道程序是因运行在 RAM 之中，当我们需要运行一个 process 时，首先会从磁盘设备中将可执行的程序Load到主记忆体中，然後开始执行，然後如有需要计算，则我们必须透过在CUP内部的通用暂存器，在写回我们的主记忆体。

但在现实中，CUP的通用暂存器与记忆体之间有很大的速度落差(将近百倍)，因此CUP必须等待记忆体的时间，因此，我们有一种折中的方法，那就是制作一个速度极快的同时又容量极小的存储设备，其成本也不会太高。这块存储设备我们称作 Cache Memory。

CPU cache 是用於减少处理器存取记忆体所需平均时间的机制

Cache hierarchy

现代的电脑，引入了多层级的快取机制(Cache hierarchy)，可以看到快取记忆体从 L1 的速度 1.1ns 到 L3 的 12.8ns，都是为了让系统性能提升。

图片连结

多层级的Cache之间如何运作?

CPU要访问的资料在cache中有缓存，称为"命中" (hit)，反之则称为"缺失" (miss)，电脑会从L1 cache 到 L4 cache 查询是否命中，如果都缺失(Miss)，就必须从主记忆体中Load资料，在多层级的Cache之间工作不须保证某一地址的资料缓存只会存在於多层级 Cache 其中之一。

快取记忆体的设计方式

Cache 的组成

在现代大多数的处理器中，Cache 的大小称为 Cache Size，代表cache 可以缓存的最大数据的大小，Cache被分成很多行 (Cache Line)，Cache Line 大小不一，从16Byte 到 128Byte不等。

举一个例子：我们共有８行的cache line，cache line 的 size 为 8 Bytes，所以我们可以利用 3 bits 来循址 8 bytes 中的某一字节，我们称这个部分 bits 的组合为 offset， 8 行的cache line，同理需要 3 bits 查找某一行，这部分称之为 index，我们又引入tag array区域，tag array和data array一一对应。每一个cache line都对应唯一一个tag，tag中保存的是整个地址位宽去除index和offset使用的bit剩余部分，所以，当我们根据地址中index位找到cache line後，取出当前cache line对应的tag，然後和地址中的tag进行比较，如果相等，这说明cache命中。如果不相等，说明当前cache line存储的是其他地址的数据，这就是cache缺失

快取记忆体有三种对映机制

• 直接对映式 Direct Mapped
  • 直接对映可以理解为每个地址都可以立刻直接且只能映射到某个Cache Line上，有那些坏处呢？那就是Cache Miss率极高，因为数据的相关性和局限性，当两个变数映射到同一个 cache line 时，他们会不停地把对方替换出去。
• 完全关联式 Fully Associative
  • 完全关联就是所有Cache Line 可以对映所有的记忆体地址，可以减少大量的 Cache Miss，但是查询Cache是否命中的代价(Over Head)很高，必须遍历整个Cache。
• N路集合关联式 n-way associative
  • 直接对映式和完全关联式寻找平衡所提出的方法，n-way的意思就是将 Cache分成 N 组，每一组对映一个记忆体地址，对於 组中只需遍历组中每个元素就可以确定对象是否在快取中。

三种对映机制详细说明 Cache的基本原理

参考资料

现代处理器设计: Cache 原理和实际影响
Cache的基本原理
Cache是怎么组织和工作的？