• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

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

王国澎, 胡向东, 尹飞, 朱英

王国澎, 胡向东, 尹飞, 朱英. BTB索引散列算法的研究与设计[J]. 计算机研究与发展, 2014, 51(9): 2003-2011. DOI: 10.7544/issn1000-1239.2014.20130132
引用本文: 王国澎, 胡向东, 尹飞, 朱英. BTB索引散列算法的研究与设计[J]. 计算机研究与发展, 2014, 51(9): 2003-2011. DOI: 10.7544/issn1000-1239.2014.20130132
Wang Guopeng, Hu Xiangdong, Yin Fei, Zhu Ying. Research and Design of Hash Indexing Mechanism for BTB[J]. Journal of Computer Research and Development, 2014, 51(9): 2003-2011. DOI: 10.7544/issn1000-1239.2014.20130132
Citation: Wang Guopeng, Hu Xiangdong, Yin Fei, Zhu Ying. Research and Design of Hash Indexing Mechanism for BTB[J]. Journal of Computer Research and Development, 2014, 51(9): 2003-2011. DOI: 10.7544/issn1000-1239.2014.20130132
王国澎, 胡向东, 尹飞, 朱英. BTB索引散列算法的研究与设计[J]. 计算机研究与发展, 2014, 51(9): 2003-2011. CSTR: 32373.14.issn1000-1239.2014.20130132
引用本文: 王国澎, 胡向东, 尹飞, 朱英. BTB索引散列算法的研究与设计[J]. 计算机研究与发展, 2014, 51(9): 2003-2011. CSTR: 32373.14.issn1000-1239.2014.20130132
Wang Guopeng, Hu Xiangdong, Yin Fei, Zhu Ying. Research and Design of Hash Indexing Mechanism for BTB[J]. Journal of Computer Research and Development, 2014, 51(9): 2003-2011. CSTR: 32373.14.issn1000-1239.2014.20130132
Citation: Wang Guopeng, Hu Xiangdong, Yin Fei, Zhu Ying. Research and Design of Hash Indexing Mechanism for BTB[J]. Journal of Computer Research and Development, 2014, 51(9): 2003-2011. CSTR: 32373.14.issn1000-1239.2014.20130132

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

基金项目: “核高基”国家科技重大专项基金项目(2009ZX01028-002-001)
详细信息
  • 中图分类号: TP302

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散列算法的离散效果更好.
    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.
  • 期刊类型引用(10)

    1. 徐怡,陶强. 划分序乘积空间约简算法研究. 系统工程理论与实践. 2025(02): 554-570 . 百度学术
    2. 刘长顺,刘炎,宋晶晶,徐泰华. 基于论域离散度的属性约简算法. 山东大学学报(理学版). 2023(05): 26-35+52 . 百度学术
    3. 张清华,艾志华,张金镇. 融合密度与邻域覆盖约简的分类方法. 陕西师范大学学报(自然科学版). 2022(03): 33-42 . 百度学术
    4. 张雨新,孙达明,李飞. 基于粒化单调的不完备混合型数据增量式属性约简算法. 计算机应用与软件. 2021(03): 279-286 . 百度学术
    5. 邹丽,任思远,杨光,杨鑫华. 基于改进条件邻域熵的接头疲劳寿命影响因素分析. 焊接学报. 2021(11): 43-50+99-100 . 百度学术
    6. 刘正,陈雪勤,张书锋. 基于最小化邻域互信息的邻域熵属性约简算法. 微电子学与计算机. 2020(03): 26-32 . 百度学术
    7. 陈帅,张贤勇,唐玲玉,姚岳松. 邻域互补信息度量及其启发式属性约简. 数据采集与处理. 2020(04): 630-641 . 百度学术
    8. 周艳红,张强. 基于三层粒结构的三支邻域熵. 数学的实践与认识. 2020(14): 83-93 . 百度学术
    9. 亓慧,史颖. 不同度量下集成属性选择器的对比研究. 山西大学学报(自然科学版). 2019(04): 848-853 . 百度学术
    10. 周艳红,张迪,张强. 基于单调信息度量的特定类属性约简. 内江师范学院学报. 2019(12): 35-39 . 百度学术

    其他类型引用(11)

计量
  • 文章访问数:  1604
  • HTML全文浏览量:  4
  • PDF下载量:  840
  • 被引次数: 21
出版历程
  • 发布日期:  2014-08-31

目录

    /

    返回文章
    返回