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. 1 Beckenbach, E. (Ed.). Applied Combinatorial Mathematics. Wiley, New York, 1964.]]
2. 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. 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. 4 Burnett, G.J. Performance analysis of interleaved memory systems. Ph.D. Th., Princeton U., Princeton, N.J., 1970.]]
5. 5 Burnett, G.J., and Coffman, E.G., Jr. A combinatorial problem related to interleaved systems. J.ACM 20, 1, (Jan. 1973), 39-45.]]
6. 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.]]
7. 7 Chewning, D. Multiprocessor memory interference. Unpublished report, Dep. of Electrical Engineering, Stanford U., Stanford, Calif. April 1973.]]
8. 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. 9 Conti, C.J. Concepts for buffer storage. IEEE Computer Group News (March 1969), 9-13.]]
10. 10 Cox, D.R., and Lewis, P.A.W. The Statistical Analysis of Series of Events. Methuen and Col, London, 1966.]]
11. 11 Cox, D.R., and Smith, W.L. Queues. Chapman and Hall, London, 1961.]]
12. 12 Feller, W. An Introduction to Probability Theory and Its Applications, Vol. I. Wiley, New York, 1968.]]
13. 13 Firestone, R.M. Parallel programming: operational model and detection of parallelism. Ph.D. Th., New York U., May 1971.]]
14. 14 Flores, I. Derivation of a waiting time factor for a multiple bank memory. J. ACM 11, 3 (July 1964), 265-282.]]
15. 15 Flynn, M.J. Some computer organizations and their effectiveness. IEEE Trans. on Comp. C-21, 9 (Sept. 1972), 948-960.]]
16. 16 Gordon, W.J., and Newell, G.S. Closed queueing systems with exponential servers. Op. Res. 15 (1967), 254-265.]]
17. 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. 18 Jackson, J.R. Jobshop-like queueing systems. Management Sci. 10, 1 (Oct. 1963), 131-142.]]
19. 19 Madnick, S. Multiprocessor software lockout. Proc. 1968 ACM National Conf., Las Vegas, Aug. 1968, pp. 19-24.]]
20. 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.]]
21. 21 Saaty, T.L. Elements of Queueing Theory. McGraw-Hill, New York, 1961.]]
22. 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. 23 Singleton, R.C. On computing the fast Fourier transform. Comm. ACM 10, 10 (Oct. 1967), 647-654.]]
24. 24 Skinner, C.E., and Asher, J. Effects of storage contention on system performance, IBM Sys. J. 4 (1969), 319-333.]]
25. 25 Strecker, W.D. Analysis of the instruction execution rate in certain computer structures, Ph.D. Th., Carnegie Mellon U., Pittsburgh, Pa., 1970.]]
26. 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.]]