《Computer Achitecture A Quantitative Approach》读书笔记
Chapter 1 - Fundamentals of Quantitative Design and Analysis
一些物理/工艺相关的知识
- Trends in Technology
- CPU 的片上缓存是<10ns级别的，而主存DRAM是数十ns级别的，网络接口是微秒级别的，而磁盘则是毫秒级别的，因此一次 cache miss 就对应几十个甚至上百个周期的停滞。
- Trends in Power and Enenergy
- TDP 是 Thermal Design Power 的缩写，不代表峰值功耗（可能为1.5倍TDP），也不是平均功耗（通常低于TDP），而是给予散热系统的指导数据。
- CMOS 工艺芯片的主要功耗来自于晶体管状态的翻转，\(P_{dynamic} \propto fCV^{2}\)，\(f\)是时钟频率，\(C\)是电容，\(V\)是电压，而 CPU 的时钟频率又往往与电压成正比，动态的功耗可能与电压呈三次方的线性关系。另一方面，随着晶体管数量的增加，静态的功耗也成为了较大的开销部分，即使晶体管没有翻转，仍然有电流通过，\(P_{static}=IV\)。因此电源管理系统甚至直接关闭掉某一个区域的电源以节约功耗。
- Trends in Cost
- 圆晶（wafer）是由硅单质生长出来的，受限于工艺为圆形，按照面积大小切割为 die ，圆晶上会有随机分布的缺陷存在，再结合数字电路的复杂度形成工艺良率。工业中往往会对 memory 进行冗余设计，即通过冗余的 cell 单元来避免良率带来的影响。芯片在切割后还要经过测试、封装、封装后测试等步骤，这都给芯片制造添加了额外的成本。
Appendix B - Review of Memory Hierarchy
Introduction
在评判存储体系设计时，考虑基础的单发射处理器模型，影响的指标有命中率、未命中惩罚和访存指令占比，三者综合可以计算出存储体系对于处理器性能的影响，进而评价其设计的好坏。但是随着现代处理器体系结构的发展，越来越多的因素需要被一并考虑进来：
命中率基于数据统计，表示存储体系在面对随机访问时的命中概率，比较直观的定义是访存指令命中的概率，即命中次数除以执行的访存指令数量。但是在现代处理器中，投机执行策略可能会发射不会被提交的错误指令，错误的访存指令是否命中符合命中率的定义，然而却不直接影响性能。因此严格来说，从性能的角度考虑，应该使用命中次数除以实际提交的指令数量作为命中率，更能反应出存储体系设计对于性能的影响。同时，这也启发了进一步的设计思考：错误发射的访存指令是否应该影响存储体系的状态？
未命中惩罚通常是基于多级Cache的延迟计算得出，进一步引出的思考是为什么往往采用串行方式逐级查询？在L1命中率较高的情况下，广播查询并设计逐级匹配的逻辑电路在功耗、性能上是不划算的。再继续考虑延迟的计算，在非阻塞缓存设计下，失配的查询会被暂存以继续提供服务，那么延迟代价就存在合并的可能性，在某个时间多条失配地址被一起发送到下级缓存查询。从准确的角度考虑，以硬件设计得到的失配延迟来计算是不准确的，需要根据实际数据对平均未命中惩罚进行计算。缓存、甚至是核内LSU的策略设计和微架构设计都会造成影响。
访存指令占比则与指令集设计、编译器优化强相关，反而是与硬件设计技术无关。
在了解一个未知的存储体系设计时，可以通过四个问题入手：block placement, block identification, block replacement, write strategy，这四个问题涵盖了大部分可能出现的情况，以基础的cache结构为例：
block placement：描述数据如何确定放置的位置，也就是定位cache line。最简单的cache结构是direct mapped，根据数据地址的low bit写入相应的cache line。进一步的有set associative（组相连），每一个set里面可以含有k个cache line，就是k-路组相连，表示每一个block按照low bit放入对应的set中，可能有k个位置。全相连则表示任何block都可以放在任何位置。在真实世界中，较多使用的是2-way和4-way组相连。
block identification：描述如何确认cache line存储的就是要寻找的数据。low bit作block offset，用于在cache line内截取需要的数据，其余继续划分low bit作(set)index，剩下的为tag，比较的时候按照index定位set，再逐一比较tag。这里还要确认一下用于寻址的地址是physical还是virtual，转换的过程在哪里进行。在传统面试的计算题中，cache size描述的是配套的RAM的大小，所有其他信息都不包含在范围之内，用它除以cache line大小就可以算出cache line数目，再进一步根据组相连情况划分。
block replacement：描述如何寻找换出的block。常见的思路有伪随机，LRU，FIFO，通常来说LRU表现效果最好，在硬件上通常使用Pseudo-LRU实现方式：
树伪LRU：维护二叉树，每一个非叶子结点具有1bit，表示最近一次使用的cahce line位于左侧还是右侧，在每一个access过程更新路径上的bit，需要替换时按照指示即可寻找LRU近似，时间复杂度O(logN)。
单位伪LRU：每个cache line一个bit，表示最近是否被访问过，当一次access后cache line中所有的bit都为1了，则重置这次访问以外的所有bit，需要替换时在bit为0的cache line中使用伪随机寻找，时间复杂度O(1)。
write strategy：描述写入数据如何处理cache和low-level memory的关系。由于写的占比小于读，因此对于读的优化很重要，在读的过程中可以同时取数据和比较tag，在写的过程中CPU不需要等待操作完成。按照同步性可以分为两种：
write-through & no write-allocate：写入数据时同时修改cache和low-level memory的状态，当发生write miss时只修改low-level的数据。这样做的好处是不需要考虑多级存储之间的数据一致性问题，便于其他核心/设备读取。
write-back & write-allocate：写数据只修改在cache中，通过dirty bit记录状态，当数据换出cache时同步修改到low-level memory，当发生write miss时只影响cache内。这样做的好处是可以利用空间局部性减少miss，可以通过write buffer减少存储间通信的代价，并且统一了read miss & write miss的行为模型，但是需要考虑多核情况下一致性的维护。一般来说还有一个优化，当发生read miss时，low-level memory的数据可以优先传递需要的8 byte数据，尽量减少CPU等待时间，再传输cache line中的其他数据。
通常来说，cache会被划分为Icache和Dcache，其中Icache的miss率可以做到很低，这样划分后相比于unified cache在小规模上可以去的更低的失配率。