# Day 14 Cache and TLB Flushing Under Linux (Q&A - II)

今天来复习 cache 相关的知识！
首先可以参考一下这篇：Day.8 Cache 的基本原理

cache 相关计算

cache 是一个折衷的设计，存取速度比 RAM 快上一大截，比较接近 CPU 的运作速度，但是 size 没有 RAM 大，所以 cache 能够储存的资料量一定是 RAM 的子集，那麽要怎麽知道现在 CPU 要存取的资料有没有在 cache 中呢？
cache 的设计原理有点像是一个杂凑表(hash table)，取要存取位址的某些部份来做比对，很多资讯工程硕士班的入学考试，都会有相关的题目，笔者作为一个考试录取的硕士生，从来没有真正的理解这部分怎麽计算XDDDD
直到这次的整理，才大致上了解 cache 计算的细节，那我们就以考题为例，来复习一下 cache 的相关计算罗！

• 重点：
  • cache 的 hashing 方式是将要比对的位址，分成以下几个部分：

    [ tag | index | block or line offset | byte offset ]
    

    • 计算方法
      • byte offset：用来存取一个 word 里面的某个 byte，所以所需的 bit 数会是可以代表一个 word 里面可以存的 byte 数，通常 1 word == 4 byte 所以这个部分通常为 2 bit
      • block offset：用来存取 cache line 中的某个 word，所以由 cache line size(cache block size) 和 byte per word 来决定，举例 64 B 的 cache block size，4 byte per word，那 block offset 就是 4 bit (64/4 == 2^4)
      • index：用来存取某个 set，所以由 way 和 cache block entry 数目决定；若为 direct-mapped，表示有 cache block entry 这麽多个 set；若为 fully associative 则是只有 1 个 set (index bit 数目为零)；若是 n-way associative，则 set 数量 == (# of cache block entry / n)
      • tag：用来比对是否存在 cache 中的索引，bit 数量 == (# of bit representing the address space - # of bit for byte offset - # of bit for block offset - # of bit for index)
  • 题目通常会提类似 "64 KB资料量大小的 cache，<其他的一些条件>，请问 cache 的大小"
    • cache 是由 tag bit、valid bit 还有储存的资料量所组成，题目给的是储存的资料量，要来计算整个 cache 的大小
    • 题目若没有多加描述的话，全部都是 byte addressable (byte offset == 2 bit)

题目范例

题目	答案

cache & TLB: VIVT、VIPT、PIPT

从上面可以大致上理解，cache 比对的方式，那麽接下来记录的是 cache 比对方式的种类。
上个图：

TLB 的位置决定了 cache 比对的方式，最左边 PIPT(Physically Indexed, Physically Tagged)，中间 VIVT(Virtually Indexed, Virtually Tagged)，最右边 (Virtually Indexed, Physically Tagged)。

• VIVT：上述 cache 的相关计算都是用 VA 来算的
  • 优点：VA 一出 CPU 就直接可以去 cache 做比对，效率高
  • 缺点：会有 aliasing 问题(包含了 homonyms 和 synonyms)
    • homonyms：同一个 VA 对应到 2 个不同的 PA
    • synonyms：同一个 PA 对应到在 cache 中的 2 个 VA；对其中一个 VA 做修改，会导致两个 VA 的值有歧异的问题。
    • 解法： flush cache
• PIPT：上述 cache 的相关计算都是使用 PA 来计算
  • 优点：不会有 aliasing 问题
  • 缺点：要经过 TLB 转译後才会去比对 cache，若 TLB miss 会有极大的 latency
• VIPT： 则是两者的折衷， Index 部分可以直接到 cache 中做比较，而 tag 的部分则是要经过 TLB 做转换，换成 PA 之後才做比较
  • 优点：TLB 和 cache 的比对可以并行，且有机会避免 aliasing 问题，兼具 VIVT 与 PIPT 的部分好处
  • 缺点：还是有机会有 aliasing 问题 (synonyms)
    • 解法：cache coloring、设计支援 alias detection 的硬体、设计使 VIPT 表现得像是 PIPT

附录

图片来源

参考资料

• 题目来源 (大硕 计算机组织与结构 讲义)
  • Ptt Grad-ProbAsk1
  • Ptt Grad-ProbAsk2
• stackoverflow：Cache Addressing
• stackoverflow：Cache Addressing confusion
• CPU Cache 原理探讨
• 附录.B 记忆体架构复习
• Cache 原理和实际影响
• chapter 21 cache
• 深入理解cache对写好程序码至关重要
• L1 Cache architecture in ARM
• 如何计算 CPU Cache size?
• page coloring
• 图解| CPU-Cache
  以上资料都阅读过的话，相信对 cache 会有一定程度的了解的！
  今天复习了 cache 相关的计算和观念，也回答了部分自己在阅读这份文件的疑惑，明天来做些总结，就启程前往下篇文件吧！
  感谢各位，我们明天见！