lab3 Paper Summary
由于CPU执行速率远高于访存速率，一次Load/Store指令就可能会让CPU暂停数百个时钟周期，导致CPU性能下降。在现代处理器中，我们使用多级缓存缓解了这个问题。然而，当Cache Miss时，CPU仍需要到内存中取出相应的数据。所以，我们提出了Cache Prefetcher来降低Cache Miss的可能性。
1 Background
受限于L1D Cache的资源与带宽限制，我们的Prefetcher需要有尽可能小的内存开销和尽可能高的准确率。在过去的研究中，我们发现Delta Prefetcher在这类任务中表现不错。Delta Prefetcher是一类基于当前访存地址和之前的访存地址之差来进行预取的Prefethcer。
文章中提出了几种Delta Prefetcher的设计：
1 SandBox Prefetcher：其定义了一种训练delta的流程来进行预取，是最早的Delta Prefetcher。
2 The Best-offset Prefetcher(BOP)：在SandBox Prefetcher的的delta训练流程上基础上考虑了时间因素
3 Multi-lookahead offset Prefetcher(MLOP)：研究者观察到很多时间上并不有效的预取仍是准确的，于是在BOP的基础上训练 global delta，也就是不考虑时间因素，在整个程序执行过程中都进行训练的全局delta来进行预取
4 Berti_DPC3:使用bit vector来记录内存访存特征，但是对于跨页访问或者交错访问存在缺陷。
5 Berti：在Berti_DPC3的基础上不仅记录每个Page的访存模式，还记录发出访存指令的PC的访存模式，达到了Delta Prefetcher的SOTA水平
文章中介绍了考虑时间因素的Delta训练过程：
左图：
设置一个RR (Recent Request) Table，记录一定长度的曾经进行过预取的地址，并人为设置好一些待选的Delta，将其放入Delta List中，当下一个访存指令到达时，用该访存地址分别减去Delta List中的Delta，并判断相减结果是否在RR table中，如果在RR table中，则增加相应的delta的可信度。
这个训练过程假定了同一个基地址对于不同地址的预取延迟时相同的，实际上，这个假设并不一定正确，同时，其预先定义的Delta List也限制了其性能。
右图：
记录发生Cache Miss的时间，当该地址被填入Cahce时，根据填入和Miss之间的延迟latency，从发生Cache Miss的时间往前找，找到满足延迟的最近的访存地址。根据地址之差更新对应地址的Delta。
这个训练方法提出了更合理的一种假设：即从Miss到被填入Cache之间的延迟与从发出预取指令到被填入Cache之间的延迟相同。
文章考虑到我们仍有多种可以用于Delta训练的上下文没有使用（如Page，offset等），于是文章使用多种上下文的排列组合和右图的训练方法构建出Prefetcher，对其性能表现进行了实验。
2 Designs
在PC、Page、offset、和global四种上下文的排列组合中。文章发现使用PC+Page是最有效的一种方式，同时具有较高的accuracy和coverage，之所以只采用两种上下文进行排列组合是因为使用更多的种类提升不明显，同时还会产生更多的内存开销。
Hyperion的具体机制设计如下：
1、Latency计算问题
文章在MSHR和PQ中开辟了16bit的位置分别用于存储timestamp。并在Cache中开辟了12bit的位置用于存储latency
demand miss发生的timestamp被记录在MSHR中，当对应Cacheline被填充时，Cache会用现在的timestamp减去MSHR中保存的timestamp计算出latency保存在Cache中。
随后Cache会立刻使用指令的PC、地址、latency按照训练方法更新History Table和Delta Table。
L1D中存储的latency会在第一次预取的Cacheline第一次hit时被读取，此时Cache会再次仿照上述步骤更新HistroyTable和DeltaTable
2、History和Delta记录问题
对于PC和Page分别以PC本身和VPN为索引，设立History和Delta两类表，根据Background中提出的训练方法进行delta训练。
并设立一个Prefetch Queue存储预取请求。
然而，这种设计对于内存的开销太大，文章通过一些方法解决了内存资源有限的问题：
1、History Table内存开销问题
文章相继提出了DiGHB和aDiGHB进行内存开销减小
DiGHB中GHB由一个循环链表构成，每个数据单元存储着对应指令的PC、访存地址、Timestamp和两个next指针，两个指针分别指向PC相同的下一个访存记录和addr相同的下一个访存记录。同时我们再设置两个“起点索引表” PCiT和VPNiT，分别指向对应的PC和VPN在GHB中“最早的”记录，也就是由next指针链接起来的链表的头部。
查找时通过index Table找到链表头部，再通过next指针遍历，插入时则将记录放到链表的头部，更新index Table即可。如果GHB满时，我们会使用被替换出的记录的PC和addr从index Table中找到对应链表的头部，遍历链表删除对应记录。
aDiGHB则进一步优化了GHB中存储的冗余PC，因为GHB中的PC仅仅会在发生eviction时使用，所以，我们删除GHB中的PC，而是新增一个iPCT表，表中维护了GHB中最早的访问记录（也就是会在FIFO时会被evict的记录）的index对应的PC。
在entry数较少时，两个分离的表性能表现更好，内存占用也更小，但是entry数一旦增大，DiGHB和aDiGHB就会体现出优势，其内存占用随entry数增大增长的更慢
2、Delta Table的内存占用问题
为了能把PC的Delta Table和VPN的Delta Table放入一张表，并避免其中的记录被PC和VPN相互evict，Hyperion使用缓存分割技术来实现这一点，如分别给PC和VPN分配M和N sets（M+N为一个周期），则我们可以通过以下公式变换其index：
来确保其落在对应的索引范围内，即可将PC和Page的记录放在一张表中。
3、Prefetch Buffer
由于PQ和MSHR的大小是有限的，不可能所有被选入的prefetch指令都能够被顺利执行，所以，当PQ满时，更多的prefetch请求被放入到Prefetch Buffer中。
当demand hit，并且是非预取指令命中时，如果PQ不满，再从Prefetch Buffer中取出指令进行预取。
现在，我们可以具体来看Hyperion的训练过程：
总共分为四种情况。
情形一：起始于一个demand miss或prefetch miss，如果是prefetch miss，则把PQ中记录的timestamp传入MSHR中，如果是demand miss，则把当前的timestamp传入MSHR中。待后续取用。
情形二：起始于内存的Cacheline被填入，此时Hyperion会根据当前的timestamp和MSHR中记录的timestamp计算latency，如果不是prefetch fill，是demand fill的话则会根据latency更新Histroy Table与Delta Table，并进行预取
情形三：起始于预取的Cacheline命中，会根据Cache中记录的latency和当前的timestamp重新更新Delta Table，并进行预取。
情形四：起始于非预取命中，此时会从PQ或者PB中取出prefetch指令并进行预取。
具体的预取策略为：
从对应的PC和Page的Delta Table中取出置信度最高的12个Delta，把对应的Prefetch指令放到PQ或者PB中。若L1D的实时预取准确率低于0.6，则会将所有的预取指令全部放入L2C中。否则就正常进行指令的issue。
PS：这里的Delta训练方法有多种，论文中表述并不是很清楚，个人根据文章后续的描述认为论文中的训练方法应该为训练方法1。
训练方法1：
在每次训练时，在History Table中找到所有符合 条件的记录，并计算出这些记录的Delta，将其 Local Counter 加一。与此同时 Total Counter 也只加一，也就是说，Total Counter记录的是训练次数。
在这种训练方法下，大部分Delta能够得到大于 的结果，这与文章中所设置的参数相同。同时，这种训练方法也符合文章中 的设计。
训练方法2：
这种训练方法是教学网上所发的Lab说明中提到的训练方法，相比训练方法1，每次训练时只选出所有符合条件的Delta中，绝对值最小的Delta，将其 Local Counter 加一，同时 Total Counter也加一。
在这种训练方法下，Total Counter是所有Local Counter之和，因此，仅可能有一个 Delta 取得大于 0.5 的 confidence，所以我们需要将 相应调小，并调大 ，在这种设计下，两种训练方法能够大致得到统一。