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

Research and Design of Hash Indexing Mechanism for BTB

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

It is well known that branch mispredictions have become a serious bottleneck to achieve better processor performance.Branch-target buffer（BTB）,which caches the most recent resolved target,is the important dedicated structure to provide branch target address in modern processors.However,because of inheriting from cache,the performance of BTB is restricted by its hit ratio.Due to the nonuniform distribution of branch instructions,the conventional indexing method always causes many unnecessary conflicts,having negative effects on BTB performance.Such mispredictions caused by conflicts can be easily avoided by means of a properly chosen Hash function.Although Hash functions have been well studied to improve the utilization of memory system,the Hash-indexing method,which is specifically indicated for BTB,is not explored in literature.In this paper,based on analysis of regular pattern of branch distribution and control flow in program,the Hash indexing mechanism for BTB is researched and two Hash-indexing methods for BTB are designed in this paper.One is XOR-based Hash function,the other is optimized bit-select method.The evaluation framework is estimated for set index function so that the best-performing transformation matrix can be fast detected.The maximal number of branches,which are mapped to the same BTB set under Hashindexing mechanism,is evaluated by probability theory.The experimental results show that our Hash-indexing methods are efficient to minimize BTB mis-predicitons caused by conflict miss;the XOR-based Hash function performs even better.