CS61C - 学习总结 1
Cache 缓存
为了解决内存空间大但访问慢的问题，设置缓存作为中间站。cpu 与 cache 的交流比内存要快的多。
缓存和内存都是随机访问存储器件，但是缓存是 SRAM，通过晶体管实现，不需要通电保持数据，每个比特需要大量晶体管来保持所以价格巨贵。相比之下内存是 DRAM，电容实现所以会不断发生漏电，需要隔一段时间通个电来刷新。简单而言是这样。
第一种：Direct-Mapped Cache 直接映射缓存
T - I-O：实际上是把内存地址分块，解决内存大缓存小，多对一映射的空间问题而存在。I 是 index，对应内存地址中间位，标记数据去往 cache 的哪一行，也就是哪一个块。o 是 offset 偏移量，因为缓存和内存之间是以块 Block 为交流单位，所以一个块中会对应多个存储位置。offset 确定了存放在哪个位置。缓存 T 是 tag，对应内存地址的高位，作为地址的标志符，验证所取到的内容是不是需要的。对于直接映射缓存，有：
$I = row = block/blocksize, O = blocksize$
课上的比喻很有意思：Baggage claim（行李领取处）。虽然所有飞机的行李都在同一个转盘（Index），但你需要通过行李牌（Tag）来区分哪个箱子是你的。
具体实现中，直接映射缓存是多对一的映射结构，即 index 相同的块对应缓存的同一位置，所以当现在需要检索的内存地址 tag 和 index 对应缓存的 tag 不一样时需要踢掉原来的。这也催生了 valid 位，有效位，用来标识缓存的这个 block 是否可用，是不是垃圾（和垃圾比 tag 有什么用），确保获得的内容准确性。
电路图看的明白一点。
Hit and Miss：
就是缓存命中和缓存未命中，Hit 就是所需地址就在缓存中且有效。缓存未命中则分很多种，compulsory miss 描述一个从未进入过缓存的块必然会发生的一次未命中，比如程序刚刚启动需要加载一车地址，而这些地址都不在缓存中。conflict miss 指的是除了 compulsory 之外，发生冲突的那些未命中。比如两个 tag 不同的块加载到同一个 index 下就会发生踢人事件。capacity miss 描述由缓存本身容量决定，不得不踢人，而不一定是发生矛盾（其实没有矛盾哪需要踢人。。。只是如果缓存大一点就不会发生矛盾）这种和直接映射缓存没关系了。还有一种在后面介绍。然后就有了命中率，AMAT 公式那些东西可以描述缓存的性能。
Write-back and Write-through：
写回和写穿透。区别在于写穿透是每次 cpu 修改了数据，会在缓存和内存都进行修改。这样做确保了内存里的数据每时每刻都是新的，但是对内存操作实在太慢，所以有了写回模式，即 cpu 只对缓存进行修改，暂时不动内存，而是把缓存中修改的那一块的脏位 dirty-bit 设置成 1，标识这个位置已经修改过了。那什么时候写回，这发生在脏块被踢走 eviction 的时候（这样就不得不改内存了吧）以及强制刷新。性能确实极大提升，但是带来缓存不一致的问题会导致多核心操纵内存时卡 bug，留到后面。不过，如果写的时候地址不在缓存中怎么办，还得分两种：Write-allocate 和 No-Write-allocate，写分配是从内存读数据到缓存再修改缓存，非写分配则绕过缓存直接改内存，这会让缓存中没有这个地址对应的块。还有个 Write-around 写绕，就是只写内存，挺捞的就不提了。
时间相关性和空间相关性：
缓存最精妙的思想，因为当我们读到一个地址，很有可能我们还会再用相同的地址；很有可能我们会用相邻的地址。既然有一个很可能下次还会再用的地址，那为什么不找个地方存起来，这就是缓存了啦；为了保证不用从内存中再拿相邻地址里的东西，就一次性拉一车地址过来，这就是 cache 是以 block 为单位的原因。缓存的性能提升都和这两个思想有关。
第二种：Fully-Associative Cache 全相联缓存
直接映射缓存不是经常发生踢人事件嘛，那就让 block 们之间不要冲突就好了，来一个 block 占一个位置，这样每个 block 都有位置可占，不会发生 conflict miss 了。
这样一来就没有 index 区段了（因为没有固定的映射关系了），也就是说 any block can go anywhere in the cache, and must compare with all tags in entire cache to see if data is there。写入时随便放，读取时并行检查每一行
这样当然好，前提是造起来不贵，当然没有这个前提。因为要给每行都做一个比较器，这个非常昂贵，所以全相联缓存基本只用在 TLB 上。
第三种：N-Way-Set-Associative-Cache 组相联缓存
那就折中一下，依然做映射，但是原本（直接映射）是一个 index 只能容纳一个块，现在扩充一下容错，让一个 index 容纳两个或更多的块，这样发生 conflict miss 就大大减少。同时，因为只要对每条路做比较器，硬件成本也可以接受了。
现在 index 指向的是一个 set 组，一个 set 里有多个 block。在这张模式图中看到相同的组用同种颜色标出了，这样相同 index 就能容错了。不过，在 block 总数相同的情况下这样分组到底有什么用，在平均随机的内存访问下确实性能和直接映射是基本相差不大的，因为这种情况最终大家都会被塞满，然后不断踢来踢去。不过现实中绝大部分都是具有空间相关性的访问。这样直接映射会有很多空位不能坐的情况，比如来回访问 AB 两个地址，直接访问就会打起乒乓，但组相联就可以把两个人一块存下来。
我很喜欢这张图。很明显的突出了组，块，路是什么。set 就是行，block 就是一个长方条，way 是大坨大坨垒起来的四个大块。同时体现了一个电路的常见模式：不管控制信号是什么先直接给出数据，这样省电路，也表现了 hit 所需的条件：有一个 tag 击中了而且不是垃圾位，这样依靠这个 tag 的信号控制选择器选择 data。
Block Tradeoff：
想到直接映射总是 conflict，那为什么不把每个 block 里的字节数做大一点，这样就能多容纳一点地址了啦，就减少 conflict 了啦。的确在一开始命中率确实会提升，利用了空间相关性，访问大数组的时候一个 block 就能存很多，不用开一个新 block 存了多好啊。但是太大的话，相同 block 总数情况下必然导致 index 减少（宽度增加行数减少），这会使得命中率降低，很容易打乒乓。而且这样未命中惩罚也很大，每次要搬一大堆数据从内存，说不定新开搬来的数据完全用不到，还会被新数据挤走，这就很捞。
也就是说要对 block 的大小做权衡。
最后讲到踢地址的几种方式，LRU，FIFO，RAND 等，以及多级缓存。多级架构实在是经典。为了弥补一个缓存的低效，用第二级缓存去保证第一级缓存 miss 了可以从第二级找数据用，免得去内存找。第二级缓存拥有第一级的所有数据，比第一级容量大但速度慢，相当于给第一级打个补丁接漏水的属于是。
写好累放个图奖励一下
