Previous [ 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 (July 2004)

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.
+Leadtek Inc.
Taipei, 235 Taiwan

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

Full Text (¥ş¤åÀÉ) Retrieve PDF document (200407_01.pdf)

Received September 19, 2002; revised June 26, 2003; accepted December 10, 2003.
Communicated by Yu-Chee Tseng
*This research was supported in part by the Office of Naval Research under grants N00014-95-1-0514 and N00014-96-1-0897, and in part by the Department of Defense/Air Force Office of Scientific Research under grant F49620-96-1-0472.