Abstract
This paper analyzes the memory interference caused by several processors simultaneously using several memory modules. Exact results are computed for a simple model of such a system. The limiting value is derived for the relative degree of memory interference as the system size increases. The model of the limiting behavior of the system yields approximate results for the simple model and also suggests that the results are valid for a much larger class of models, including those more nearly like real systems than the simple model. The assumptions and results of the simple model are tested against some measurements of program behavior and simulations of systems using memory references from real programs. The model results provide a good indication of the performance that should be expected from real systems of this type.
- 1 Beckenbach, E. (Ed.). Applied Combinatorial Mathematics. Wiley, New York, 1964.]]Google Scholar
- 2 Bhandarkar, D.P., and Fuller, S.H. A survey of techniques for analyzing memory interference in multi-processor systems. Tech. Rep., Carnegie-Mellon U., Pittsburgh, Pa., April 1973.]]Google Scholar
- 3 Budnik, P., and Kuck, D. The organization and use of parallel memories. IEEE Trans. on Comp. C-20, 12 (Dec. 1971), 1566-1569.]]Google ScholarDigital Library
- 4 Burnett, G.J. Performance analysis of interleaved memory systems. Ph.D. Th., Princeton U., Princeton, N.J., 1970.]]Google Scholar
- 5 Burnett, G.J., and Coffman, E.G., Jr. A combinatorial problem related to interleaved systems. J.ACM 20, 1, (Jan. 1973), 39-45.]] Google ScholarDigital Library
- 6 Burnett, G.J., and Coffman, E.G., Jr., Analysis of interleaved memory systems using blockage buffers. Comm. ACM, 18, 2 (Feb. 1975), 91-95.]] Google ScholarDigital Library
- 7 Chewning, D. Multiprocessor memory interference. Unpublished report, Dep. of Electrical Engineering, Stanford U., Stanford, Calif. April 1973.]]Google Scholar
- 8 Coffman, E.G., Jr., Burnett, G.J., and Snowdon, R.A. On the performance of interleaved memories with multiple word bandwidths. IEEE Trans. on Comp. C-20, 12 (Dec. 1971), 1566- 1569.]]Google Scholar
- 9 Conti, C.J. Concepts for buffer storage. IEEE Computer Group News (March 1969), 9-13.]]Google Scholar
- 10 Cox, D.R., and Lewis, P.A.W. The Statistical Analysis of Series of Events. Methuen and Col, London, 1966.]]Google ScholarCross Ref
- 11 Cox, D.R., and Smith, W.L. Queues. Chapman and Hall, London, 1961.]]Google Scholar
- 12 Feller, W. An Introduction to Probability Theory and Its Applications, Vol. I. Wiley, New York, 1968.]]Google Scholar
- 13 Firestone, R.M. Parallel programming: operational model and detection of parallelism. Ph.D. Th., New York U., May 1971.]] Google ScholarDigital Library
- 14 Flores, I. Derivation of a waiting time factor for a multiple bank memory. J. ACM 11, 3 (July 1964), 265-282.]] Google ScholarDigital Library
- 15 Flynn, M.J. Some computer organizations and their effectiveness. IEEE Trans. on Comp. C-21, 9 (Sept. 1972), 948-960.]]Google ScholarDigital Library
- 16 Gordon, W.J., and Newell, G.S. Closed queueing systems with exponential servers. Op. Res. 15 (1967), 254-265.]]Google ScholarDigital Library
- 17 Heart, F.E., Ornstein, S.M., Crowther, W.R., and Barker, W.B. A new minicomputer/multiprocessor for the ARPA network. AFIPS Conf. Proc., Vol. 42, 1973 SJCC, AFIPS Press, Montvale, N.J., 1973, pp. 529-537.]]Google ScholarDigital Library
- 18 Jackson, J.R. Jobshop-like queueing systems. Management Sci. 10, 1 (Oct. 1963), 131-142.]] Google ScholarDigital Library
- 19 Madnick, S. Multiprocessor software lockout. Proc. 1968 ACM National Conf., Las Vegas, Aug. 1968, pp. 19-24.]] Google ScholarDigital Library
- 20 Muntz, R.R., and Baskett, F. Open, closed, and mixed networks of queues with different classes of customers. Stanford Electronics Labs. Tech. Rep. No. 33, Stanford U., Stanford, Calif., Aug. 1972.]] Google ScholarDigital Library
- 21 Saaty, T.L. Elements of Queueing Theory. McGraw-Hill, New York, 1961.]]Google Scholar
- 22 Sekino, A. Performance evaluation of multiprogrammed time-shared computer systems, Ph.D. Th., Project MAC Document MAC TR-103, MIT, Cambridge, Mass., Sept. 1972.]]Google Scholar
- 23 Singleton, R.C. On computing the fast Fourier transform. Comm. ACM 10, 10 (Oct. 1967), 647-654.]] Google ScholarDigital Library
- 24 Skinner, C.E., and Asher, J. Effects of storage contention on system performance, IBM Sys. J. 4 (1969), 319-333.]]Google ScholarDigital Library
- 25 Strecker, W.D. Analysis of the instruction execution rate in certain computer structures, Ph.D. Th., Carnegie Mellon U., Pittsburgh, Pa., 1970.]] Google ScholarDigital Library
- 26 Wulff, W., and Bell, C.G.C.mmp, a multi-mini-processor, AFIPS Conf. Proc., Vol. 41, part II, 1972 FJCC, AFIPS Press, Montvale, N.J., pp. 765-777.]]Google Scholar
Recommendations
Interleaved Memory Bandwidth in a Model of a Multiprocessor Computer System
An approximate analysis is performed of an often studied model of an interleaved memory, multiprocessor system consisting of M memory modules and N processors. A closed-form solution is obtained and the one approximation used is found to result in ...
Multiprocessor memory organization and memory interference
ture of shared memory in a multiprocessor computer system is examined with particular attention to noninterleaved memory. Alternative memory organizations are compared and it is shown that a home memory organization, in which each processor is ...
Reducing Interference Among Vector Accesses in Interleaved Memories
Memory interference occurs when two or more concurrent data requests are addressed to the same main memory bank. In vector superconductors, this problem is serious due to the periodic interaction among vectors accesses, and can significantly reduce ...
Comments