cache地址映射，全相连、直接、组相联

高速缓存存储器的地址映射

• 信息在主存和Cache中，确定它们的对应关系就需要借助地址映射。
• 地址映射的定义：
  • 主存地址按某种规律（函数）映射到cache中。
• 当cpu访问存储器时，它发出的内存会自动变换为cache地址。
• 实现：采用硬件，很快。而且编程人员不会感到Cache的存在。这种特性也称为cache的透明性。
• 主要地址映射方式：
  1. 全相联方式
  2. 直接方式
  3. 组相联方式

几个概念

• “行的概念“”： Cache的数据块称为”行”，用L_i表示。
• “块”： 主存的数据称为“块”，用B_j来表示 （每个数据块和cache的行的大小完全一样， 而且每个块或行都是由若干个连续的字组成的）。

一、全相连映射方式：

一、映射关系

• 主存中任意一个块可以映射到cache中的任意一行中。需要在cache中的一行增加标记部分，存放该行内容的主存块的块号。
• 二、主存与cache地址格式
  
• 将CPU发出的内存地址的块号部分与cache所有行的标记进行比较 ，如果有相同的，则cache命中了。如果找不到，则没命中。
• 与主存中某块的标记相同，则表示cache命中了。

三、优缺点

• 灵活性好
  • Cache中只要有空行，就可以调入所需的主存数据块
• 利用效率不高
  • 因为存在了一个m位的标记位，使cache的行包含了一些对存储无用的信息。
• 速度太慢
  • 硬件成本高
  • 每次访问cache时，需将一个一个遍历并比较标记，才能判断所需主存的字块是否在cache中
• 因此全相联映射方式更适用于小容量的cache。（容量一大，所占位数就大，块内地址的位数不变，行内地址位数不变，那么行内标记的位数就更大了，利用率更不理想。）

五、例题！！！

1. cache的地址格式：
   • cache的容量是16KB，所以按字编码的话，cache的总线长度是14位。
   • 块（行）的大小是512B，也就是说块（行）内地址是9位。
   • 因此行标记 14-9=5位 ，也就是说cache一共有32行。
     
2. 主存的地址格式
   • 主存容量1MB，一共是20位。
   • 块的大小是9位，所以块标记公用11位。 一共2048块
     
     3.块表的容量
   • 根据行的数量和块标记的位数，可以得到块表的容量是 32*11位
   • 这个块表不包含地址部分，只有标记部分。块表中块的数量由cache行的数量决定。
     
     

二、直接映射方式：

一、简介:

• 一些约定的主存块只能复制到cache中的一个特定行中。
  • 如果cache中有m行（后面2^m指的也是行），则主存的第0块，第m块，第2m块，……，第2^s-m块只能映射到cache的第0行。（s是块标记个数，m是行数）
  • 主存的第1块，第m+1块，第2m+1块，……，第2^s-m+1块只能映射到cache的第1行。
    二、映射关系
    

三、主存地址格式

• 假设主存共2ⁿ个单元，分成2^s个块，每块单元数为2^w个，则主存地址为s+w位。（2^s^个块代表块标记数目，每块单元数2^w^代表块内地址位数）
• Cache空间被分成2^m^行，每行大小也应该为2^w单元，则Cache地址为m+w位。
  

块表的大小：

• 主存的（2^s/2^m）=2^s-m个块映射于Cache的同一行（块数除以行数）。也就是说块表一共可以有多少项，因此主存块数的标记位是s-m位。
• 块表的大小就是2^m*(s-m)位。

直接映射的优缺点：

• 优点： 硬件实现简单，成本低
• 缺点： 灵活性查。每个主存块只有一个固定的行可以存放。如果cache容量比较小，则非常容易发生冲突，效率大大降低。
• 适用：直接映射方式一般用于大容量的cache中。

例题

三、组相联映射方式

• 前面讲过全相连映射更适合小容量的cache，直接映射方式适合大容量的cache。而容量不大不小的cache更适用用组相联映射方式。
• 是全相联映射方式和直接映射方式的折中方案。它既有全相联映射的特点，又有直接映射的优点。
• 将cache的2^m行分成2^d组，每组有2^m-d行，每行的大小是2^b位。那么主存的第0块，第d块，第2d块，……，第2^s-d块可以映射到Cache的第0组的任意一一行。主存的第1块，第d+1块，第2d+1块，……，第2^s-d+1块可以映射到Cache的第1组的任意一 一行。也就是组间直接映射，组内全相联映射
  

检索过程：

• 拿到一个主存地址，先根据地址中的d位组号找到cache的相应组，然后将该组中所有行的标记部分与内存地址的高s-d位同时比较，判断是否命中。

特点

• 组内有一定的灵活性，而且因组内行数较少，比较的硬件电路比全相联方式简单些。而且空间利用率比直接映射方式要高。
• 组相联映射的每组的行数v一般取值较小，典型值位2，4,8,16。位强调比较器的规模和存放的灵活性，常称组相联为v路相联。

例题

1. 先分析主存地址 和 Cache地址的划分情况
   • 每个字块为8个字节，32位。所以每个块占5位。
   • 存储器2MB，所以存储器一共占21位。
   • 因此存储器地址可以划分为：16位块地址，5位块内地址。
   • 这里又说是采用字节编制方式，所以可以将块内地址再次细分。一个字32位，也就是说一个字是4个字节（32位系统），表示4个字节需要2位二进制数。因此存储器地址最终版是：16位块地址，3位块内字地址(一个块8个字)，2位字内字节地址。
   • Cache地址的划分与存储器完全一样，16KB就是14位，一个块5位。一个块8个字（3位），一个字4个字节（2位）。当然，这里应该说是行。
   • 所以Cache地址划分最终版是：9位行内地址，3位行内字地址，2位字内中的字节地址。