A General Low-Cost Indirect Branch Prediction Using Target Address Pointers

Nowadays energy-efficiency becomes the first design metric in chip development. To pursue higher energy efficiency, the processor architects should reduce or eliminate those unnecessary energy dissipations. Indirect-branch pre- diction has become a performance bottleneck, especially for the applications written in object-oriented languages. Previous hardware-based indirect-branch predictors are generally inefficient, for they either require significant hardware storage or predict indirect-branch targets slowly. In this paper, we propose an energy-efficient indirect-branch prediction technique called TAP （target address pointer） prediction. Its key idea includes two parts： utilizing specific hardware pointers to accelerate the indirect branch prediction flow and reusing the existing processor components to reduce additional hardware costs and power consumption. When fetching an indirect branch, TAP prediction first gets the specific pointers called target address pointers from the conditional branch predictor, and then uses such pointers to generate virtual addresses which index the indirect-branch targets. This technique spends similar time compared to the dedicated storage techniques without requiring additional large amounts of storage. Our evaluation shows that TAP prediction with some representative state-of-the-art branch predictors can improve performance significantly over the baseline processor. Compared with those hardware-based indirect-branch predictors, the TAP-Perceptron scheme achieves performance improvement equivalent to that provided by an 8 K-entry TTC predictor, and also outperforms the VPC predictor.     

提前分支预测结构及算法研究

在理论上,越来越复杂的分支预测算法和更大的存储结构会使分支预测精度不断提高,但当前复杂算法和庞大数据结构所引发的分支预测时延已无法满足流水线单周期运行要求.针对分支预测精度和时延的矛盾,设计提出提前分支预测结构(ahead branch prediction architecture,ABPA).ABPA为流水线前端取指部件提供简单的分支预测表,以实现快速分支预测;复杂的预测算法和较大的存储结构均被移至流水线后端实现,从而保证了分支预测精度.对于一直难以准确预测的多目标间接分支指令,设计提出基于分支历史和目标路径的间接分支预测算法(indirect branch prediction algorithm based on branch history and target path,BHTP algorithm).提前分支预测算法采用改进的高精度分支预测算法和BHTP算法的混合.嵌入提前分支预测算法的分支预测引擎实现流水线后端的分支推测和目标预测,以及流水线前端的分支预测表更新.实验结果表明：采用ABPA结构和BHTP算法的分支预测系统平均精度达到94.27%.设计不仅实现了快速、高精度分支预测,更为分支预测的深入研究提供了条件.     

Effectively exploiting indirect jumps

This paper describes a general code‐improving transformation that can coalesce conditional branches into an indirect jump from a table. Applying this transformation allows an optimizer to exploit indirect jumps for many other coalescing opportunities besides the translation of multiway branch statements. First, dataflow analysis is performed to detect a set of coalescent conditional branches, which are often separated by blocks of intervening instructions. Secondly, several techniques are applied to reduce the cost of performing an indirect jump operation, often requiring the execution of only two instructions on a SPARC. Finally, the control flow is restructured using code duplication to replace the set of branches with an indirect jump. Thus, the transformation essentially provides early resolution of conditional branches that may originally have been some distance from the point where the indirect jump is inserted. The transformation can be frequently applied with often significant reductions in the number of instructions executed, total cache work, and execution time. In addition, we show that with branch target buffer support, indirect jumps improve branch prediction since they cause fewer mispredictions than the set of branches they replaced. Copyright © 1999 John Wiley & Sons, Ltd.     

BTB索引散列算法的研究与设计

分支误预测是影响高性能处理器性能进一步提升的一个主要因素.现代处理器采用分支目标缓存(branch target buffer, BTB)预测分支指令的目标地址,BTB的预测精度受限于其命中率.由于程序中分支指令的分布并不均匀,传统的BTB索引方式无法充分利用BTB资源,从而造成不必要的冲突缺失,影响分支目标地址的预测精度,采用散列索引方式优化访问映射关系是有效解决方法之一.当前大量文献研究了cache的访问方式,但对BTB的散列索引算法的专门探讨则显不足.为了消除分支指令的分布空洞,离散分支指令和BTB条目的固有映射关系,设计了用于BTB索引的XOR散列算法和优化的bit-select索引算法,使用概率方法对BTB单组最大映射数期望的上界作了估计,并对这两种散列索引算法的效果进行了模拟评估.实验结果表明,散列映射方式能够较好地避免BTB冲突缺失造成的预测失败,XOR散列算法的离散效果更好.     

A novel architecture for ahead branch prediction

