Empirical investigation of the Markov reference model

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Empirical investigation of the Markov reference model

Full text

Pdf (1.23 MB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland, United States

Pages: 653 - 662

Year of Publication: 1999

ISBN:0-89871-434-6

Author

Vincenzo Liberatore

UMIACS, A. V. Williams Building, University of Maryland, College Park, MD

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 Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 14, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

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

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	A. Aggarwal , B. Alpern , A. Chandra , M. Snir, A model for hierarchical memory, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.305-314, January 1987, New York, New York, United States [doi>10.1145/28395.28428]
	2	Alfred V. Aho , Peter J. Denning , Jeffrey D. Ullman, Principles of Optimal Page Replacement, Journal of the ACM (JACM), v.18 n.1, p.80-93, Jan. 1971 [doi>10.1145/321623.321632]
	3	Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
	4	David Callahan , Ken Kennedy , Allan Porterfield, Software prefetching, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.40-52, April 08-11, 1991, Santa Clara, California, United States
	5	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
	6	Marek Chrobak , John Noga, Competitive algorithms for multilevel caching and relaxed list update, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.87-96, January 25-27, 1998, San Francisco, California, United States
	7	W. G. Cochran. Some methods for strengthening the X2 tests. Biometrics, 10:417--451, 1954.
	8	Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
	9	P. J. Courtois, Decomposability, instabilities, and saturation in multiprogramming systems, Communications of the ACM, v.18 n.7, p.371-377, July 1975 [doi>10.1145/360881.360887]
	10	P. J. Curtois and H. Vaatilborgh. A decomposable model of program paging behavior. Acta Inforrnatica, 6(3):251-276, 1976.
	11	P. J. Denning, K. C. Khan, J. Leroudier, D. Poitier, and R. Suri. Optimal multiprogramming. Acta Information, 7(2):197-216, 1976.
	12	Peter J. Denning. Working sets: Past and present. IEEE Transactions on Software Engineering, SE- 6(1):64-84, January 1980.
	13	J. Eichenauer and J. Lehn. A non-linear congruential pseudo razidom number generator. Statist. Papers, 27:315-326, 1986.
	14	Juergen Eichensuer-Herrman. inversive congruential pseudorandom numbers: a tutorial. International Statistical Review, 60(2):167-176, August 1992.
	15	Juergen Eichenauer-Herrman. Pseudorandom number generation by nonlineax methods. International Statistical Review, 63(2):247-255, August 1995.
	16	William Feller. An Introduction to Probability Theory and Its Applications. Wiley, 1967.
	17	Domenico Ferrari. Program behavior. Computer, 9(11):7-8, November 1976.
	18	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
	19	Joseph A. Fisher. Trace scheduling: A technique for global microcode compaction. IEEE Transactions on Computers, C,-30(7):478--490, July 1981.
	20	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]
	21	M. A. Franklin , R. K. Gupta, Computation of page fault probability from program transition diagram, Communications of the ACM, v.17 n.4, p.186-191, April 1974 [doi>10.1145/360924.360928]
	22	Michael Franklin , Stanley Zdonik, A framework for scalable dissemination-based systems, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.94-105, October 05-09, 1997, Atlanta, Georgia, United States
	23	Michael J. Franklin, Client Data Caching: A Foundation for High Performance Object Database Systems, Kluwer Academic Publishers, Norwell, MA, 1996
	24	David Freedman. Markov chains. Springer-Verlag, 1983.
	25	Solomon W. Golomb , Robert E. Peile , Robert A. Scholtz, Basic concepts in information theory and coding: the adventures of secret agent 00111, Plenum Press, New York, NY, 1994
	26	John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
	27	Sandy Irani , Anna R. Karlin , Steven Phillips, Strongly Competitive Algorithms for Paging with Locality of Reference, SIAM Journal on Computing, v.25 n.3, p.477-497, June 1996 [doi>10.1137/S0097539792236353]
	28	Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel D. Sleator. Competitive snoopy caching. Algorithmica, 3(1):79-119, 1988.
	29	Anna K. Karlin, Steven J. Phillips, and Prabhakar Raghavan. Markov paging. In Proceedings of the 38rd Annual Symposium on Foundations of Computer Science, pages 208-217, 1992.
	30	Sanjeev Khanna , Vincenzo Liberatore, On broadcast disk paging, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.634-643, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276879]
	31	Hannes Leeb , Stefan Wegenkittl, Inversive and linear congruential pseudorandom number generators in empirical tests, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.2, p.272-286, April 1997 [doi>10.1145/249204.249208]
	32	Tara M. Madhyastha , Daniel A. Reed, Input/output access pattern classification using hidden Markov models, Proceedings of the fifth workshop on I/O in parallel and distributed systems, p.57-67, November 17-17, 1997, San Jose, California, United States [doi>10.1145/266220.266226]
	33	Glen McPherson. Statistics in Scientific Investigation. Springer-Verlag, New York, 1990.
	34	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
	35	Steven A. Przybylski, Cache and memory hierarchy design: a performance-directed approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
	36	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
	37	Ziv Rosen. Access graph based heuristics for online p#g algorithms. Master's thesis, Tel-Aviv University, December 1996.
	38	Sidney Siegel. Nonparametric Statistics for the Behav. ioral Sciences. McGraw-Hill, New York, 1956.
	39	Alan Jay Smith. Analysis of the optimal, lookahead, demand paging algorithms. SIAM Journal on Computing, 5(4):743--757, December 1976.
	40	Alan J#y Smith. Sequential program prefetching in memory hierarchies. Computer, 11(12):7-21, December 1978.
	41	Jeffrey R. Spirn, Program Behavior: Models and Measurements, Elsevier Science Inc., New York, NY, 1977
	42	Andrew S. Tanenbaum, Modern operating systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
	43	Dean M. Tullsen , Susan J. Eggers, Limitations of cache prefetching on a bus-based multiprocessor, Proceedings of the 20th annual international symposium on Computer architecture, p.278-288, May 16-19, 1993, San Diego, California, United States
	44	Jeffrey Scott Vitter , P. Krishnan, Optimal prefetching via data compression, Journal of the ACM (JACM), v.43 n.5, p.771-793, Sept. 1996 [doi>10.1145/234752.234753]
	45	Neal Young. The K-server dual and loose competitivehess for paging. Algorithmic, a, 11(6):525--541, 1994.
	46	J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3):337-343, 1977.

CITED BY 2

	Vincenzo Liberatore, Caching and Scheduling for Broadcast Disk Systems, Journal of Experimental Algorithmics (JEA), 6, p.5-es, 2001
	Vincenzo Liberatore, Circular arrangements and cyclic broadcast scheduling, Journal of Algorithms, v.51 n.2, p.185-215, May 2004