面向对称密码协处理器的轻量级分支预测技术研究*

吴朋庭，李 军，何卫国，梅 瑞

（成都三零嘉微电子有限公司，四川 成都 610041）

0 引言

随着云计算、大数据、5G以及高清视频业务等领域网络信息技术的快速发展，通信设备对密码处理单元的加解密性能提出了更高的要求。为了满足网络汇聚层、核心服务器对海量密码业务处理能力的需求，需要研究具有高性能的对称密码协处理器。

高性能的对称密码协处理器主要采用数据并行和指令流水的架构来提高运算并行度，采用流水线级数加深的策略来提高运算频率。理论上性能的提升应该与流水线级数加深程度成正比，然而实际情况并非如此。以简单的五级流水为例，其执行级处于流水线的第三级，当一条分支指令进入流水线时，处理器无法确定这条分支指令是否跳转。在分支预测器引入之前，流水线只能停止取指，等待这条分支指令的判断结果出来之后再继续执行，从而引入程序流控制开销[1]；并且随着流水线级数的增加，分支指令所产生的程序流控制开销还可能不断增大。因此，采用分支预测技术提前确定程序流的执行方向对提升协处理器的性能尤为重要[2]。

分支预测技术，就是在取指阶段对即将取出的指令是否为分支指令，并对其跳转方向和目标地址进行预测的技术，其本质是对程序运行行为的归纳总结和记录，是一种机器学习的过程[3]。由于预测并不等于真实情况，一旦预测失误即会引发流水线排空/冲刷（flush），从而降低流水线运行效率[4]。因此，研究如何提高分支预测的命中率成为了业界一直努力的方向。

在通用处理器领域，分支预测主要分为静态预测和动态预测两类。其中，静态预测机制的硬件开销较小，但是其命中率普遍不高；动态预测机制的命中率明显好于静态预测机制，但是其硬件开销较大，并且随着命中率的提升，硬件的开销几乎呈指数级增长[5]。对称密码协处理器是一种嵌入式微处理器，其硬件资源非常有限，因此需要一种不但硬件开销小而且预测命中率高的分支预测机制，以实现更高的性价比[6]。

本文结合对称密码算法实现特征，分析了静态分支预测的不足，设计了一种面向对称密码协处理器的轻量级分支预测器，在预测“跳转必然发生”的静态分支预测技术基础之上，通过增加分支条件学习器、记录指令跳转阈值的方式，以轻量级的硬件开销，将分支预测的平均命中率大幅提升，使其极限命中率与密码算法的循环轮数无关，同时降低了不同代码风格对分支预测命中率的影响。

1 对称密码算法实现的特征

对称密码算法主要包含分组、序列、杂凑算法，在算法编程实现时，普遍具有：①模式选择结构；②分组循环结构；③子程序调用和返回结构；④子程序轮循环结构；⑤尾包特别处理结构。对称密码协处理器设计了无条件跳转、条件跳转、模式跳转、数据结束跳转、尾数长度跳转、子程序调用/返回等分支指令来实现这些结构，其中：

（1）无条件跳转指令，主要用于分组循环，跳转必然发生；

（2）条件跳转指令，主要用于子程序循环体，跳转大概率发生；

（3）模式跳转指令，主要用于模式选择，算法模式不变时必然跳转；

（4）数据结束跳转指令，主要用于结束命令监测，仅数据结束时才跳转；

（5）尾数长度跳转指令，主要用于尾数处理，由于尾数长度随机可变，跳转概率是与尾数长度相关的函数；

（6）子程序调用/返回指令，主要用于子程序的调用和返回，跳转必然发生。

这些结构大部分属于必定跳转或者多次循环跳转结构，因此对称密码算法中的分支指令将会大概率执行跳转。针对这一算法特性，对称密码协处理器采用“预测跳转必定发生”的静态分支预测机制，就可以获得较高的预测命中率。

2 静态分支预测机制

