返回地址预测方法、返回地址栈、分支预测单元及处理器与流程

摘要: 本发明涉及高性能处理器设计领域,具体涉及一种返回地址预测方法、返回地址栈、分支预测单元及处理器。背景技术:1、在高性能乱序处理器中,分支预测单元(branchp...
返回地址预测方法、返回地址栈、分支预测单元及处理器与流程

本发明涉及高性能处理器设计领域,具体涉及一种返回地址预测方法、返回地址栈、分支预测单元及处理器。

背景技术:

1、在高性能乱序处理器中,分支预测单元(branch predicating unit,bpu)的预测精度直接决定了前端取指效率和整体指令吞吐率。返回地址栈(return address stack,ras)作为分支预测单元中专用于预测函数返回指令目标地址的组件,用于预测调用指令和返回指令的目标地址。返回地址栈的预测准确率对包含大量函数调用的工作负载有显著影响。

2、现有的返回地址栈采用固定深度的lifo(后进先出)硬件栈,典型深度为16~64个数据项,每数据项存储一个完整的虚拟返回地址。当程序中出现深层递归调用时,例如快速排序、归并排序、编译器递归下降解析、json/xml递归解析等常见算法和应用场景,函数调用深度可能超过返回地址栈的物理容量。一旦栈溢出,最早压入的返回地址被覆盖,后续所有对应的返回指令将全部预测失败。每次返回误预测将严重影响处理器的执行性能。

3、部分现有技术在地址返回栈的栈顶对连续相同地址进行计数合并,从而减少递归调用对于地址返回栈容量的挑战。但是,这类现有技术对单路递归有一定效果,但对快速排序等多路递归(多个不同返回地址交替出现)无效。

技术实现思路

1、有鉴于此,本发明实施例提供一种返回地址预测方法、返回地址栈、分支预测单元及处理器,期望减少递归调用场景下对地址返回栈容量的挑战,能够高效处理大量重复的返回地址,使得地址存储消耗在一定程度上与调用次数解耦。

2、第一方面,提供一种返回地址预测方法,所述方法包括:

3、接收调用指令的关联地址,所述关联地址为所述调用指令的目标指令地址或目标返回地址;

4、根据所述关联地址,在地址缓冲器中查询匹配的地址存储结构索引,所述地址缓冲器用于存储返回地址查询信息和对应的地址存储结构索引;

5、响应于查询命中,根据命中的地址存储结构索引获取对应的历史返回地址,所述地址存储结构用于存储返回地址;

6、响应于所述历史返回地址与目标返回地址相同,根据所述计数器存储结构的尾部数据项的状态更新所述计数器存储结构的数据项,所述计数器存储结构的数据项用于存储地址存储结构索引和对应的压缩计数器值;

7、响应于接收到返回地址预测请求,读取所述计数器存储结构的尾部数据项;

8、根据尾部数据项的地址存储结构索引,在所述地址存储结构读取对应的返回地址作为预测返回地址输出;

9、根据所述尾部数据项的压缩计数器值,更新所述计数器存储结构的数据项。

10、第二方面,提供一种返回地址栈,所述返回地址栈包括:

11、地址缓冲器,用于存储返回地址查询信息和对应的地址存储结构索引;

12、地址存储结构,地址存储结构的数据项用于存储返回地址;

13、计数器存储结构,所述计数器存储结构的数据项用于存储地址存储结构索引和对应的压缩计数器值;

14、控制寄存器,用于存储地址存储结构写索引、计数器存储结构写索引、计数器存储结构的尾部数据项索引以及尾部数据项的压缩计数器值,其中,所述地址存储结构通过地址存储结构写索引指示新的数据项的写入位置;所述计数器存储结构通过计数器存储结构写索引指示新的数据项的写入位置,通过尾部数据项索引记录尾部数据项的位置;

15、控制逻辑电路,被配置为实现如第一方面所述方法的控制步骤。

16、第三方面,提供一种分支预测单元,所述分支预测单元包括如第二方面所述的返回地址栈。

17、第四方面,提供一种处理器,包括如第三方面所述的分支预测单元。

18、本发明实施例通过地址缓冲器对调用指令的关联地址进行匹配,命中时复用地址存储结构中已有数据项而不重复写入,使得地址存储消耗从与调用次数成正比降至与不同返回地址数量成正比,解决了返回地址栈因每次调用均完整存储地址而导致的存储冗余问题。同时,本发明实施例的技术方案与所述地址存储结构数据项对应设置计数器存储结构,并在计数器存储结构的每个数据项中设置压缩计数器,连续相同地址调用时仅递增计数器而不分配新数据项,返回时若计数器大于初始值则仅递减而不回退,将递归下降阶段的序列追踪消耗从o(d)压缩至o(1),有效预测深度从数十层提升至上千层,解决了返回地址栈在递归深度超过物理容量时发生栈溢出而导致误预测的问题。

19、本发明实施例通过地址缓冲器的全局匹配,能够识别任意位置重复出现的返回地址而非仅限于栈顶相邻比较,计数器存储结构中各数据项独立记录连续相同调用次数,使得多路递归场景的存储效率同样得到保障。

20、在一个改进实现方式中,本实施例通过在每个推测分支预测点仅保存若干指针和当前尾部数据项的压缩计数器值作为检查点信息,地址缓冲器不参与检查点,而以一致性验证处理过期映射,恢复操作在单周期内即可完成,解决了现有技术方案在乱序推测执行时因保存完整栈内容或维护影子栈而导致检查点开销大的问题。

1.一种返回地址预测方法,其特征在于,所述方法包括:

2.根据权利要求1所述的方法,其特征在于,所述方法还包括:

3.根据权利要求1所述的方法,其特征在于,根据所述计数器存储结构的尾部数据项的状态更新所述计数器存储结构,包括:

4.根据权利要求3所述的方法,其特征在于,根据所述尾部数据项的压缩计数器值,更新所述计数器存储结构包括:

5.根据权利要求4所述的方法,其特征在于,所述计数器存储结构为链表,所述链表的数据项包括前一数据项索引、地址存储结构索引和对应的压缩计数器值;所述链表通过计数器存储结构写索引指示新的数据项的写入位置,通过尾部数据项索引记录尾部数据项的位置;

6.根据权利要求1所述的方法,其特征在于,所述地址存储结构通过地址存储结构写索引指示新的数据项的写入位置;所述计数器存储结构通过计数器存储结构写索引指示新的数据项的写入位置,通过尾部数据项索引记录尾部数据项的位置;

7.根据权利要求6所述的方法,其特征在于,所述地址存储结构为环形存储结构,所述地址存储结构通过第一代龄标记指示循环存储状态;

8.根据权利要求7所述的方法,其特征在于,所述计数器存储结构和所述地址存储结构具有不同数量的数据项。

9.根据权利要求1所述的方法,其特征在于,所述关联地址为目标返回地址,所述返回地址查询信息为返回地址的低k位,所述在地址缓冲器中查询匹配的地址存储结构索引具体为:根据目标返回地址的低k位与所述返回地址查询信息进行匹配,以查询匹配的地址存储结构索引;

10.根据权利要求1所述的方法,其特征在于,所述计数器存储结构为堆栈存储结构,所述堆栈存储结构的数据项包括地址存储结构索引和对应的压缩计数器值。

11.一种返回地址栈,其特征在于,所述返回地址栈包括:

12.根据权利要求11所述的返回地址栈,其特征在于,所述控制寄存器还用于存储所述地址缓冲器写索引、第一代龄标记和第二代龄标记。

13.一种分支预测单元,其特征在于,所述分支预测单元包括如权利要求11所述的返回地址栈。

14.一种处理器,其特征在于,包括如权利要求13所述的分支预测单元。