Article

Free access

Optimal prediction for prefetching in the worst case

Authors:

P. Krishnan,

Jeffrey Scott VitterAuthors Info & Claims

SODA '94: Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms

Pages 392 - 401

Published: 23 January 1994 Publication History

PDF eReader

References

[1]

D. Aldous and U. Vazirani, "A Markovian Extension of Valiant's Learning Model," Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (October 1990), 392-396.

Google Scholar

[2]

L. A. Belady, "A Study of Replacement Algorithms for Virtual Storage Computers," IBM Systems Journal 5 (1966), 78-101.

Google Scholar

[3]

D. Blackwen, "An Analog to the Minimax Theorem for Vector Payoffs," Pacific Journal of Mathematics 6 (1956), 1-8.

Google Scholar

[4]

A. Borodin, S. Irani, P. Raghavan and B. Schieber, "Competitive Paging with Locality of Reference," Proceedings of the 23rd Annual ACM Symposium on Theory of Computation (May 1991).

Digital Library

Google Scholar

[5]

T. M. Cover, "Behavior of Predictors of Binary Sequences," Proceedings of the 4th Prague Conference on Information Theory, Statistical Decision Functions, Random Processes (1967), 263-272.

Google Scholar

[6]

T. M. Cover and A. Shenhar, "Compound Bayes Predictors with Apparent Markov Structure," IEEE Transactions on System Man and Cybernetics SMC-7 (June 1977), 421-424.

Google Scholar

[7]

T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley, 1991.

Digital Library

Google Scholar

[8]

K. Curewitz, P. Krishnan and J. S. Vitter, "Practical Prefetching via Data Compression," Proceedings of the 1993 ACM SIGMOD InternationM Conference on Management of Data(May 1993), 257- 266.

Digital Library

Google Scholar

[9]

P. J. Denning, "Working Sets Past and Present," IEEE Transactions on Software Engg., SF_,-6 (1980), 64-84.

Google Scholar

[10]

M. Feder, N. Merhav and M. Gutman, "Universal Prediction of Individual Sequences," IEEE Transactions on Information Theory IT-38 (July 1992), 1258-1270.

Google Scholar

[11]

A. Fiat, It. M. Karp, M. Luby, L. A. McGeoch, q. D. Sleator and N. E. Young, "On Competitive Algorithms for Paging Problems," 3ournM of Algorithms 12 (1991), 685-699.

Digital Library

Google Scholar

[12]

R. G. Gallager, information Theory and Reh'able Communication, Wiley, 1968.

Digital Library

Google Scholar

[13]

T. Hagerup, K. Mehlhorn and I. Munro, "Optimal Algorithms for Generating Discrete Random Variables with Changing Distributions," Max Planck Institute, Technical Report MPI-I-92-145, October 15, 1992.

Google Scholar

[14]

J. F. Hannan, "Approximation to Bayes Risk in Repeated Plays," Contributions to the Theory of Games, Vol 3, Annals of MathematicM Studies (1957), 97-139.

Google Scholar

[15]

P. G. Howard and J. S. Vitter, "Analysis of Arithmetic Coding for Data Compression," Information Processing and Management 28 (1992), 749-763, invited paper in special issue on data compression for images and texts.

Digital Library

Google Scholar

[16]

S. Irani, A. R. Karlin and S. Phillips, "Strongly Competitive Algorithms for Paging with Locality of Reference," Proceedings of the 3rd Annum ACM- SIAM Symposium of Discrete Algorithms (January 1992).

Digital Library

Google Scholar

[17]

A. R. Karlin, S. J. Phillips and P. Raghavan, "Markov Paging," Proceedings of the 33rd Annum IEEE Conference on Foundations of Computer Science(October 1992), 208-217.

Google Scholar

[18]

D. Knuth, The Art of Computer Programming, Volume 2: SeminumericM Algorithms, Addison- Wesley, Reading, MA, second edition 1981.

Digital Library

Google Scholar

[19]

P. Krishnan and J. S. Vitter, "Optimal Prefetching in the Worst Case," Duke University Technical Report CS-1993-26, October 1993.

Digital Library

Google Scholar

[20]

G. G. Langdon, "A note on the Ziv-Lempel model for compressing individual sequences," IEEE Transactions on Information Theory 29(March 1983), 284-287.

Google Scholar

[21]

Y. Matins, J. S. Vitter and W. C. Ni, "Dynamic Generation of Discrete Random Vaxiates," Proceedings of the 4th Annum SIAM/ACM Symposium on Discrete Algorithms (January 1993.).

Digital Library

Google Scholar

[22]

L. A. McGeoch and D. D. Sleator, "A Strongly Competitive Randomized Paging Algorithm," Carnegie-Mellon University, CS-89-122, March 1989.

Google Scholar

[23]