“预测跳转必定发生”的静态分支预测机制，其原理是在PC值刚好更新后的时钟周期，根据PC值来预测该指令是否为分支指令，以及指令跳转的方向，并索引分支目标缓存（Branch Target Buffer，BTB）来预测跳转的目标地址。因此，m条分支指令总共需要m个BTB表项，以64条分支指令、24比特分支目标缓存为例，该机制仅需要192 B的CAM型存储器资源开销，具有硬件开销小、预测命中率较高的优点。

然而研究发现，这种静态分支预测机制虽然可将无条件分支指令的预测跳转命中率提升到较高水平，但对于条件分支指令来说，其命中率始终与算法轮函数执行的轮数以及算法实现的代码风格相关，预测命中率不稳定。

假设算法轮函数的执行轮数为N，理想情况下，除了第一个分组的第一次跳转和最后一次跳转不命中（命中次数为N-2），其余分组只有最后一次跳转不命中（命中次数为N-1），因此分支预测命中率的极限值为1-1/N，这意味着不同的算法如果有不同的循环轮数，那么就有不同的分支预测命中率；如果将目标设定为95%以上的极限命中率是可以接受的，那么至少需要循环轮数N≥20，很明显这个要求对于目前无论哪个领域的算法，都是大概率无法实现的。

此外，由于对称密码协处理器提供的分支指令比较丰富，实现算法轮函数循环体的编程方法也存在多样化的情况，例如一个轮数为10的简单循环体结构就可以使用加法、减法、条件跳转、无条件跳转指令的以下4种搭配来实现。

图1 实现轮函数的不同代码风格

对于（1）（2）代码风格来说，第一个分组的处理会触发两次预测失败，分别出现在第1次和最后1次执行循环体跳转指令时，之后每个分组都会触发1次预测失败。对于（3）（4）代码风格来说，第一个分组的处理会触发一次预测失败，出现在最后1次执行循环体跳转指令时，之后每个分组会触发N-1次预测失败。

显然，对于第（1）（2）种方式实现的循环体来说，采用“预测跳转必定发生”的静态分支预测，可以将条件跳转指令的分支预测命中率提升到90%；但对于第（3）（4）种方式来说，这种预测方式虽然使程序中的无条件跳转指令实现了100%的极限命中率，但是条件跳转指令的极限命中率仅能达到10%，这是难以接受的。

因此，需要对分支预测机制做进一步改进，使其命中率更高，并且与循环轮数无关，同时减小代码风格对预测命中率的影响。

3 改进分支预测机制

在通用处理器领域，一般采用两级动态分支预测机制来提高分支预测的命中率，其原理是使用第一级的分支历史寄存器（Branch History Register，BHR），记录每条分支指令最近的跳转执行情况，并根据其当前状态索引第二级的模式历史表（Pattern History Table，PHT）来预测分支指令是否跳转，最后索引分支目标地址缓存（Branch Target Buffer，BTB）来预测跳转目标地址。假设BHR的位宽为w，则PHT需要存储2w个表项，因此m条分支指令总共需要m个BHR、m×2w个PHT表项和m个BTB表项的硬件开销。

为了提高分支预测的命中率，往往需要更大的w取值，这导致硬件开销几乎呈指数级的增长。以64条分支指令、10比特历史寄存器为例，两级动态分支预测机制需要比静态分支预测机制多出大约80 kB的CAM型存储器资源开销。

图2 两级动态分支预测结构示意图[1]

对称密码协处理器是一种嵌入式微处理器，其硬件资源非常有限，无法提供如此大的存储器资源用作分支预测，因此需要一种不但硬件开销小，而且预测命中率高的分支预测机制来实现更高的性价比。进一步分析对称密码协处理器实现算法的指令集结构可以发现，其分支条件简单并且相对固定。此外，一旦某条分支指令执行过一次，其分支条件信息就可以被译码模块解析出来。基于该特征，本文在静态分支预测基础上提出基于分支条件学习的分支预测机制。

3.1 分支条件学习器

对于静态分支预测而言，无论采用哪种代码风格，当触发第1次分支预测失败时，分支预测器都会将跳转指令和目标指令的PC值记录到分支预测表中，用于后续基于PC的分支预测操作。由于初始的分支预测表中没有记录任何值，程序默认以PC指针递增的方式执行，因此第1次触发的必定是“该跳不跳”型的分支预测错误。

