Article

On-line restricted caching

Authors:

Richard Enbody,

Stephen WagnerAuthors Info & Claims

SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms

Pages 374 - 383

Published: 09 January 2001 Publication History

Abstract

We study the on-line caching problem in a restricted cache where each memory item can be placed in only a restricted subset of cache locations. Examples of restricted caches in practice include victim caches, assist caches, and skew caches. To the best of our knowledge, all previous on-line caching studies have considered on-line caching in identical or fully-associative caches where every memory item can be placed in any cache location.

In this paper, we focus on companion caches, a simple restricted cache that includes victim caches and assist caches as special cases. Our results show that restricted caches are significantly more complex than identical caches. For example, we show that the commonly studied Least Recently Used (LRU) algorithm is not competitive unless cache reorganization is allowed while the performance of the First In First Out (FIFO) algorithm is competitive but not optimal. We then present two near optimal algorithms for this problem as well as some lower bound arguments.

References

[1]

E.A. Arkin and E.B Silverberg. Scheduling jobs with fixed start and end times. Discrete Applied Mathematics, 18:1-8, 1987.

Digital Library

[2]

L. A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2):282-288, 1966.

[3]

A. Borodin, S. Irani, P. Raghavan, and B. Schieber. Competitive paging with locality of reference. In Proceedings of 23rd A CM Syrup. on Theory of Computing, pages 249-259, 1991.

Digital Library

[4]

Mark Brehob, Stephen Wagner, Eric Torng, and Richard Enbody. Optimal replacement is nphard for non-standard caches. Technical Report MSU-CSE-00ol4, Department of Computer Science, Michigan State University, East Lansing, Michigan, June 2000.

[5]

K.K. Chan, C.C. Hay, J.R. Keller, G.P.Kurpanek, F.X. Schumacher, and J.Zheng. Design of the hp pa7200. Hewlett-Packard Journal, February 1996.

[6]

A. Fiat and A. Karlin. Randomized and multipointer paging with locality of reference. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, pages 626- 634, 1995.

Digital Library

[7]

A. Fiat, R. Karp, M. Luby, L. McGeoch, D. Sleator, and N. Young. Competitive paging algorithms. Journal of Algorithms, 12:685-699, 1991.

Digital Library

[8]

A. Fiat and Z. Rosen. Experimental studies of access graph based heuristics: Beating the LRU standard? In Proc. 8th Annual ACM- SIAM Syrup. on Discrete Algorithms, pages 63- 72, 1997.

Digital Library

[9]

S.S. Irani, A.R. Karlin, and S.J. Phillips. Strongly competitive algorithms for paging with locality of reference. In Third A CM-SIAM Symposium on Discrete Algorithms, pages 228-236, 1992.

Digital Library

[10]

N. Jouppi. Improving direct-mapped cache performance by the addition of a small fullyassociative cache and prefetch buffers. Proceedings of the Seventeenth Annual International Symposium on Computer Architecture, 18(2):364-373, May 1990.

Digital Library

[11]

Antoon W.J. Kolen and Jeo G Kroon. On the computation complexity of (maximum) class scheduling. European Journal of Operational Research, 54:23-38, 1991.

[12]

C. Lund, S. Phillips, and N. Reingold. IP over connection-oriented networks and distributional paging. In Proceedings of the 35th Annual IEEE Foundations of Computer Science, pages 424- 434, 1994.

[13]

L.L. McGeoch and D.D. Sleator. A strongly competitive randomized paging algorithm. AI- gorithmica, 6:816-825, 1991.

[14]

A. Seznec. A case for two-way skewedassociative caches. Proceedings of the 20th International Symposium on Computer Architecture, pages 169--178, 1993.

Digital Library

[15]

D.D. Sleator and R.E. Tarjan. Amortized efficiency of list update and paging rules. CACM, 28:202-208, 1985.

Digital Library

[16]

Edward S. Tam, Jude A. Rivers, Vijayalakshmi Srinivasan, Gary S. Tyson, and Edward S. Davidson. Active management of data caches by exploiting reuse information. IEEE Trans. on Computers, 48(11), November 1999.

Digital Library

[17]

E. Torng. A unified analysis of paging and caching. Algorithmica, 20:175-200, 1998.

Cited By

Bender MBhattacharjee AConway AFarach-Colton MJohnson RKannan SKuszmaul WMukherjee NPorter DTagliavini GVorobyeva JWest EAgrawal KAzar Y(2021)Paging and the Address-Translation ProblemProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461814(105-117)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461814
Peserico E(2003)Online paging with arbitrary associativityProceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/644108.644202(555-564)Online publication date: 12-Jan-2003
https://dl.acm.org/doi/10.5555/644108.644202

Recommendations

On-line restricted caching
Special issue: On-line algorithm part I

We study the on-line caching problem in a restricted cache where each memory item can be placed in only a restricted subset of cache locations. Examples of restricted caches in practice include victim caches, assist caches, and skew caches. To the best ...
Selective Victim Caching: A Method to Improve the Performance of Direct-Mapped Caches

Although direct-mapped caches suffer from higher miss ratios as compared to set-associative caches, they are attractive for today's high-speed pipelined processors that require very low access times. Victim caching was proposed by Jouppi [1] as an ...
Cooperative Caching for GPUs

The rise of general-purpose computing on GPUs has influenced architectural innovation on them. The introduction of an on-chip cache hierarchy is one such innovation. High L1 miss rates on GPUs, however, indicate inefficient cache usage due to myriad ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms

January 2001

937 pages

ISBN:0898714907

Chairman:
S. Rao Kosaraju

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM: Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 09 January 2001

Check for updates

Qualifiers

Article

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
200
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bender MBhattacharjee AConway AFarach-Colton MJohnson RKannan SKuszmaul WMukherjee NPorter DTagliavini GVorobyeva JWest EAgrawal KAzar Y(2021)Paging and the Address-Translation ProblemProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461814(105-117)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461814
Peserico E(2003)Online paging with arbitrary associativityProceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/644108.644202(555-564)Online publication date: 12-Jan-2003
https://dl.acm.org/doi/10.5555/644108.644202

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten