Perceptron Learning for Reuse Prediction
Perceptron Learning for Reuse Prediction
-
论文的主要贡献:
- 通过结合多种特征作为输入,感知器学习可以大大的改善 cache block reuse预测
- 基于感知器的预测结果可以用于帮助cache的replacement和bypass优化
- 基于感知器学习的cache管理策略会比更大一倍的基于LRU的cache 更高效
-
感知器学习在微体系结构中的应用:
- 最早的感知器学习被提出应用于预测条件分支指令。根据分支指令的PC值通过hash后索引得到权重向量,然后通过和分支历史纪录进行点积,得到预测结果。如果结果不小于0,则认为该分支应该发生跳转,否则不跳转。权重的更新规则:如果预测错误或者点积结果没有超过阈值,则权重相应的减少或者增加
- 之后这类工作主要是:通过使用分支指令的历史位在权重表中生成索引,而不是作为点积计算的输入,改进了操作的延迟
-
传统的基于PC的block reuse预测器和基于感知器的预测器的不同
-
预测器选择的特征:
- the trace of memory access instruction(PCs):从block放入cache之后开始,到block被替换出cache之后的纪录。使用时不再放在一起使用,而是分开每一个PC单独使用
- the PC of the memory instruction
- bits from the memory address:地址中的page number或者是tag
- a compressed representation of 数据。block中的数据如果类似,行为可能也会类似
- time/reference count。block被访问的次数。可能一个block每次访问固定次数后就不会再被访问
-
预测器的主要思想:
- 每个特征用于索引不同的表,每个表的表项都是一个饱和计数器,之后累加在一起。如果累加结果超过某个阈值,则预测block不会被使用
- 感知器的更新规则:如果预测不正确,或者累加和没有超过某个数量级,权重会减少/增加在block访问/替换的情况下
- 通过加权求和来组合特征,能够避免由于将特征组合而带来的破坏性干扰和索引膨胀
-
利用采样器的感知器训练
- 采样器是一个单独的数组,包含少量的采样的cache sets。这些cache sets从LLC中选择得到。采样器中cache set中的表项的组成:
- 部分tag域,用于标识block,不需要完全准确的标注
- 一个小的整数sum,用于标识最近计算得到的预测值
- 一个由特征hash之后的值组成的序列,用于索引预测表。特征首先要hash,然后和该block的最后一个存储访问指令的PC的低位进行异或
- LRU bits,用于采样器的替换策略
- 如果LLC中的某个被采样的cache set被访问,此时相应的采样器中的该cache set也会被访问。在采样器中,通过比对部分的tag来找到block,如果未发现,此时需要使用LRU策略,将新的tag放入采样器。
- 如果利用tag,在采样器中找到了block,此时认为是命中,感知器需要根据特征来训练感知器纪录这次hit
- 如果一个表项从采样器中被替换出去,则之前对该block的访问指令被认为是其最后一次访问,此时也要训练感知器
- 采样器是一个单独的数组,包含少量的采样的cache sets。这些cache sets从LLC中选择得到。采样器中cache set中的表项的组成:
-
从内存访问中提取特征到进行预测的数据通路
-
预测过程:
- 当一个存储器操作到达LLC,预测器开始判断当前访问的block是否将会被重用
- 当一个block准备放入LLC中时,预测器会判断这个block未来是否会用,如果预测为不会被再次用到,会使用bypass直接将数据传递给core
-
预测器的训练过程
- When there is a replacement in the sampler :当采样器发生miss时,采样器中的某一个block将要被替换出去,意味着这个block看起来不会在被使用,此时需要据此进行训练。如果block的sum值小于阈值或者是预测不对,此时特征对应的tables的entry需要增加
- When a sampled entry is accessed :当采样器发生hit时,此时意味着block将会被reuse。此时如果sum大于阈值,特征对应的tables entry就需要减少
-
论文选择的特征(六个):
- (PCi代表着最近第i次访问LLC的存储指令的PC值,PC0代表当前正在访问的指令的PC)
- PCi右移两位,i=0
- 三个PCi,每个PCi向右移动i位,i为1到3
- 当前block的tag值,右移4位
- 当前block的tag值,右移7位