N. Merhav and M. Feder, "Universal Sequential Learning and Decision from Individual Data Sequences," Proceedings of the 5th ACM Workshop on ComputationM Learning Theory (July 1992), .

Digital Library

Google Scholar

[24]

T. C. Mowry, M. S. Lrtm and A. Gupt~, "Design and Evaluation of a Compiler Algorithm for Prefetching," Proceedings of the Fifth InternationM Conference on ArchitecturM Support for Programming Languages and Operating Systems (October 1992).

Digital Library

Google Scholar

[25]

A. Rogers and K. Li, "Software Support for Speculative Loads," Proceedings of the Fifth InternationM Conference on ArchitecturM Support for Programming Languages and Operating Systems (October 1992).

Digital Library

Google Scholar

[26]

G. S. Shedler and C. Tung, "Locality in Page Reference Strings," SIAM JournM on Computing 1 (1972), 218-241.

Google Scholar

[27]

D. D. Sleator and ft. E. Tarjan, "Amortized Efficiency of List Update and Paging Rules," Communications of the A CM 28 (February 1985), 202-208.

Digital Library

Google Scholar

[28]

J. S. Vitter and P. Krishnan, "Optimal Prefetching via Data Compression," Proceedings of the 32nd Annum IEEE Symposium on Foundations of Computer Science(October 1991), 121-130, Also appears as Brown University Technical Report No. CS-91-46.

Digital Library

Google Scholar

[29]

J. Ziv and A. Lempel, "Compression of Individual Sequences via Variable-Rate Coding," IEEE Transactions on Information Theory 24 (September 1978), 530-536.

Google Scholar

Cited By

View all

Albers SGarg NLeonardi SVitter J(1998)Minimizing stall time in single and parallel disk systemsProceedings of the thirtieth annual ACM symposium on Theory of computing10.1145/276698.276858(454-462)Online publication date: 23-May-1998
https://dl.acm.org/doi/10.1145/276698.276858
Chen ICoffey JMudge T(1996)Analysis of branch prediction via data compressionACM SIGPLAN Notices10.1145/248209.23717131:9(128-137)Online publication date: 1-Sep-1996
https://dl.acm.org/doi/10.1145/248209.237171
Chen ICoffey JMudge T(1996)Analysis of branch prediction via data compressionACM SIGOPS Operating Systems Review10.1145/248208.23717130:5(128-137)Online publication date: 1-Sep-1996
https://dl.acm.org/doi/10.1145/248208.237171
Show More Cited By

Index Terms

Optimal prediction for prefetching in the worst case

Recommendations

Optimal Worst Case Formulas Comparing Cache Memory Associativity

In this paper we derive a worst case formula comparing the number of cache hits for two different cache memories. From this various other bounds for cache memory performance may be derived.

Consider an arbitrary program P which is to be executed on a ...
Analyzing the worst-case execution time for instruction caches with prefetching

Time predictability is one of the most important design considerations for real-time systems. In this article, we study the impact of instruction prefetching on the worst-case performance of instruction caches. We extend the static cache simulation ...
Optimal Prediction for Prefetching in the Worst Case

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '94: Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms

January 1994

735 pages

ISBN:0898713293

Chairman:
Daniel D. Sleator

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 1994

Check for updates

Qualifiers

Article

Conference

SODA94

Sponsor:

SIGACT
SIAM

SODA94: Conference on Discrete Algorithms

January 23 - 25, 1994

Virginia, Arlington, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
290
Total Downloads

Downloads (Last 12 months)49
Downloads (Last 6 weeks)4

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Albers SGarg NLeonardi SVitter J(1998)Minimizing stall time in single and parallel disk systemsProceedings of the thirtieth annual ACM symposium on Theory of computing10.1145/276698.276858(454-462)Online publication date: 23-May-1998
https://dl.acm.org/doi/10.1145/276698.276858
Chen ICoffey JMudge T(1996)Analysis of branch prediction via data compressionACM SIGPLAN Notices10.1145/248209.23717131:9(128-137)Online publication date: 1-Sep-1996
https://dl.acm.org/doi/10.1145/248209.237171
Chen ICoffey JMudge T(1996)Analysis of branch prediction via data compressionACM SIGOPS Operating Systems Review10.1145/248208.23717130:5(128-137)Online publication date: 1-Sep-1996
https://dl.acm.org/doi/10.1145/248208.237171
Chen ICoffey JMudge TDally BEggets S(1996)Analysis of branch prediction via data compressionProceedings of the seventh international conference on Architectural support for programming languages and operating systems10.1145/237090.237171(128-137)Online publication date: 1-Oct-1996
https://dl.acm.org/doi/10.1145/237090.237171

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Optimal Worst Case Formulas Comparing Cache Memory Associativity

Analyzing the worst-case execution time for instruction caches with prefetching

Optimal Prediction for Prefetching in the Worst Case