ISSN 1000-1239 CN 11-1777/TP

• 系统结构 •

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

1. (国家高性能集成电路设计中心 上海 201204) (wgp06@mail.ustc.edu.cn)
• 出版日期: 2014-09-01
• 基金资助:
基金项目：“核高基”国家科技重大专项基金项目(2009ZX01028-002-001)

### Research and Design of Hash Indexing Mechanism for BTB

Wang Guopeng, Hu Xiangdong, Yin Fei, Zhu Ying

1. (National High Performance IC Design Center, Shanghai 201204)
• Online: 2014-09-01

Abstract: 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 Hash-indexing 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.