Computer Architecture: Memory Hierarchy

开始之前

既然 Load/Store 都写完了，就来讲讲 Memory 吧！

相信看到这边的读者在学校都有学过或者接触过计算机相关知识，
课堂描述的角度不一定适合每个人，
网路上很多不同角度切入的文章也很值得参考，
例如这次参加铁人赛的 ycliang 发的系列文，
可以看到从 OS 角度的切入实际应用案例，
看完之後回头看教材会更容易理解。

毕业之後断断续续的有看过很多公开课程，
猴子推荐 Onur Mutlu 教授的频道，
我当时是看 CMU 时期的版本，因为疫情的关系，这阵子有上传很多较近期的课程。
Onur Mutlu 在卡内基美隆大学(CMU)和苏黎世理工大学(ETH Zürich)任教，
内容清晰而且会带入很多实际的案例以及参考文献。
课堂中也有很多很棒的观念提点，
例如在问同学怎麽做决定的时候，就会说他很喜欢的答案叫做"It depands."，
引导同学更进一步描述情境。
或者在讲架构的时候会提到它很喜欢的想法"Do other things."，
分别对应到 CPU 乱序执行的相依性分析，找出等待时可以先做的指令，
以及 GPU 因为运算量够多，用 fine-grained MT 的方式重叠等待时间等等。

除了上面的 Onur Mutlu 教授之外，还要推荐 Georgia Tech - HPCA 课程，
特色是会把很多题目和运作行为用短影片的方式一步一步带着做，
观念的部分我会看 Onur Mutlu 教授，如果是某一部份看不懂就会来这边查。

记忆体

好了，现在终於来进入正题了，
对大部分的使用者来说，就是一个可以存取的位置。
但是实际上分很多类，
例如 ROM、SRAM、DRAM、Flash、XPoint等等技术，
其中依照断电後资料是否还在分为 Volitile 和 Non-volitile 等。

嵌入式系统中会需要修改 Linker Script 让资料放在特定位置，
也有研究者在研究怎麽有效率的使用这些特殊记忆体，
例如国立中正大学的罗习五教授之前在 Facebook 也有提及相关研究。

记忆体特性

最常见的 DRAM 来说，存取步骤有：

• decode row
• drive bit line
• amplify row data
• decode column address & select subset of row
  也可以拆下自己电脑研究一下记忆体时序，上面有标示每个步骤需要的时间，
  通常也会有 Row Cache，让下次存取不需要再经过前三个步骤。
  另外 jserv 也有提过因为 DRAM 平常就要定时充电的特性，
  有研究者在研究怎麽减少这部分的影响，
  细部可以参考 Onur Mutlu 的课程

记忆体存取特性

因为软件对记忆体的使用上有特定的规律，
通常会有下面两个现象：

• Spatial Locality：存取过的位置附近通常会是下一个存取目标，例如 Array。
• Temporal Locality：存取过的位置通常最近会再存取第二次

针对一些软件也有特殊的规律，
例如：为了不要让 OS 从记忆体被 Swap Out 到硬碟里，Linux 可以把特定记忆体 pin 住、
又或者有些特殊的资料要常常存取，可以手动搬到特殊的记忆体位置等等。

Memory Hierarchy

Fast、Cheap、Large Capacity 是我们对记忆体的理想条件，
但是根本不可能同时达成。
为了让记忆体满足又大又快又便宜的特性，
我们利用上面提到的特性把记忆体分成多个阶层，
就像我们家里面会把在用的拿在手上，常用的东西放在手边，
不常用的放在仓库，想买但暂时不会用到的放在虾皮购物车然後就会手滑。
记忆体也会这样分层：

• Register
• Cache
• Memory
• Disk

Cache

收纳类的书籍都会这样说：
只留最重要的东西在桌上。

依照存取特性通常分成两大类：

• Manualy：就是手动管理，例如 Tightly-Coupled Memory (ARM TCM)
• Automatically：硬体支援自动管理，是最常提到的 Cache 这个考试会考要背起来。

自动管理的 Cache 就是针对上面提到的两个 Locality 特性设计的，
但因为指令和资料的存取特性不一样，
比较贵的处理器还会分成 I-Cache 和 D-Cache。

