A Combinatorial Problem Related to Interleaved Memory Systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Combinatorial Problem Related to Interleaved Memory Systems

Full text

Pdf (353 KB)

Source

Journal of the ACM (JACM) archive
Volume 20 , Issue 1 (January 1973) table of contents

Pages: 39 - 45

Year of Publication: 1973

ISSN:0004-5411

Authors

G. J. Burnett	The Pennsylvania State University, Computer Science Department, University Park, Pennsylvania
E. G. Coffman, Jr.	The Pennsylvania State University, Computer Science Department, University Park, Pennsylvania

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 17, Citation Count: 7

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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/321738.321742 What is a DOI?

ABSTRACT

A combinatorial problem arising from the analysis of a model of interleaved memory systems is studied. The performance measure whose calculation defines this problem is based on the distribution of the number of modules in operation during a memory cycle, assuming saturated demand and an arbitrary but fixed number of modules. In general terms the problem is as follows. Suppose we have a Markov chain of n states numbered 0, 1, ···, n - 1. For each i assume that the one-step transition probability from state i to state (i + 1) mod n is given by the parameter &agr; and from state i to any other state is &bgr; = (1 - &agr;)/(n - 1). Given an initial state, the problem is to find the expected number of states through which the system passes before returning to a state previously entered. The principal result of the paper is a recursive procedure for computing this expected number of states. The complexity of the procedure is seen to be small enough to enable practical numerical studies of interleaved memory systems.

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	BURNETT, G. J, AND COFFMAN, E G JR. A study of interleaved memory systems. Proc" AFIPS 1970 SJCC, Vol. 36, AFIPS Press, Montvale, N. J., pp 467-474.
	2	HELLERMAN, H. Digital Computer System Pmnc~ple8 McGraw-Hill, New York, 1967
	3	BURNETT, G.J. Performance analysis of interleaved memory systems. Ph.D. Thesis, Elec. Eng. Dept., Princeton U., Princeton, N. J., Jan. 1970.

CITED BY 7

	Harold S. Stone, A note on a combinatorial problem of Burnett and Coffman, Communications of the ACM, v.17 n.3, p.165-166, March 1974
	Randy J. Raynor , John M. Gwynn, Jr., Minimization of supervisor conflict for multiprocessor computer systems, ACM SIGSIM Simulation Digest, v.7 n.4, p.61-69, July 1976
	Micha Hofri, Analysis of interleaved storage via a constant-service queuing system with Markov-chain-driven input, Journal of the ACM (JACM), v.31 n.3, p.628-648, July 1984
	G. J. Burnett , E. G. Coffman, Jr., Anaysis of interleaved memory systems using blockage buffers, Communications of the ACM, v.18 n.2, p.91-95, Feb. 1975
	Forest Baskett , Alan Jay Smith, Interference in multiprocessor computer systems with interleaved memory, Communications of the ACM, v.19 n.6, p.327-334, June 1976
	W. R. Franta , Philip A. Houle, Comments on models of multi-processor multi-memory bank computer systems, Proceedings of the 7th conference on Winter simulation, p.87-97, January 14-16, 1974, Washington, DC
	David J. Kuck, A Survey of Parallel Machine Organization and Programming, ACM Computing Surveys (CSUR), v.9 n.1, p.29-59, March 1977