Enhancing the Accuracy of O-GEHL Branch Predictor: Analysis and ApproachEkkasit Tiamkaew Department of Computer Science and Information TechnologyNaresuan UniversityPhitsanulok, ThailandAngkul Kongmunvattana Department of Computer Science Columbus State UniversityColumbus, GA 31907USAAbstractIn the first international branch prediction competition, the O-GEHL branch predictor has shown to yield the highest prediction accuracy under an official limited storage budget of 64Kbits. In this paper, we propose and evaluate two alternative designs of the predictor to further improve its efficiency. The first proposed method dynamically adjusts the lengths of branch history used in its indexing function with regard to the type of a benchmark currently in execution. The aim is to increase space utilization of the first predictor table. The second one proposes to add an extra table into the predictor using the space saved from the sharing of hysteresis bits. Experimental results show that each scheme increases the accuracy of two different predictor configurations, creating two attractive research paths for future explorations.1. INTRODUCTIONWhile so much efforts in branch prediction research have focused on reducing the aliasing rate or lowering its impact [2, 3, 9, 10], such strategy has limited potential to improve prediction accuracy since behaviors of some branch instructions are simply unpredictable. To aid the study such branch, perceptron, a simple version of neural networks, has been adapted for use in a branch predictor [6, 7].At the first championship branch prediction contest [1], the top three predictors, within a limited budget of 64Kbits using a common workload, are primarily based on perceptron and are at least 4.34% more accurate than the fourth placed. The first-placed O-GEHL (Optimized GEometric History Length) predictor [11] exploits various lengths of global branch history and also contains a dynamic mechanism that can adaptively adjust history lengths of its predictor tables, allowing longer branch history to be deployed when necessary.In this paper, we perform an extensive analysis on the O-GEHL predictor, mainly searching for its characteristics that can be exploited to enhance its efficiency. Based on the results, we subsequently propose two alternative designs aimed at enhancing the O-GEHL predictor as follows: 1) increasing its space utilization in the first predictor table, T0, by dynamically adjusting branch history lengths used in the indexing function, and 2) adding an additional predictor table without requiring extra space by means of sharing hysteresis bits.Our simulation results show that the first proposed scheme improves the prediction accuracy in almost all hardware budgets, except for 8K and 16K bits. Meanwhile, the second scheme provides best performance when working with branch predictors larger than 64K bits, indicating that when there are abundant hardware resources, adding extra predictor tables is more likely to improve prediction accuracy than increasing the size of the existing predictor tables. Further analysis of the experimental results reveals that even though the second scheme performs worse than the first one on average, it enjoys more success in large branch predictors.The rest of this paper proceeds as follows. Section 2 provides a background on the O-GEHL branch predictor as well as related work and Section 3 describes our experimental setup. Section 4 shows our analysis results on the O-GEHL predictor. Our proposed enhancements and evaluation results are discussed in Section 5. Finally, we conclude in Section 6.2. PERTINENT BACKGROUND2.1 Overview on the O-GEHL Branch PredictorThe O-GEHL predictor can be perceived as an enhanced version of perceptron predictor, which uses the perceptron, a simple form of neural networks, to keep neuron weights for the calculation
本文来源：https://www.2haoxitong.net/k/doc/6026e19a51e79b8968022656.html
