JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]


Journal of Information Science and Engineering, Vol. 20 No. 4, pp. 557-574


Effective Branch Prediction through Caching of Aliasing Branches


Wei-Ming Lin and An-Yi Yang+
Department of Electrical Engineeing 
The University of Texas at San Antonio 
San Antonio, TX 78249, U.S.A. 
E-mail: wlin@utsa.edu 
+Leadtek Inc. 
Taipei, 235 Taiwan 
E-mail: kevin_yang@leadtek.com.tw


    High performance CPUs constantly face obstacles in pipelining delays from conditional branches to reach their expected potential. Precise branch prediction is required to overcome this performance limitation imposed on high performance architecture and is the key to many techniques for enhancing and exploiting Instruction-Level Parallelism (ILP). In general, prediction accuracy can be improved by reducing aliases in the prediction table used in a traditional dynamic prediction mechanism. In this paper, we propose a new technique to significantly reduce the more likely destructive aliases by caching up recurring aliasing branches that occur within a small temporal locality with one another. An extensive pre-simulation analysis on traces clearly supports such a claim showing that aliasing branches with a small temporal locality account for majority of all aliases. This paper further shows that such aliases are more likely to lead to destructive prediction result. Thus, our technique, incorporated with a small additional “alias table” with its size much smaller than the existing prediction table normally used, is capable of eliminating most of aliases, especially the highly performance-degrading repetitive “local” aliases. Our simulation results demonstrate a significant improvement in prediction accuracy from adopting this technique while requiring very limited extra hardware cost. In addition, this proposed add-on feature can be easily incorporated into any existing or advanced dynamic branch predictors to further enhance their prediction performance.


Keywords: branch prediction, instruction-level parallelism, high performance computing, aliases, dynamic branch prediction

  Retrieve PDF document (JISE_200404_01.pdf)