4.9-Cache地址映射与变换方法

主存与Cache地址映射概念

1. 主存数据如何迁至Cache才能实现快速查找

　　2. 常见三种映射方法

1. 1. 全相联映射
   2. 直接相连映射
   3. 组相联映射

全相联工作原理

主存分块，Cache分行，两者大小相同

设主存分块，每块4个字，主存大小为1024个块，则第61个地址为00001111 01（块号 块内地址）

主存分块后地址就丛一维变成二维

映射算法：主存的数据块可映射到Cache任意行，同时将该数据块地址对应行的标记存储体中保存

全相连就是指主存的任意块可以映射到Cache的任意行上去，或者按照某种关联算法映射

CPU访问数据流程：

1. 首先主存和Cache的对应关系为主存将所有的标记和字都迁移到对应的Cache行中，标记（数据地址）保存在Tag中
2. Cpu访问数据的时候首先是根据标记先跟所有的Cache中的tag比较，如果命中则返回Cache行中的数据，如果没有命中则丛主存中取数据后保存在Cache行中
3. 同Cache行的比较是通过比较器进行比较的

举例：

1. 首先CPU要访问1F地址，首先将1F变成二进制tag和块内偏移地址
2. 然后将标记部分tag与所有相连存储器通过多路并发比较电路比较所有的tag
3. 由于第一次访问，没有命中，所以会访问主存，基于地址访问主存，将主存的数据搬迁到Cache中去，并保存有效位和标记位，同时有效位置为1

优缺点：Cache利用率高，块冲突低，淘汰算法复杂

应用场合：小容量的Cache

直接映射工作原理

• 主存分块，Cache分行，两者大小相同
• 主存分块后还将以Cache行数为标准进行区分
• 设每块4个字，主存大小为1024个字，Cache分为4行，第61个字的主存地址为（000011 11 01 区号 区内快号，块内地址）主存地址从一维变成3维
• 映射算法：Cache共n行，主存第j行块号映射到Cache行号为：I = j mod n
• 即主存的数据映射到Cache行的特定行（直接映射的由来）

1. 查找原理

• 首先将主存一一映射到Cache行中去，主存数据块包括标记，index行，数据，Cache行包括v， tage， 数据，index行对应的是Cache行的v，标记对应tag
• 查找数据的时候比较器比较的是index = v， 标记=tag来比较
• 如果命中返回CPU，如果不命中访问主存，并存放在Cache行中

举例：访问1F地址数据0000 111 11（tag， index， 偏移量）

• 由于第一次范文肯定不会命中，直接访问主存
• 将访问到的数据inded根据地址译码器翻译成区号放在有效位上，tag放在Cache行的tag上，数据放在数据块缓冲区
• 访问44的时候有效位和Tag已经被访问的20占据，那么就需要覆盖之前访问的20号地址

优缺点：Cache利用率低，块冲突高，淘汰算法简单

使用场合：大容量Cache

组相联映射

• 主存分块，Cache分行，两者大小相等
• Cache分组，每组中包含k行，本例假定k=4，每组包含行数相同
• 主存分块后还将以Cache组数为标准进行分组
• 假设每块4个字，主存大小为1024个字，Cache分为2组，第61个字为0000111 1 01（主存组号 Cache组号， 内块偏移地址）主存地址从一维变成三维
• 映射算法：Cache共n组，主存第j块号映射到Cache的组号为I = j mod n 即主存的数据映射到Cache特定组的任意行

查找原理

• 主存地址被划分为标记，组，字三个部分，对应的内存行为 tag， v 数据标记与tag对应，组与v对应，取数据时候通过比较器比较组号，和组号下面的全部tag对比数据
• 如果不命中则搬迁到Cache行中

举例：访问1F 00001 10 00 tag index 偏移地址

• 首先index地址通过组索引译码器翻译成对应的组号，然后多路并发比较器根据组号，tag同内存行中的组和tag进行比较，如果命中则返回CPU，如果没有命中则访问主存，将数据搬迁到对应的Cache行中去
• 如果迁移的时候某个组已经满了，那么就要根据调度算法覆盖其中的一行数据

优缺点：兼有全相联和直接映射的优缺点，都是介于两者之间。如果只有1组就是全相联，如果组和行相同就是直接映射

使用场合：使用中间大小的Cache使用