(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111358078.7 (22)申请日 2021.11.16 (71)申请人 中国科学院上海高等研究院 地址 201210 上海市浦东 新区张江高科技 园区海科路9 9号 (72)发明人 王玉庆　杨秋松　李明树　 (74)专利代理 机构 上海智信专利代理有限公司 31002 代理人 杨怡清 (51)Int.Cl. G06F 12/02(2006.01) G06F 9/30(2006.01) G06N 20/00(2019.01) G06F 12/0862(2016.01) (54)发明名称 一种基于指令流和访存模式学习的缓存替 换系统及方法 (57)摘要 本发明提供一种基于指令流和访存模式学 习的缓存替换系统， 包括分支预测模块， 其对指 令流进行预测并写入取指地址队列； 访存指令记 录模块， 其依次记录已经提交的访存指令的信息 并写入到其访存指令缓冲中； 同时查询得到访存 指令序列； 访存模式学习模块， 其将访存指令序 列记录在其访存历史缓冲中， 据此对访存模式进 行学习， 随后预测访存指令的访存物理地址并写 入访存地址队列； 缓存替换决策模块， 其接收缓 存替换候选项的物理地址并用其检索取指地址 队列或访存地址队列， 根据得到的重用距离选择 一个缓存替换候选项作为踢出项反馈给一级缓 存。 本发明还提供相应的方法。 本发明的缓存替 换系统能避免乱序执行和缓存预取的干扰， 提高 访存序列预测的准确性。 权利要求书3页 说明书16页 附图6页 CN 113986774 A 2022.01.28 CN 113986774 A 1.一种基于指令流和访存模式学习的缓存替换系统， 其特征在于， 包括分支预测模块、 取指地址队列、 访存指令记录模块、 访存模式学习模块、 访存地址队列和缓存替换决策模 块； 所述分支预测模块设置为采用提前预测技术， 对目标程序的指令流进行预测并将预测 结果写入取指地址队列中； 所述访存指令记录模块设置为依次记录已经提交的访存指令的信 息， 将这些访存指令 的信息写入到其访存指令缓冲中； 同时， 每当取指地址队列写入新的条目项时， 用该条目项 所对应的指令块的起始 地址查询所述访 存指令缓冲， 以通过查询尝试得到访存指 令序列并 将其输出至访存指令学习模块和访存地址队列； 所述访存模式学习模块设置为将访存指令序列记录在其访存历史缓冲中， 根据访存历 史缓冲中保存的历史信息对访 存指令的访存模式进行学习， 并根据学习到的访 存模式来预 测访存指令序列中每条访存指令的访存物理地址并写入访存地址队列； 所述缓存替换 决策模块设置为接收一级缓存发出的所有缓存替换候选项的物 理地址， 使用这些物理地址检索所述取指地址队列或访 存地址队列， 得到每个缓存替换候选项的重 用距离， 根据重用距离 选择一个缓存替换候选项作为踢出项反馈给一级缓存。 2.根据权利要求1所述的基于指令流和访存模式学习的缓存替换系统， 其特征在于， 所 述分支预测模块设置为将预测结果以指令块为粒度写入取指地址队列中； 且所述分支预测 模块设置为执 行： 步骤A1： 在每个周期， 将当前预测地址所在的指令块作为当前指令块， 将当前预测地址 作为当前指令块的预测起始 地址； 根据当前指 令块的预测起始 地址确定从当前指 令块开始 的固定预测窗口； 步骤A2： 在获得当前指令块的预测起始地址后， 在当前指令块中对分支指令进行检索 和预测， 以判断当前指令块是否命中跳转的分支指令； 步骤A3： 根据判断结果， 若当前指令块未命中跳转的分支指令， 说明当前指令块中没有 分支指令或者识别到的分支指 令均未跳转， 则将当前指令块的信息作为分支预测模块的预 测结果写入取指地址队列； 随后， 确定下一指 令块的预测起始 地址， 并将下一指 令块作为新 的当前指 令块， 并回到步骤A2， 直到 当前指令块为固定预测窗口中的最后一个指 令块， 此时 当前预测地址根据固定预测窗口中的指令块的个数自增， 以进入下一个周期； 否则， 从命中的跳转的分支指令 中选择线性地址最小的第 一个跳转的分支指令作为当 前指令块的结尾地址， 将当前指令块的信息作为预测结果写入取指地址队列， 同时将当前 预测地址更新 为第一个跳转的分支指令的跳转 地址， 以进入下一个周期 或者， 所述分支预测模块设置为将预测结果以指令块为粒度写入取指地址队列中； 且 所述分支预测模块设置为执 行如下步骤： 步骤A1’： 在每个周期， 将当前预测地址所在的指令块作为当前指令块， 将当前预测地 址作为当前指令块的预测起始地址； 随后， 根据当前指令块的预测起始地址确定从当前指 令块开始的固定预测窗口中的所有指令块的预测起始地址； 步骤A2’： 根据各个指令块的预测起始地址， 在各个指令块中对分支指令进行检索和预 测， 以判断各个指令块是否命中跳转的分支指令； 步骤A3’： 根据判断结果， 若所有指令块均未命中跳转的分支指令， 则将所有指令块的权　利　要　求　书 1/3 页 2 CN 113986774 A 2信息作为分支预测模块的预测结果依次写入取指地址队列； 当前预测地址根据固定预测窗 口中的指令块的个数自增， 以进入下一个周期； 否则， 若存在至少一个指令块命中至少一个跳转的分支指令， 则从命中的跳转的分支 指令中选择线性地址最小的第一个跳转的分支指 令作为当前指 令块的结尾地址， 将当前指 令块及其前面的所有指 令块的信息作为预测结果写入取指地址队列， 同时将当前预测地址 更新为第一个跳转的分支指令的跳转 地址， 以进入下一个周期。 3.根据权利要求2所述的基于指令流和访存模式学习的缓存替换系统， 其特征在于， 指 令块的信息包括指令块的行线性 地址、 行物理地址、 起始偏移、 结束偏移以及跳转 位； 在将指令块的信 息写入取指地址队列时， 将指令块的预测起始地址拆分为高位的行线 性地址和低位的起始偏移， 并通过行线性地址查询TLB得到行物理地址， 并将得到的行线性 地址、 行物理地址和起始偏移写入取指地址队列的条目项中的对应域； 此外， 如果指 令块命 中的跳转的分支指 令， 则第一个跳转的分支指 令的末尾字节偏移作为结束偏移写入取指地 址队列； 否则， 取指地址队列中的结束偏移设置为6 3。 4.根据权利要求1所述的基于指令流和访存模式学习的缓存替换系统， 其特征在于， 所 述取指地址队列每一条目项的结构为： <valid,line_addr,phys_ad dr,begin_offset,end_of fset,taken>， 其中， valid表示有效位； line_addr表示行线性地址； phys_addr表示行物理地址； begin_offset表示起始偏移； end_of fset表示结束偏移； taken表示跳转 位； 所述取指地址队列还设有提交指针， 读指针和写指针； 取指地址队列的提交指针指向 下一个将提交的指 令所在的指 令块在取指地址队列中的条目项； 取指地址队列的读指 针指 向下一个将读取的指 令所在的指令块在取指地址队列中的条目项； 取指地址队列的写指 针 指向分支预测模块下一次写入的位置； 在处理器的主流水线刷新 发生后， 根据刷新类型， 取 指地址队列的读指针和写指针回滚到分支刷新的位置或者 提交指针的位置； 所述访存指令缓冲的每一个表项的结构为： <LineAddr,PhyAd dr,InstType,Memlen>， 其中， LineAddr表示访存指令的指令线性地址； PhyAddr表示访存指令在上一次执行时 的访存物理地址； InstType表明访存指令的类型， InstType∈{DirectInst , InDirectInst}， 其中DirectInst表示直接访存指令， InDirectInst表示间接访存指令； Memlen表明访存指令的访存长度； 所述访存历史缓冲是一个由访存指令的PC作为索引的阵列， 访存历史缓冲中的每一个 表项都记录有同一访存指令过去12次的访存物理地址； 且所述访存地址队列中每一条目项的结构为： <valid,inst_line_addr,mem_phys_ad dr,memlen,i nst_queue_i ndex>， 其中， valid表示有效位； inst_line_addr表示指令线性地址； mem_phys_addr表示访存 物理地址； memlen表示访存长度； i nst_queue_i ndex表示取指地址队列索引； 所述访存地址队列具有提交指针、 读指针和写指针； 在主流水线发生分支刷新时， 访存 地址队列的读指针和写指针回滚到分支刷新的位置 。 5.根据权利要求4所述的基于指令流和访存模式学习的缓存替换系统， 其特征在于， 所 述分支预测模块设置为： 若取指地址队列写满则暂停预测过程； 取指地址队列是否写满根权　利　要　求　书 2/3 页 3 CN 113986774 A 3