Interference in multiprocessor computer systems with interleaved memory

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.

REFERENCES

• 1: Beckenbach, E. (Ed.). Applied Combinatorial Mathematics. Wiley, New York, 1964.
• 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.
• 3: Budnik, P., and Kuck, D. The organization and use of parallel memories. IEEE Trans. on Comp. C-20, 12 (Dec. 1971), 1566-1569.
• 4: Burnett, G.J. Performance analysis of interleaved memory systems. Ph.D. Th., Princeton U., Princeton, N.J., 1970.
• 5: G. J. Burnett , E. G. Coffman, Jr., A Combinatorial Problem Related to Interleaved Memory Systems, Journal of the ACM (JACM), v.20 n.1, p.39-45, Jan. 1973 [doi>10.1145/321738.321742]
• 6: 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 [doi>10.1145/360666.360668]
• 7: Chewning, D. Multiprocessor memory interference. Unpublished report, Dep. of Electrical Engineering, Stanford U., Stanford, Calif. April 1973.
• 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.
• 9: Conti, C.J. Concepts for buffer storage. IEEE Computer Group News (March 1969), 9-13.
• 10: Cox, D.R., and Lewis, P.A.W. The Statistical Analysis of Series of Events. Methuen and Col, London, 1966.
• 11: Cox, D.R., and Smith, W.L. Queues. Chapman and Hall, London, 1961.
• 12: Feller, W. An Introduction to Probability Theory and Its Applications, Vol. I. Wiley, New York, 1968.
• 13: Roger Morris Firestone, Parallel programming: operational model and detection of parallelism, 1971
• 14: Ivan Flores, Derivation of a Waiting-Time Factor for a Multiple-Bank Memory, Journal of the ACM (JACM), v.11 n.3, p.265-282, July 1964 [doi>10.1145/321229.321231]
• 15: Flynn, M.J. Some computer organizations and their effectiveness. IEEE Trans. on Comp. C-21, 9 (Sept. 1972), 948-960.
• 16: Gordon, W.J., and Newell, G.S. Closed queueing systems with exponential servers. Op. Res. 15 (1967), 254-265.
• 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.
• 18: Jackson, J.R. Jobshop-like queueing systems. Management Sci. 10, 1 (Oct. 1963), 131-142.
• 19: Stuart E. Madnick, Multi-processor software lockout, Proceedings of the 1968 23rd ACM national conference, p.19-24, August 27-29, 1968 [doi>10.1145/800186.810561]
• 20: Richard R. Muntz , Forest Baskett, III, Open, closed, and mixed networks of queues with different classes of customers., Stanford University, Stanford, CA, 1972
• 21: Saaty, T.L. Elements of Queueing Theory. McGraw-Hill, New York, 1961.
• 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.
• 23: Richard C. Singleton, On computing the fast Fourier transform, Communications of the ACM, v.10 n.10, p.647-654, Oct. 1967 [doi>10.1145/363717.363771]
• 24: Skinner, C.E., and Asher, J. Effects of storage contention on system performance, IBM Sys. J. 4 (1969), 319-333.
• 25: William Daniel Strecker, An analysis of the instruction execution rate in certain computer structures, 1970
• 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.

INDEX TERMS

Keywords:
interleaved memory, memory, memory interference, multiprocessing, trace driven simulation