在这之后，分支预测器中已经记录了分支预测表项，当程序指针再次指向该指令时，跳转将必然发生。可以预见，当（1）（2）代码风格的循环结束时，或者（3）（4）代码风格执行后续循环时，都将触发“不该跳却跳”型的分支预测错误。因此，要想进一步提高分支预测命中率，就必须解决由“预测跳转必然发生”引起的“不该跳却跳”型的分支预测错误。

由于“不该跳却跳”型分支预测错误和“该跳不跳”型分支预测错误发生在同一条分支指令，仅仅通过PC地址无法提前预判跳转条件是否跨越跳转阈值而不再跳转，因此还需要在“不该跳却跳”错误发生的时候，根据译码状态采集跳转条件相关的各种信息。为此，本设计提出如图3所示的分支条件学习器，学习“不该跳却跳”预测失败状态。由于译码段滞后PC段两个时钟周期，为了在PC段就能完成分支条件的预测，分支条件预测基准需要记录为分支判断主体两个周期前的状态。

图3 引入分支条件学习器的分支预测结构原理图

对称密码协处理器采用计数器CNT作为分支条件的判断主体，使用“≥”“≤”“=”“≠”作为分支判定符。因此，本文设计的分支条件学习器采用PC阶段的CNT_PC作为分支预测判断主体，使用比较符“≥”“≤”“=”“≠”作为分支预测判定符。下面证明设计的合理性。

以第（1）种代码风格实现的轮函数为例，当触发“不该跳却跳”预测错误的时候，跳转指令在PC阶段时记录的CNT_PC值为9（由于前一条指令处于IF阶段，因此本轮的CNT_ID值尚未计算出来）。此时，分支条件学习器采用CNT_PC ＜9来预测CNT_ID ≤9，其极限命中率分析如下：

由于在PC阶段进行分支预测时，前一条指令处于IF阶段，其CNT值尚未递增，但随着分支指令执行到ID阶段，前一条指令将处于ID阶段的下一个流水段，其CNT值终将完成本轮递增，因此预测CNT_PC ＜9相当于预测CNT_ID ＜10，又由于CNT的值必为整数，因此有CNT_ID ＜10等效于CNT_ID ≤9。

综上，预测CNT_PC ＜9等效于预测CNT_ID≤9。

由此可见，分支条件学习器记录的阈值信息可以反映真实的跳转条件。在“预测跳转必然发生”的静态分支预测机制的基础上，增加这样的分支条件学习器，可以使分支预测的极限命中率达到100%。

由于每条分支指令只可能有一个分支条件，因此m条分支指令只需要m个分支条件学习表项。以64条分支指令、20比特的分支条件位宽为例，整个分支条件学习器的存储器开销仅为160 B，达到了轻量级设计的目标。

3.2 分支预测的执行流程

基于条件学习的分支预测技术在“预测跳转必定发生”的静态分支预测基础上，通过引入“分支预测失败状态学习”的功能来获取跳转条件的阈值信息，从而实现预测“所有指令不跳转”→“分支指令必定跳转”→“分支指令条件跳转”3个阶段的逐步演进，使分支预测在运行过程中逐渐趋近于真实情况。

在程序运行过程中，当触发过“该跳不跳”和“不该跳却跳”两型分支预测错误后，在程序指针PC更新的流水阶段，根据PC值来判断当前指令是否为跳转指令，并且预测跳转条件是否满足，跳转操作是否执行，并获取跳转方向和跳转目标地址。其执行流程如图4所示。

图4 基于条件学习的分支预测指令执行流程

当程序开始执行（PC阶段）时，分支预测器通过当前PC值查询分支预测表（分支预测表中储存有分支指令的PC值和对应跳转目的地址信息）。若分支预测表中不存在该指令的PC值，则预测当前指令不是分支指令，程序顺序执行（PC+1）；若分支预测表中存在该指令的PC值，则预测当前指令是分支指令，需要继续查询对应的分支条件表项（分支条件表项中储存有分支预测错误状态学习记录）。如果表项中没有学习记录，则预测当前指令必定跳转至分支预测表项中记录的目标地址；如果表项中有学习记录，则需要判断当前的分支状态是否达到记录的错误状态。如果没有达到错误状态则预测程序跳转至目标地址，如果达到错误状态则预测程序顺序执行。

