浅谈主存和Cache间的地址映射

最近在学计算机架构，正好学到主存与Cache间的地址映射，记录一下，方便以后复习回顾。

学一个东西要弄清楚这个东西有什么用，发明它的目的是什么。Cache和主存的地址映射则主要是为了加快CPU的处理速度，因为如果CPU每次都要从主存(如4GB)中找数据的话就太慢了，但是如果在Cache(如64K)中有对应主存的数据，这样就很快了。下面的地址映射方式都是想判断主存中某个数据在不在Cache中，只不过效率不同而已。

首先指明基础单位，简单来说，有4个基础单位：Bit，Byte，Block，Word
其中

Bit就是0/1二进制位
Byte = 8 Bits （4GB即4 Giga Bytes）
Block = 32 Bytes （根据情况而定，可能不一样）
Word = 64 Bits （根据操作系统位来定，大部分都是64位操作系统）

在主存和Cache间的地址映射过程中，都是使用Block作为基本单位来交换数据，因为这样更加高效

主存和Cache有三种地址映射方式

1. Fully Associative Mapping （全相联映射）
2. Direct Associative Mapping （直接相连映射）
3. Set Associative Mapping （组相连映射）

1. Fully Associative Mapping （全相联映射）

全相连映射大概如下图所示：

Fully Associative Mapping.png

Cache和Main Memory(MM)都被分为一定数量的Block，即图中的b(0), b(1), ...

由图可知，Cache被分为 C/B-1 个Block，Main Memory被分为 M/B-1 个Block （C是缓存大小，如64k=2^16 Bytes，同理B和M分别是Block和MM大小）

全相连映射方式比较简单，其思想是MM中的任意一个Block可以存在Cache中任意一个Block中，寻址方式如下图：

Fully Associative Address Transformation.png

1. MM Address，由MM中的Block序号(Block No.)和Block中的地址(得到byte或者bit)(Block Address)组成
2. Cache Address，也是由Block序号(Block No.)和Block中的地址(Block Address)组成
3. Directory Table(相联存储器，三种映射方式都有)，存着MM和Cache的映射关系，其中Effective Bit是判断该条映射是否有效

BTW：Associative Memory(相联存储器)的列数和Cache的列数一致

例题1：
Assume that cache capacity is 64KB in a computer system, data block size is 16 bytes, main memory capacity is 4MB, fully associative mapping is used.

Solution

2. Direct Associative Mapping （直接相连映射）

Direct Associative Mapping.png

直接相连映射与全相连映射的不同之处在于它将MM中的Block分成了一个个Area，每个Area的大小都和Cache相同，并且每个Area中的Block只能存在Cache中对应位置的Block，例如：MM中Area0的b(0)只能存在Cache中的b(0)，Area1的b(0)也只能存在Cache中的b(0)，以此类推。因此它也要求MM的大小必须是Cache大小的整数倍。

Direct Associative Address Transformation.png

Ei是Area编号，Bi是Area中的Block编号，bi是Cache中Block编号，Block Address是Block中的地址

首先，由Bi选出Directory Table中对应的Block，该Block存着Area编号，将这个编号和MM Address的Ei比较一下，相同的话就说明在Cache中找到了对应MM中的数据（Hit），然后直接把MM Address的Bi和Block Address当做Cache Address去Cache找。

例题2：
Assume that cache capacity is 64KB in a computer system, data block size is 16 bytes, main memory capacity is 4MB, direct associative mapping is used.

Solution

3. Set Associative Mapping （组相连映射）

Set Associative Mapping

组相连映射的思想相当于结合了前两种映射思想，在已经分好Area的基础上再进一步地分Group，每个Areaz里面有若干个Group，与直接相连映射不同的是，组相连映射要求的只是每个Group必须一一对应，而Group里面的Block则是随意对应(即全相连映射)

Set Associative Mapping Address Transformation

Gi是Group的编号，其余同直接相连映射
同理，先由Gi选出Directory Table中对应的Group，再把Ei和Bi与其内容作比较，相等就说明Cache中存在MM中的数据，然后直接把Directory Table中的bi和MM Address中的Gi当成Cache Address去Cache中找数据

例题3：
Assume that cache capacity is 32KB in a computer system, data block size is 64 bytes, main memory capacity is 1MB, set associative mapping is used and the group count is 128.

Solution

最后，总结一下三种映射方式，当组相连映射中的Group数量减少到1时，组相连映射变成全相连映射，当Group数量增加到Block总数时，组相连映射变成直接相连映射。