既然是桌子和仓库之间，资料有事没事就会搬进搬出，
就要规划怎麽使用桌上的空间啦！
目前常见空间设计通常都介於 Direct map 和 Fully Set Associative 之间，
N-Way Set Associative 是在 Conflice 和 Access time 取的平衡的设计，

有了桌面空间规画之後，桌上都是空空的，
东西找不到(Cache Miss)就要进仓库拿，
但是进仓库又很花时间，这时候研究规律就很重要：
Cache 里又叫做 3C (Capacity Miss, Compulsory Miss, Conflict Miss)
Conflict Miss 发生之後，又分成不同的置换方式 (Random, LRU)
也会因为存取特性设计 Prefatch (另一种形式的 Implice Memory Access)

另外资料管理又分成几个类型，物品的故事掰不下去了就直接写特性：

• Write-back vs Write-Through：写入当下更新全部资料，
  或者等被置换掉才写回去上一层
• Write-allocate vs Write-around：写入 Miss 时会放一份在 Cache 里，
  或者直接写回去上一层(通常是 Memory)

Multi-Processor

在多处理器共用同一块 Memory 的情况下又比上面更复杂了，
会在 Cache 发生类似 Data Racing 的情况，这时候就需要有仲裁者来管理。
於是伟大的 Bus Snooping Protocal 就出现了！
计算机组织最常介绍的就是 MESI 模型：

• Modify(M)：被改过了，如果原本资料是 Shared 就要做一些处理(例如清除其他 Cache 的资料)
• Exclusive(E)：资料只有我有，写入的资料被置换掉的时候再写回去就好
• Shared(S)：有多份资料在不同 Cache 里
• Invalid(I)：这个 Cache Line 位置是空的，可以直接覆写资料。

在实际运作的时候也可能有一个 CPU 一直写入，但其他CPU只是读取，
结果一直清除(evict)其他 Cache 的情况，
例如 LL-SC 在抢 Lock 的时候，这种情况称为 False Sharing。

Virtual Memory

从古早时期记忆体就是重要的储存单位，
但 Compile 後，执行档中用到的相对位置和绝对位置都会固定下来，
於是不管有没有用到，每个 Subroutine(Function) 都会被放在 Memory 上。

为了减少占用的的记忆体空间，於是 Overlay 就出现了，
简单来说就是可以把某段程序从记忆体里面拿出来，搬到指定的位置取代掉原本的，
这时候就可以在执行 A 工作的时候 Load A 的相关函式，
执行 B 工作的时候 Load B 的相关函式，
再也不用同时把 A 和 B 的所有资料都放在记忆体上了。
但是在使用上有点麻烦，以前用的时候都要先执行 Load Overlay X 的函式，
用到的时候才 Load 对执行速度上也会有影响。

而 Memory Management Unit(MMU) 可以说是 Overlay 的加强版，
让硬体支援相关操作，使用时只要把虚拟记忆体映射表填好就可以，
如果遇到 Page Fault 就把资料从硬碟搬上来，再更新映射表就好罗！

讲到 MMU 就得要说到 Virtual Memory 了，
Segmentation 和 Page Mapping 让我们从 External Fragmentation 的地狱中解放出来，
但是又带进 Internal Fragmentation 的问题，
如果需要使用更小的区块该怎麽办？
总不能 new 一个 10 byte 的物件就给我 4K 的记忆体吧！

这时候 Slab Allocator 就出现了，
让我们能把记忆体区块又继续往下拆分。
於是小镇村又恢复了和平...。

不过问题还不只这些，有了虚拟记忆体映射代表 Cache 又有问题了，
如果要存取一个 Virtual Memory Address，到底要直接告诉 Cache (VIVT)呢？
还是要先问 MMU 再给 Cache (PIPT)呢？ 还是两个都问(VIPT)呢？
细部的说明可以请大家参考 ycliang 的这篇文章

另外 MMU 去 Memory 查表也很花时间，
还要准备一个 Translation Lookaside Buffer(TLB) 来加速这个过程。

结语

总之记忆体的问题很长很复杂，
单处理器还有很多细节没有函盖到，
多处理器中的 UMA、NUMA 又是另外的问题了。
虽然对感兴趣但是一直都没有时间研究，
也不是今天看得完的，
就先这样吧，搭晚安！