Optimal prefetching via data compression

ABSTRACT

Caching and prefetching are important mechanisms for speeding up access time to data on secondary storage. Recent work in competitive online algorithms has uncovered several promising new algorithms for caching. In this paper, we apply a form of the competitive philosophy for the first time to the problem of prefetching to develop an optimal universal prefetcher in terms of fault rate, with particular applications to large-scale databases and hypertext systems. Our prediction algorithms with particular applications to large-scale databases and hypertext systems. Our prediction algorithms for prefetching are novel in that they are based on data compression techniques that are both theoretically optimal and good in practice. Intuitively, in order to compress data effectively, you have to be able to predict future data well, and thus good data compressors should be able to predict well for purposes of prefetching. We show for powerful models such as Markov sources and mthe order Markov sources that the page fault rate incurred by our prefetching algorithms are optimal in the limit for almost all sequences of page requests.

REFERENCES

• 1: Naoki Abe , Manfred K. Warmuth, ON THE COMPUTATIONAL COMPLEXITY OFAPPROXIMATING DISTRIBUTIONS BY PROBABILISTIC AUTOMATA, University of California at Santa Cruz, Santa Cruz, CA, 1990
• 2: AMIT, Y., AND MILLER, M. 1990. Large deviations for coding Markov chains and Gibbs random ~ field~s. Tech. Rep. Washington Univ.
• 3: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 4: BLACKWELL, D. 1956. An analog to the minimax theorem for vector payoffs. Pac. J. Math. 6, 1-8.
• 5: Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
• 6: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 7: R. Board , L. Pitt, On the necessity of Occam algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.54-63, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100223]
• 8: Allan Borodin , Prabhakar Raghavan , Sandy Irani , Baruch Schieber, Competitive paging with locality of reference, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.249-259, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103422]
• 9: James T Brady, A theory of productivity in the creative process, IEEE Computer Graphics and Applications, v.6 n.5, p.25-34, May 1986 [doi>10.1109/MCG.1986.276789]
• 10: Tien-Fu Chen , Jean-Loup Baer, Reducing memory latency via non-blocking and prefetching caches, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.51-61, October 12-15, 1992, Boston, Massachusetts, United States
• 11: COVER, r. M., AND SHENHAR, A. 1977. Compound Bayes predictors with apparent Markov ~ structure. IEEE Trans. Syst. Man Cyb. SMC-7 (June), 421-424.
• 12: 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
• 13: FEDER, M., MERHAV, N., AND GUTMAN, M. 1992. Universal prediction of individual sequences. ~ IEEE Trans. Inf. Theory IT-38 (July), 1258-1270.
• 14: Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
• 15: Robert G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, Inc., New York, NY, 1968
• 16: HANNAN, J.F. 1957. Approximation to Bayes risk in repeated plays. In Contributions to the Theory ~ of Games, Vol. 3, Annals of Mathematical Studies. Princeton, N.J., 97-139.
• 17: Paul G. Howard , Jeffrey Scott Vitter, Analysis of arithmetic coding for data compression, Information Processing and Management: an International Journal, v.28 n.6, p.749-763, Nov.–Dec. 1992 [doi>10.1016/0306-4573(92)90066-9]
• 18: Sandy Irani , Anna R. Karlin , Steven Phillips, Strongly competitive algorithms for paging with locality of reference, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.228-236, September 1992, Orlando, Florida, United States
• 19: KARLIN, A. R., PHILLIPS, S. J., AND RAGHAVAN, P. 1992. Markov paging. In Proceedings of the 33rd ~ Annual IEEE Conference on Foundations of Computer Science (Oct.). IEEE, New York, pp. ~ 208 -217.
• 20: KARLIN, S., AND TAYLOR, H.M. 1975. A First Course in Stochastic Processes, 2nd ed., Academic ~Press, New York.
• 21: KEARNS, M. J., AND SCHAPIRE, R.E. 1990. Efficient distribution-free learning of probabilistic concepts. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (Oct.). IEEE, New York, pp. 382-391.
• 22: P. Krishnan , Jeffrey Scott Vitter, Optimal prediction for prefetching in the worst case, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.392-401, January 23-25, 1994, Arlington, Virginia, United States
• 23: LAIRD, P. 1992. Discrete sequence prediction and its applications. AI Research Branch, NASA ~ Ames Research Center, Moffet Field, Calif.
• 24: LANGDON, G. G. 1983. A note on the Ziv-Lempel model for compressing individual sequences. ~ IEEE Trans. Inf. Theory 29 (Mar.), 284-287.
• 25: LANGDON, G. G. 1984. An introduction to arithmetic coding. IBM J. Res. Develop. 28 (Mar.), ~ 135-149.
• 26: LEMPEL, A., AND ZIv, J. 1976. On the complexity of finite sequences. IEEE Trans. Inf. Theory ~ IT-22, i (Jan.), 75-81.
• 27: McGEOCH, L. A., AND SLEATOR, D.D. 1989. A strongly competitive randomized paging algorithm. ~ CS-89-122. Carnegie-Mellon Univ., Pittsburgh, Pa.
• 28: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• 29: Mark Palmer , Stanley B. Zdonik, Fido: A Cache That Learns to Fetch, Proceedings of the 17th International Conference on Very Large Data Bases, p.255-264, September 03-06, 1991
• 30: R. Hugo Patterson , Garth A. Gibson , M. Satyanarayanan, A status report on research in transparent informed prefetching, ACM SIGOPS Operating Systems Review, v.27 n.2, p.21-34, April 1993 [doi>10.1145/155848.155855]
• 31: Anne Rogers , Kai Li, Software support for speculative loads, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.38-50, October 12-15, 1992, Boston, Massachusetts, United States
• 32: SHWARTZ, A., AND WEISS, A. 1995. Large Deviations for Performance Analysis. Chapman & Hall, ~ New York.
• 33: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 34: TRIVEDI, K.S. 1979. An analysis of prepaging. Computing 22, 191-210.
• 35: VAPNIIC, V. 1982. Estimation of Dependencies Based on Empirical Data. Springer-Verlag, New ~ York.
• 36: VITTER, J. S., CUREWITZ, K., AND KRISHNAN, P. 1996. Online background predictors and prefetch- ~ ers. Duke Univ., United States Patent No. 5,485,609.
• 37: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]
• 38: ZIv, J., AND LEMPEL, A. 1978. Compression of individual sequences via variable-rate coding. IEEE ~ Trans. Inf. Theory 24 (Sept.), 530-536.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Swapping**

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory
      D.4.8 Performance
          Subjects: Stochastic analysis

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Markov source, caching, competitive analysis, data compression, databases, fault rate, hypertext, prediction, prefetching, secondary stage, universal prefetcher