Skip to main content

A simple characterization of provably efficient prefetching algorithms

Publication ,  Journal Article
Jin, W; Barve, RD; Trivedi, KS
Published in: Proceedings of the 2002 International Conference on Dependable Systems and Networks
December 1, 2002

In this paper, we characterize a broad class C of prefetching algorithms and prove that, for any prefetching algorithm in this class, its total elapsed time is no more than twice the smallest possible total elapsed time. This result provides a performance guarantee for several practical prefetching algorithms, which fall into this class and have no previously proven performance bound. Prefetching involves making two fundamental decisions: when to begin a prefetch operation and which page to replace. Provably optimal prefetching algorithms are rendered impractical because of complicated techniques to decide when to issue prefetches. However, a Class C algorithm only has to obey certain simple (previously known) guidelines governing these decisions. The performance guarantee for this class strongly relies on the optimal replacement requirement, and this suggests that more so than the decision of when to start prefetching the next missing page, the replacement decision remains the most important decision to be made in prefetching algorithms.

Duke Scholars

Published In

Proceedings of the 2002 International Conference on Dependable Systems and Networks

Publication Date

December 1, 2002

Start / End Page

571 / 580
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Jin, W., Barve, R. D., & Trivedi, K. S. (2002). A simple characterization of provably efficient prefetching algorithms. Proceedings of the 2002 International Conference on Dependable Systems and Networks, 571–580.
Jin, W., R. D. Barve, and K. S. Trivedi. “A simple characterization of provably efficient prefetching algorithms.” Proceedings of the 2002 International Conference on Dependable Systems and Networks, December 1, 2002, 571–80.
Jin W, Barve RD, Trivedi KS. A simple characterization of provably efficient prefetching algorithms. Proceedings of the 2002 International Conference on Dependable Systems and Networks. 2002 Dec 1;571–80.
Jin, W., et al. “A simple characterization of provably efficient prefetching algorithms.” Proceedings of the 2002 International Conference on Dependable Systems and Networks, Dec. 2002, pp. 571–80.
Jin W, Barve RD, Trivedi KS. A simple characterization of provably efficient prefetching algorithms. Proceedings of the 2002 International Conference on Dependable Systems and Networks. 2002 Dec 1;571–580.

Published In

Proceedings of the 2002 International Conference on Dependable Systems and Networks

Publication Date

December 1, 2002

Start / End Page

571 / 580