cache – 主存的地址映射和替换算法

---

映射(3)

1.直接映射

• 原理
  
• 主存块以cache长度分区,映射时cache缓存块仅接受各区中相对应的块号,tag仅需保存t位区号
• eg: cache[0] 中仅可以存放 主存[0,2^c,2^c+1,3*2^c…]
• 每个缓存块i(cache) 可以和 若干个主存块对应
• 每个主存块j只能和 一个 缓存块(cache)对应
• 地址块号直接与cache对应块标记内区号对比,仅比较t位,加速查找(m mod 2^c [tag]==t ?)
• 但cache的利用率可能很低,冲突概率也很大(0区0块与n区0块互相冲突)

---

2.全相联映射

• 原理
  
• cache利用率提高(只要cache有空闲,即可调入)
• 查找困难,对应给定主存块add,需与所有的cache块比较tag(全相联位置任意)
• 比较长度较长(m位):由于任意映射,tag中同时保存块号和区号共 m=t+c 位

---

3.组相联映射

• 原理 (直接与全相联的折中)

• 将cache 均匀 分组,每组中缓存块数 若干(eg:共Q组,每组两块)

• cache被分了多少组,主存储即被分成多少个区

• 某一主存块 j 按模Q映射到缓存
  的第 i 组 的任一块

• 不同组(区) 直接映射,组内全相联映射
  
  

• 结构复杂度可以接受,cache利用率较高,冲突少

• 特别的:
  若每组仅含一块缓存块 --> 直接映射
  若总共一组 --> 全相联映射

---

在多层次cache结构中应用范围

1. 靠近CPU --> 高速 --> 直接映射 / 路数 少的组相联映射

2. 中间层次 --> 路数 适中的组相联(eg:2/4/8路组相联)
3. 距离CPU远的cache层次–>对速度要求较低但对利用率要求较高 -->全相联映射

---

替换算法 ¹

• 置换时选择哪一块缓存块退出cache用以装入新块

algorithm(2)

1. FIFO(先进先出算法) :无法很好的体现程序 局部性原理²
2. LRU(近期最少使用算法):将最近的情况视为将来的可能情况,较好的体现了程序局部性原理

---

思考

1. 是否Cache越大，计算机效率越高？Cache的大小与哪些因素有关？³
2. Pentium 4中为什么设置L1，L2，L3三级Cache？L1 cache分成I-cache和D-cache有什么好处?⁴
3. 单体多字系统中存储器的字结构中位的数量与存储器带宽的关系
   由于程序和数据在存储体内是连续存放的，因此CPU访存取出的信息也是连续的，如果可以在一个存取周期内，从同一地址取出多条指令，然后再逐条将指令传 送至CPU执行。按照课本上4.41（P103）中的结构，存储器中每字是W位，请讨论：是不是W的数量越大，主存的带宽就越大？⁵

---

1. 详见操作系统 ↩︎

2. 时间局部性原理：如果某个数据或指令被使用，那么不久将可能再被使用
   空间局部性原理：如果某个数据或指令被使用，那么附近数据或指令也可能被使用
   利用这种特性，将被访问的程序及其附近的程序调入cache中，可减少访问主存的次数 ↩︎

3. • 答案: 否,效率与cache的命中率相关,当命中率小于100%时,cache扩容提高命中率进而提高效率,当命中率达到100%时,相当于cache速度级主存,此时制约效率的并非cache容量.
   2. cache大小因素:子块个数,子块长
   ↩︎
4. 1. 设置多级cache的原因: 进一步提升命中率, 弥补cpu时钟周期和内存周期之间的差距, 同时也权衡了成本和效率
   2. L1 cache分为i-cache和d-cache的优点: 减少访问数据和指令的cache冲突
   ↩︎

5. 存疑

   • 存储器带宽: 与存取周期密切相关，表示单位时间内存储器存取的信息量。
   • 提高带宽: 缩短存取周期 / 增加存储器字长 / 增加存储体。
   • 存储器字长(即W)的数量越大，一次访存取出的数据越多，主存的带宽就越大。但是主存带宽增大不一定会使CPU效率更高，因为当程序中遇到转移指令时，后面连续取出的指令就失效了。
   ↩︎