Loading...

Enhancing Branch Target Buffer Efficiency with a Bias-Aware (Re)placement Policy

Ebrahimi, Mahdi | 2022

300 Viewed
  1. Type of Document: M.Sc. Thesis
  2. Language: Farsi
  3. Document No: 56106 (19)
  4. University: Sharif University of Technology
  5. Department: Computer Engineering
  6. Advisor(s): Sarbazi Azad, Hamid; Hessabi, Shaahin
  7. Abstract:
  8. Branch Target Buffer is a widely used component in modern processors. While there are different designs for BTB, they generally have a set-associative structure keeping branches and their target to help the frontend fetch the instructions on the correct path. To achieve high performance, it’s essential to obtain a high hit rate out of the BTB. Prior works has shown that BTB suffers from frequent misses that require large sizes or sophisticated BTB prefilling mechanisms to overcome the problem. However, the first solution imposes a significant storage overhead, and the latter results in limited benefits. Prior works have shown that branches exhibit different behaviors from being strongly taken to strongly not taken. Accordingly, we argue that BTB can be polluted by branches that are biased toward being not taken. These branches do not contribute to the program's control flow; however, occupy entries in the BTB. Therefore, there is a potential to devote the BTB capacity to branches that have a stronger bias toward being taken compared to others. This phenomenon can be utilized for designing a Bias-Aware BTB by improving its insertion and replacement policy. The goal is to have a BTB that despite having a high hit rate for the program's branches, maximizes the "taken-branch hit rate" since it is the actual parameter that improves the processor's efficiency. In this research, a bias-aware policy named DBAP with total overhead of 4.41 KB is presented, which simulates the behavior of the optimal policy and uses the result of its decisions to determine insertion or not insertion of branches. On average, DBAP covers 90% of the gap between LRU and the optimal policy in Taken MPKI and provides 44% more efficiency than LRU, which is equivalent to 97% of the total performance improvement space between LRU and the optimal policy.
  9. Keywords:
  10. Server Workloading ; Branch Target Buffer (BTB) ; Replacement Policy ; Bias-Aware Policy ; Insertion Policy ; Decision Simulation ;

 Digital Object List

 Bookmark

No TOC