Branch prediction based on universal data compression algorithms

ABSTRACT

Data compression and prediction are closely related. Thus prediction methods based on data compression algorithms have been suggested for the branch prediction problem. In this work we consider two universal compression algorithms: prediction by partial matching (PPM), and a recently developed method, context tree weighting (CTW). We describe the prediction algorithms induced by these methods. We also suggest adaptive algorithms --- variations of the basic methods that attempt to fit limited memory constraints and to match the non-stationary nature of the branch sequence. Furthermore, we show how to incorporate address information and to combine other relevant data. Finally, we present simulation results for selected programs from the SPECint95, SYSmark/32, SYSmark/NT, and transactional processing benchmarks. Our results are most promising in programs with difficult to predict branch behavior.

REFERENCES

• 1: C. Bloom, PPMZ, h ttp://www, vms. ut e xas. ed u/~c b 1 oo m
• 2: I-Cheng K. Chen , John T. Coffey , Trevor N. Mudge, Analysis of branch prediction via data compression, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.128-137, October 01-04, 1996, Cambridge, Massachusetts, United States
• 3: J. G. Cleary and I. H. Witten, "Data Compression Using Adaptive Coding and Partial String Matching," IEEE Trans. on Communications, pp. 396-402, vol. 32, no. 4, 1984.
• 4: T. M. Cover, "Universal Gambling Schemes and the Complexity Measures of Kolmogorov and Chaitin," Dept. of Statistics, Standford University, no. 12, Oct. 1974.
• 5: Kenneth M. Curewitz , P. Krishnan , Jeffrey Scott Vitter, Practical prefetching via data compression, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.257-266, May 25-28, 1993, Washington, D.C., United States
• 6: L. D. Davisson, "The Prediction Error of Stationary Gaussian Time Series of Unknown Covariance," IEEE Transactions on Information Theory, pp. 527-532, Oct. 1965.
• 7: M. Feder, N. Merhav, and M. Gutman, "Universal Prediction of Individual Sequences," IEEE Transactions on Information Theory, pp. 1258-1270, July 1992.
• 8: M. Feder and N. Merhav, "Relations Between Entropy and Error Probability," IEEE Transactions on Information Theory, pp. 259-266, Jan. 1994.
• 9: J. L Kelly Jr., "A New Interpretation of Information Rate," Bell Systems Tech. Journal, pp. 917-926, 1956.
• 10: S. McFarling, "Combining Branch Predictors," WRL Technical Note TN-36, Digital Equipment Corp., June 1993.
• 11: R. E. Krichevsky and V. K. Trofimov, "The Performance of Universal Encoding," IEEE Trans. information Theory, pp. 199-207, vol. 27, no. 2, 1981.
• 12: A. Moffat, "Implementing the PPM Data Compression Scheme," IEEE Trans. Comm., pp. 1917-1921, vol. 38, no. 11, 1990.
• 13: T. N. Mudge, I-C. K. Chen, and J. T. Coffey, "Limits to Branch Prediction," Technical Report CSE-TR-282-96, University of Michigan, Jan. 1996.
• 14: Shien-Tai Pan , Kimming So , Joseph T. Rahmeh, Improving the accuracy of dynamic branch prediction using branch correlation, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.76-84, October 12-15, 1992, Boston, Massachusetts, United States
• 15: J. Rissanen and G. G. Langdon, "Universal Modeling and Coding," IEEE Transactions on Information Theory, pp. 12-23, 1984.
• 16: C. E. Shannon, "Prediction and Entropy of Printed English," Bell Sys. Tech. Journal Vol. 30, pp. 51-64, 1951.
• 17: Jeffrey Scott Vitter , P. Krishnan, Optimal prefetching via data compression (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.121-130, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185360]
• 18: F. Willems, Y. Shtarkov, and T. Tjalkens, "The Context-Tree Weighting Method: Basic Properties", IEEE Transactions on Information Theory, Vol. IT-41, No. 3, May 1995.
• 19: R. N. Williams, Adaptive Data Compression, Kluwer, 1991.
• 20: Tse-Yu Yeh , Yale N. Patt, Alternative implementations of two-level adaptive branch prediction, Proceedings of the 19th annual international symposium on Computer architecture, p.124-134, May 19-21, 1992, Queensland, Australia
• 21: Cliff Young , Nicolas Gloy , Michael D. Smith, A comparative analysis of schemes for correlated branch prediction, Proceedings of the 22nd annual international symposium on Computer architecture, p.276-286, June 22-24, 1995, S. Margherita Ligure, Italy
• 22: J. Ziv and A. Lempel, "Compression of Individual Sequences via Variable-Rate Coding," IEEE T ransactions on Information Theory, pp. 530-536, Sept. 1978.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Modeling of computer architecture