Advanced Search
    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

    Research and Design of Hash Indexing Mechanism for BTB

    • 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.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return