在译码（ID）阶段，分支预测判断逻辑根据指令的译码信息判断该指令是否为分支指令。若为分支指令，则根据指令的相关译码信息对本次分支预测行为进行判断，若分支预测成功，则对称密码协处理器继续顺序执行；若分支预测失败，这时需要立刻更改PC值，并清除已错误取出的指令。此外，分支指令在触发“该跳不跳”错误时，需将该指令的分支信息（PC值、跳转目标地址）写入分支预测表中；触发“不该跳却跳”错误时，需将错误阈值信息（CNT_PC）和分支判定符（“≥”“≤”“=”“≠”）记录到分支条件表中。

4 分支预测改进的效果

对于条件分支指令，基于分支条件学习的分支预测技术在“预测跳转必定发生”的静态分支预测机制消除了“该跳不跳”分支预测错误的基础上，进一步消除了由该机制引入的“不该跳却跳”分支预测错误，通过最少1个、最多2个分组的学习，将分支预测的极限命中率从1-1/N或1/N提升至100%，基本消除了分支预测极限命中率受循环轮数以及代码风格限制的问题。

假设待处理的数据包包含y个分组，每个分组执行z次循环。

4.1 对于第（1）（2）种代码风格

“预测跳转必然发生”的静态分支预测在第1个分组失败2次，后续每个分组失败1次，因此，其平均命中率为P=1-(y+1)/yz，命中率与分组数、循环数的关系如图5所示。

图5 静态分支预测命中率关系图（代码风格1、2）

本文研究的分支预测在第1个分组失败2次，在后续分组全部命中，因此，其总体命中率为P=1-2/yz，命中率与分组数、循环数的关系如图6所示。

图6 改进后分支预测命中率关系图（代码风格1、2）

当循环轮数为8时，改进的分支预测处理5个分组就能得到95%的平均命中率，处理25个分组就能得到99%以上的平均命中率，相对于改进前的85%和87%分别提高10%和12%。当循环轮数为16时，改进的分支预测处理3个分组就能得到95%的平均命中率，处理13个分组就能得到99%以上的平均命中率，相对于改进前的91%和93%分别提高4%和6%。随着分组数的不断增大，命中率的极限值由1-1/z提升为100%。

4.2 对于第（3）（4）种代码风格

“预测跳转必然发生”的静态分支预测在第1个分组失败1次，在后续每个分组失败z-1次，因此，其平均命中率为P=(y+z-1)/yz，命中率与分组数、循环数的关系如图7所示。

图7 静态分支预测命中率关系图（代码风格3、4）

本文研究的分支预测在第1个分组失败1次，在第2个分组失败z-1次，后续分组全部命中，因此，其总体命中率为P=1-1/y，命中率与分组数、循环数的关系如图8所示。

图8 改进后分支预测命中率关系图（代码风格3、4）

当循环轮数为8或16时，改进的分支预测处理20个分组就能得到95%的平均命中率，相对于改进前的16%和10%分别提高79%和85%；处理100个分组就能得到99%的平均命中率，相对于改进前的13%和7%分别提高86%和92%。随着分组数的不断增大，命中率的极限值由1/z提升为100%。

5 结语

本文研究了面向对称密码协处理器的分支预测技术，结合对称密码算法实现结构中以循环体为代表的分支指令大概率会执行跳转，密码算法程序规模小、重复执行次数不高，以及跳转条件简单并且固定的特征，在“预测跳转必定发生”的分支预测机制基础上，通过新增分支条件学习器、记录指令跳转阈值的设计，以轻量级的硬件开销和极短的学习过程，将分支预测的平均命中率大幅提升，使其极限命中率与密码算法的循环轮数无关，同时降低了不同风格的代码对分支预测命中率的影响，为高性能对称密码协处理器减少分支指令引入的程序流控制开销提供了解决方案。