In theory, branch predictors with more complicated algorithms and larger data structures provide more accurate predictions. Unfortunately, overly large structures and excessively complicated algorithms cannot be implemented because of their long access delay. To date, many strategies have been proposed to balance delay with accuracy, but none has completely solved the issue. The architecture for ahead branch prediction (A²BP) separates traditional predictors into two parts. First is a small table located at the front-end of the pipeline, which makes the prediction brief enough even for some aggressive processors. Second, operations on complicated algorithms and large data structures for accurate predictions are all moved to the back-end of the pipeline. An effective mechanism is introduced for ahead branch prediction in the back-end and small table update in the front. To substantially improve prediction accuracy, an indirect branch prediction algorithm based on branch history and target path (BHTP) is implemented in A²BP. Experiments with the standard performance evaluation corporation (SPEC) benchmarks on gem5/SimpleScalar simulators demonstrate that A²BP improves average performance by 2.92% compared with a commonly used branch target buffer-based predictor. In addition, indirect branch misses with the BHTP algorithm are reduced by an average of 28.98% compared with the traditional algorithm.     

反馈式编译优化在转移预测中的研究

处理器性能的发挥常常受到转移指令的限制,所以转移预测的成功与否对于处理器的性能影响至关重要。反馈式编译优化是一种基于程序当前和以前运行时的趋势来改变程序以后执行动作的技术,能够提供给编译器一些有用的优化信息。本文针对ALPHA中的结构特点,利用反馈式编译优化技术,提高了ALPHA中的转移预测命中率,实验结果表明,加速比效果较为明显。     

一种复合分支预测电路的设计与实现

针对现有预测算法仅能精准预测某类程序的缺陷,设计一种复合分支预测电路。该电路组合多种分支预测算法,可以对各种程序进行精准预测,并应用于自主设计的嵌入式微处理器中。性能仿真结果表明,复合分支预测电路对各种程序可以实现高精准预测,并且满足处理器设计的时序要求。     

开源处理器Rocket的分支预测机制与性能评估

Rocket是基于RISC-V指令集架构的开源处理器,具有分支预测功能,其实现了GShare分支预测机制,在分析Rocket处理器分支预测处理过程、分支预测实现原理的基础上,利用模拟器进行了性能测试,并依据测试结果,对Rocket处理器分支预测参数配置给出建议.     

基于历史长度自适应的分支预测方法

通过研究处理器动态分支预测器中预测效率与分支历史长度的关系,针对程序中各分支指令存在不同最优历史长度的规律,提出一种搜索各分支指令最佳历史长度的分支预测方法.该方法通过实时监测分支指令的预测准确率,在分支预测表硬件资源不变的情况下动态调整预测器的历史长度,以适应程序的动态运行特征.实验结果表明,在相同硬件资源下,文中方法相对于Gshare预测器错误率降低15.8%,相对于Bi-mode预测器预测错误率降低10.3%.     

基于跳跃访问控制的低功耗分支目标缓冲器设计

传统的分支目标缓冲器(BTB)每个取指周期都要进行访问,由于程序中的分支指令只占总指令数的20%左右,使得大约80%的BTB访问都是无效的.为此,利用程序控制流中分支指令间距固定的特性,提出一种对性能影响极小的BTB跳跃访问算法.在BTB中存储分支指令到运行路径中下一条分支指令的距离,BTB命中后,根据相应的分支距离来关闭当前分支指令与下一条分支指令之间的BTB访问,以有效地提高访问效率并降低动态功耗.该算法在嵌入式处理器中实现时只控制预测跳转分支指令的BTB跳跃访问,减少了硬件资源的开销.在硬件模型上进行模拟和综合后的结果表明,在128分支项的BTB中,采用文中算法可以降低72%的动态功耗,而性能损失仅为0.013%.     

基于循环体访问过滤的低功耗分支目标缓冲器

分支目标缓存(BTB)是高端嵌入式CPU的主要耗能部件之一。针对BTB访问中引入的冗余功耗问题,提出了一种循环体访问过滤机制消除循环体指令流中顺序指令对BTB的无效访问。进一步提出了一种分支跟踪方法补偿循环过滤机制对循环体中非循环类分支指令的错误过滤造成的性能损失,节省了循环体指令流中顺序指令访问BTB的大量冗余功耗。基于Powerstone基准程序的仿真实验表明,在128表项BTB配置下,二级循环过滤器和4表项分支踪迹表可以减少约71.9%的BTB功耗,而平均每条指令周期数(CPI)退化仅为0.66%。     

嵌入式微处理器分支预测的设计与实现

针对五级流水线嵌入式微处理器的特定应用环境,对分支预测技术进行了深入研究,提出了一种新的分支预测方案。该方案兼容带缓存设计,通过扩展指令总线,在取指段提前对分支指令跳转方向和目标地址进行预测,保存可能执行而未执行的指令和地址指针以备分支预测失效时得以恢复,减少了预测失效的代价,同时保证了指令流的正确执行。研究表明,该方案硬件开销小,预测效率高,预测失效代价低。     

一种向分支指令后插入冗余指令的容错微结构

随着深亚微米工艺的广泛应用,瞬态故障已成为芯片失效的主要原因.文中提出了一种向分支指令后插入冗余指令的容错微结构,利用分支误预测浪费的处理带宽,降低了冗余执行导致的性能损失.实验结果表明,该技术的性能损失在6%～31%之间,平均为21%,明显低于MBI技术而和DIE技术的性能损失相当.该技术能够检测流水线上各阶段发生的瞬态故障并能恢复处理器状态,故障检测延时短,需要的硬件开销也较小,非常适合提高带有简单预测机制的嵌入式微处理器的容错能力.     

