Competitive paging with locality of reference

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Competitive paging with locality of reference

Full text

Pdf (1.17 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 249 - 259

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Allan Borodin	Department of Computer Science, University of Toronto
Prabhakar Raghavan	IBM T.J. Watson Research Center, Yorktown Heights, NY
Sandy Irani	Computer Science Division, UC Berkeley
Baruch Schieber	IBM T.J. Watson Research Center, Yorktown Heights, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 21, Citation Count: 18

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/103418.103422 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L.A. Belady. A study of replacement algorithms for virtual storage computers. IBM Systems Journal, 5:78-101, 1966.
	2	S. Ben-David , A. Borodin , R. Karp , G. Tardos , A. Wigderson, On the power of randomization in online algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.379-386, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100268]
	3	A. Borodin , N. Linial , M. Saks, An optimal online algorithm for metrical task systems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.373-382, January 1987, New York, New York, United States [doi>10.1145/28395.28435]
	4	P.:I. Denning. Working sets past and present. IEEE Trans. Software Engg., SE-6:64-84, 1980.
	5	D. Ferrari. The improvement of program behavior. IEEE Computer, 9'39-47, November 1976.
	6	A. Fiat, R. Karp, M. Luby, L. McGeoch, D. Sleator, and N. Young. On competitive algorithms for paging problems. To appear in Journal of Algorithms, 1991.
	7	P. A. Franaszek , T. J. Wagner, Some Distribution-Free Aspects of Paging Algorithm Performance, Journal of the ACM (JACM), v.21 n.1, p.31-39, Jan. 1974 [doi>10.1145/321796.321800]
	8	D. Hatfield and J. Gerald. Program restructuring for virtual memory. IBM J. Syst. and Tech., 10:168-192, 1971.
	9	W.C. Hobart, Jr. and H.G. Cragon. Locality characteristics of symbolic programs. In IEEE Inlernational Conference on Compute.r Design: VLSI in Computers and Processors, pages 508- 511, 1989.
	10	A. R. Karlin, M. S. Manasse, L. Rudolph, and D.D. Sleator. Competitive snoopy cac, hing. Algorithmica, 3(1):70-119, 1988.
	11	T. Kilburn, D.B.G. Edwards, M.J. Lanigan, and F.H. Sumner. One-level storage system. IRE Trans. Elect. Computers, 37:223-235, 1962.
	12	A. Lempel, S. Even, and I. Cederbaurn. An algorithm for planarity testing of graphs. In Proc. Int. Syrup. on Theory of Graphs; P. Rosenstiehl Ed., pages 215-232. Gordon and Breach, 1967.
	13	P.A.W. Lewis and G.S. Shedler. Empirically derived models for sequences of page exceptions. IBM J. Res. and Develop., 17:86-100, {973.
	14	Mark S. Manasse , Lyle A. McGeoch , Daniel D. Sleator, Competitive algorithms for server problems, Journal of Algorithms, v.11 n.2, p.208-230, Jun. 1990 [doi>10.1016/0196-6774(90)90003-W]
	15	L.A. McGeoch and D.D. Sleator. A strongly competitive randomized paging algorithm. Technical Report CMU-CS-89-122, Carnegie-Mellon University, Pittsburgh, PA, 1989. Submitted to Algorithmica.
	16	L.A. McGeoch, D.D. Sleator, and C. Tomasi. Decision procedures for competitive algorithms. In preparation.
	17	Prabhakar Raghavan , Marc Snir, Memory Versus Randomization in On-line Algorithms (Extended Abstract), Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.687-703, July 11-15, 1989
	18	G.S. Shedler and C. Tung. Locality in page reference strings. SIAM Journal on Compuling, 1:218-241, 1972.
	19	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]
	20	Jeffrey R. Spirn, Program Behavior: Models and Measurements, Elsevier Science Inc., New York, NY, 1977
	21	Neal Young, On-line caching as cache size varies, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 28-30, 1991, San Francisco, California, United States

CITED BY 18

	Marshall Bern , Daniel Greene , Arvind Raghunathan, On-line algorithms for cache sharing, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.422-430, May 16-18, 1993, San Diego, California, United States
	Jeffrey Scott Vitter , P. Krishnan, Optimal prefetching via data compression, Journal of the ACM (JACM), v.43 n.5, p.771-793, Sept. 1996
	Susanne Albers , Stefano Leonardi, On-line algorithms, ACM Computing Surveys (CSUR), v.31 n.3es, Sept. 1999
	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
	Mark H. Nodine , Michael T. Goodrich , Jeffrey Scott Vitter, Blocking for external graph searching, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.222-232, May 25-28, 1993, Washington, D.C., United States
	Amos Fiat , Anna R. Karlin, Randomized and multipointer paging with locality of reference, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.626-634, May 29-June 01, 1995, Las Vegas, Nevada, United States
	William R. Burley , Sandy Irani, On algorithm design for metrical task systems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.420-429, January 22-24, 1995, San Francisco, California, United States
	Gideon Glass , Pei Cao, Adaptive page replacement based on memory reference behavior, ACM SIGMETRICS Performance Evaluation Review, v.25 n.1, p.115-126, June 1997
	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
	Amos Fiat , Ziv Rosen, Experimental studies of access graph based heuristics: beating the LRU standard?, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.63-72, January 05-07, 1997, New Orleans, Louisiana, United States
	Edith Cohen , Haim Kaplan, Exploiting regularities in Web traffic patterns for cache replacement, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.109-118, May 01-04, 1999, Atlanta, Georgia, United States
	Mark Brehob , Richard Enbody , Eric Torng , Stephen Wagner, On-line restricted caching, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.374-383, January 07-09, 2001, Washington, D.C., United States
	Andrew Chou , Jeremy Cooperstock , Ran El-Yaniv , Michael Klugerman , Tom Leighton, The statistical adversary allows optimal money-making trading strategies, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.467-476, January 22-24, 1995, San Francisco, California, United States
	Allan Borodin, Can competitive analysis be made competitive?, Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada
	Ben Juurlink, Approximating the optimal replacement algorithm, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy
	Ronny Lempel , Shlomo Moran, Competitive caching of query results in search engines, Theoretical Computer Science, v.324 n.2-3, p.253-271, 20 September 2004
	Mark Brehob , Richard Enbody , Eric Torng , Stephen Wagner, On-line restricted caching, Journal of Scheduling, v.6 n.2, p.149-166, March/April 2003
	Konstantinos Panagiotou , Alexander Souza, On adequate performance measures for paging, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Sequencing and scheduling

Additional Classification:
B. Hardware
B.3 MEMORY STRUCTURES
B.3.2 Design Styles
Subjects: Virtual memory
B.3.3 Performance Analysis and Design Aids**
Subjects: Formal models**

D. Software
D.4 OPERATING SYSTEMS
D.4.2 Storage Management

General Terms:
Algorithms, Performance, Theory

REVIEW

"Arvind Raghunathan : Reviewer"

Given some knowledge of a program's reference pattern, can we use it to improve the paging performance of the program? The authors address this question by considering access patterns dictated by locality of reference. They define an more...

Collaborative Colleagues:

Allan Borodin: colleagues

Prabhakar Raghavan: colleagues

Sandy Irani: colleagues

Baruch Schieber: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player