动态翻译系统中的间接转移关联软件预测算法

Correlated Software Prediction for Indirect Branch in Dynamic Translation Systems

动态翻译系统每执行一次间接转移指令均需进行一次地址转换,该过程是翻译系统性能开销的主要来源之一.无特殊硬件支持的翻译系统常采用软件预测法来降低地址转换开销,而软件预测法的预测准确率较低,制约其对翻译系统整体性能的提升.低开销关联软件预测算法(low-overhead correlated software prediction,LOCSP)可利用代码副本区分待预测指令的不同转移场景,将到达该指令的多条动态执行路径分离为多个互不重合的代码缓存副本,并为各个副本提供独立的预测链.从而在不增加动态指令数的前提下实现关联预测,显著提升软件预测的预测准确率.同时,LOCSP算法基于动态剖析的结果,仅对部分难预测的热点间接转移指令进行关联软件预测,进一步降低预测开销.实验表明,相比软件预测法,LOCSP算法可将平均预测准确率从58.9%提升至82.2%,将翻译系统的整体性能开销平均降低19.3%,最高降低41.9%,而平均静态代码数量仅增加2.4%.

Dynamic translation system should perform an address translation for each execution of indirect branch instructions, so handling indirect branch becomes a major performance overhead of the system. The translation systems without hardware support always use software prediction to reduce the overhead of address translation, but the low prediction accuracy restricts the performance improvement. This paper analyzes the performance bottleneck of software prediction, and proposes a novel prediction mechanism called low-overhead correlated software prediction （LOCSP）, which can significantly improve the prediction accuracy using branch correlation. LOCSP uses code replicas to distinguish the different branch occasions of an indirect branch instruction. By making different control flows execute different code replicas, and deploying individual software prediction chains for each replica, LOCSP realizes correlated prediction without any increase in dynamic instruction count. Meanwhile, LOCSP classifies the indirect branch instructions by dynamic profiling, and only applies correlated prediction on hot and hard-to-predict instructions, further minimizing prediction overhead. The experiment shows that, compared with software prediction, LOCSP can improve the average prediction accuracy from 58.9% to 82.2%, thus reduces the performance overhead by 19.3% on average, up to 41.9%, while only increases static code size by 2.4% on average. Furthermore, LOCSP can cooperate with other optimization techniques of handling indirect branch.