基于预测和双缓冲区的直升机视景仿真

为了解决直升机视景仿真中的飞控与视景不同步和降落问题,首次提出了一种基于预测和双缓冲的直升机视景系统数据同步的解决方法。该方法首先将直升机的姿态信息进行采样处理,使之与视景仿真频率匹配,然后将处理后的姿态信息分别存储于两个缓冲区中,一个缓冲区的数据驱动场景进行渲染,另一个缓冲区的数据被用来预测下一帧飞机的位置姿态,将预测到的数据发送给视景进行碰撞检测,最终引导直升机正确着落。实验结果显示,该方法产生的数据比不做处理的数据更接近真实数据,能够满足视景仿真数据的实时性需求,目前该方法已成功应用在直升机通用着舰训练系统中。     

移动自组网中基于移动预测和概率的能量有效组播路由算法

移动自组网中节点的使用寿命很大程度上依赖于电池能量的有效利用．通过研究移动节点能量的剩余和使用情况，提出了一种新的关于节点能量估价函数PCF（power cost function）计算方法，能够较好地反映当前节点的能耗值．并且结合PCF提出一种基于移动预测和概率构造能量有效组播树M-REMiT（an algorithm based on mobility prediction and probability for refining energy-efficient multicast tree）的分布式算法，在节点移动的情况下，利用概率优化方法减少一棵组播树的总能量消耗，延长了组播树中每个节点的使用寿命．模拟结果显示这个组播算法比以前相关的算法具有更好的性能．     

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

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

一种精确的分支预测微处理器模型

在当今深流水宽发射的微处理器中，为实现高性能，精确的分支预测是不可缺少的关键技术．分支预测失效将浪费大量的时钟周期，无法发挥乱序执行的效能．宽发射微处理器的有效性能同时还依赖指令窗口的大小和指令预取宽度．提出了一种新的更精确的支持分支预测和分支误预测周期损失的微处理器模型．根据指令的执行带宽为指令窗口中可用指令数的平方根统计规律，给出了一个更为精确的描述微处理器取指带宽、分支预测精度、分支误预测周期损失、指令窗口大小和IPC之间关系的算法，并讨论了这些参数的综合权衡以及这些参数对程序IPC的影响．由此可以确定依赖多个微处理器参数的取指带宽阈值和微处理器中几个关键参数的选取．     

间接转移指令在动态二进制翻译器中的预测方法

动态二进制翻译器中间接转移指令的预测优化对其性能至关重要.在研究了动态二进制翻译器的取值信息收集框架后,给出如何在程序运行起始阶段对间接转移指令的目标地址进行取值信息收集的方法,并结合统计原理,提出对目标地址的预测应该结合取值信息进行区间估计.最后,提出了一个基于取值信息收集分析结果进行目标地址预测的优化决策函数并且通过在动态二进制翻译器"IA-32 Execution Layer"上进行实验验证了该决策函数对于间接转移指令预测的效果,并讨论了其准确性和精确度.     

基于指令流访存模式预测的缓存替换策略

传统的缓存替换策略主要基于经验主义,近年来研究者们使用预测技术推测访存行为,提高缓存替换的准确性,预测技术的应用是当前缓存替换策略研究的热点.由于访存行为自身的复杂性,直接在缓存系统中预测访存行为是困难的,要面对很大的不确定性.当前已有的研究为了解决该问题,使用越来越复杂的预测算法来分析访存行为之间的关联.然而这种方式并未真正减小不确定性,同时现有的缓存替换策略很难避免乱序执行和缓存预取对访存行为分析过程的干扰.为了解决以上问题,提出了一种新的预测缓存访问序列的方法IFAPP(instruction flow access pattern prediction),根据分支预测技术推测程序指令流,定位指令流中的访存指令,进而对其中访存指令的行为逐一进行预测.通过访存序列计算每个替换候选项的重用距离,将重用距离最远的候选项踢出.该方法可以避免乱序执行和缓存预取的干扰,预测对象是行为简单的独立访存指令,减少预测过程中所面对的不确定性.实验结果表明,该算法在一级数据缓存上比LRU算法平均减少3.2%的缓存缺失.相比经典的基于缓存预测的BRRIP和BIP算法,该算法在一级数据缓存上分别减少12.3%和14.4%的缓存缺失.     

机动目标预测跟踪方法研究

在目标被遮挡条件下的自动预测跟踪中,研究了跟踪机动目标过程中的角位置自适应卡尔曼预测算法。针对估计与预算中出现的发散现象,推导了导引头框架角位置预测方法。建立了目标遮挡预测跟踪测试系统,设计多种不同的目标运动形式,并通过转台实现,测试改进的自适应位置预测算法在典型测试条件下的有效性和准确程度。实验结果表明:当目标进入遮挡区域时,改进的自适应位置预测算法能够有效地实现预测跟踪,保证目标退出遮挡时能够顺利重新捕获和跟踪。