Probabilistic analysis of a crossbar switch

ABSTRACT

This paper presents a probabilistic analysis of a crossbar switch interconnection network. A crossbar switch can be used to interconnect various combinations of computer subsystems. In the analysis below it is assumed, without loss of generality, that the crossbar is being used to connect N processors to M memories. The crossbar is termed an N-M crossbar (read “N to M crossbar”). General expressions are developed for a variety of performance figures for an N-M crossbar including: the probability of a memory request being accepted (i.e. not being blocked by another request to the same memory), the expected bandwidth of the crossbar, and the average wait time of a request before it is accepted. Closed form solutions to these expressions are given for the uniform request case and for the favorite memory case (i.e. where processor i requests memory i with a higher probability than others memories). The closed form solutions are tested against simulations.

REFERENCES

• 1: 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 [doi>10.1145/360238.360243]
• 2: K. E. Batcher, "The flip network in STARAN," Proc. of the 1976 Int'l Conf. on Parallel Processing, August 1976, pp. 65-71.
• 3: V. E. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic, Academic Press, New York 1965.
• 4: D. P. Bhandarkar, "Analysis of Memory Interference in Multiprocessors," IEEE Trans. Computers, Vol. C-24, No. 9, September 1975, pp. 897-908.
• 5: F. A. Briggs, and E. S. Davidson, "Organization of Semiconductor Memories for Parallel-Pipelined Processors," IEEE Trans. Computers, Vol. C-26, No. 2 February 1977, pp. 162-169.
• 6: D. Chang, P.J. Kuck, and D. H. Lawrie, "On the Effective Bandwidth of Parallel Memories," IEEE Trans. Computers, Vol. C-26, No. 5 May 1977, pp. 480-490.
• 7: C. Clos, "A Study of Non-blocking Switching Networks," The Bell System Technical Journal, Vol. 32, March 1953, pp. 406-424.
• 8: T. Feng, "Data Manipulating Functions in Parallel Processes and their Implementations," IEEE Trans. Computers, Vol. C-23, No. 3, March 1974, pp. 309-318.
• 9: M. A. Franklin, "VLSI Performance Comparison of Banyan and Crossbar Connection Networks," in {Sie80}, pp. 20-28.
• 10: L. Rodney Goke , G. J. Lipovski, Banyan networks for partitioning multiprocessor systems, Proceedings of the 1st annual symposium on Computer architecture, p.21-28, December 09-11, 1973
• 11: C. H. Hoogendoorn, "A General Model for Memory Interference in Multiprocessors," IEEE Trans. Computers, Vol. C-26, No. 10, October 1977, pp. 998-1005.
• 12: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 13: D. H. Lawrie, "Access and Alignment of Data in an Array Processor," IEEE Trans. Computers, Vol. C-24, No. 18, December 1975, pp. 1145-1155.
• 14: G. J. Lipovski, M. Malek, "A Theory for Multicomputer Interconnection Networks" IEEE Trans. Computers, (to appear).
• 15: B. A. Makrucki, T. N. Mudge, VLSI Design of a Crossbar Switch, SEL Report No. 149, Department of Electrical and Computer Engineering, University of Michigan, January 1981.
• 16: B. A. Makrucki, T. N. Mudge, Probabilistic Analysis of a Crossbar Switch, SEL Report No. 150, Department of Electrical and Computer Engineering, University of Michigan, March 1981.
• 17: Janak H. Patel, Processor-memory interconnections for multiprocessors, Proceedings of the 6th annual symposium on Computer architecture, p.168-177, April 23-25, 1979 [doi>10.1145/800090.802906]
• 18: J. H. Patel, "Performance of Processor-Memory Interconnections for Multiprocessors," IEEE Trans. Computers, Vol. C-30, No. 10, October 1981, pp. 771-780.
• 19: M. C. Pease, "The Indirect Binary n-Cube Microprocessor Array," IEEE Trans. Computers, Vol. C-26, No. 5, May 1977, pp. 458-473.
• 20: N. Pippenger, "On Crossbar Switching Networks," IEEE Trans. Communications, Vol. COM-23, No. 6, June 1975, pp. 646-659.
• 21: C. V. Ravi, "On the Bandwidth and Interference in Interleaved Memory Systems," IEEE Trans. Computers, Vol. C-21, No. 8, August 1972, pp. 899-901.
• 22: B. R. Rau, "Interleaved Memory Bandwidth in a Model of a Multiprocessor Computer System," IEEE Trans. Computers, Vol. C-28, No. 9, September 1979, pp. 678-681.
• 23: A. S. Sethi, N. Deo, "Interference in Multiprocessor Systems with Localized Memory Access Probabilities," IEEE Trans. Computers, Vol. C-28, No. 2, pp. 157-163.
• 24: H. J. Siegel, (Ed.), Proceedings of the Workshop on Interconnection Networks, Purdue University, April 21-22, 1980.
• 25: H. J. Siegel, R. J. McMillen, "Using the Augmented Data Manipulator Network in PASM," Computer, Vol. 14, No. 2, February 1981, pp. 23-33.
• 26: H. J. Siegel, R. J. McMillen, "The Multistage Cube: A Versatile Interconnection Network," Computer, Vol. 14, No. 12, December 1981 (to appear).
• 27: Howard Jay Siegel , S. Diane Smith, Study of multistage SIMD interconnection networks, Proceedings of the 5th annual symposium on Computer architecture, p.223-229, April 03-05, 1978 [doi>10.1145/800094.803052]
• 28: William Daniel Strecker, An analysis of the instruction execution rate in certain computer structures, 1970
• 29: Clark David Thompson, A complexity theory for vlsi, 1980
• 30: C-L. Wu, T-Y. Feng, "On a Class of Multistage Interconnection Networks," IEEE Trans. Computers, Vol. C-29, No. 8, August 1980, pp. 694-702.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Design, Performance, Reliability