An analytic model of multistage interconnection networks

ABSTRACT

Multiprocessors require an interconnection network to connect processors with memory modules. The performance of the interconnection network can have a large effect upon overall system performance, and, therefore, methods are needed to model and compare alternative network architectures. This paper is concerned with evaluating the performance of multistage interconnection networks consisting of k × s switching elements. Examples of such networks include omega, binary n-cube and baseline networks. We consider clocked, packet switched networks with buffers at switch output ports. An analytical model based on approximate Mean Value Analysis is developed, then validated through simulations.

REFERENCES

• 1: V. E. Benes, "Mathematical Theory of Connecting Networks and Telephone Traffic," Academic Press, New York, 1965.
• 2: D.M. Dias and J. R. Jump, "Analysis and Simulation of Buffered Delta Networks," IEEE Trans. Comput., Vol. C-30, pp. 273-282, Apr. 1981.
• 3: D. M. Dias and J. R. Jump, "Packet Switching Interconnection Networks for Modular Systems," Computer, Vol. 14, pp. 43-53, Dec. 1981.
• 4: T. Y. Feng, "A Survey of Interconnection Networks," Computer, Vol. 14, pp. 12-27, Dec. 1981.
• 5: D. Gajski, D. Kuck, D. Lawrie and A. Sameh, "Cedar - A Large Scale Mulfiprocessor," Proc. 1983 Int'l Conf. Parallel Processing, pp. 524-529, 1983.
• 6: 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
• 7: A. Gotflieb, R. Grishman, C. P. Kruskal, K. P. McAuliffe, L. Rudolph and M. Snir, "/'he NYU Ultracomputer - Designing an MIMD Shared Memory Parallel Computer," IEEE Trans. Comput., Vol. C-32, pp. 175-189, Feb. 1983.
• 8: D. T. Harper, III , J. R. Jump, Performance evaluation of reduced bandwidth multistage interconnection networks, Proceedings of the 14th annual international symposium on Computer architecture, p.171-175, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30370]
• 9: C. P. Kruskal and M. Snir, "l'he Performance of Multistage Interconnection Networks for Multiprocessors," IEEE Trans. Comput., Vol. C-32, pp. 1091-1098, Dec. 1983.
• 10: C. P. Kruskal , M. Snir , A. Weiss, The Distribution of Waiting Times in Clocked Multistage Interconnection Networks, IEEE Transactions on Computers, v.37 n.11, p.1337-1352, November 1988 [doi>10.1109/12.8700]
• 11: D.H. Lawrie, "Access and Alignment of Data in an Array Processor," IEEE Trans. Compuc, Vol, C-24, pp. 1145- 1155, Dec. 1975.
• 12: Edward D. Lazowska , John Zahorjan , G. Scott Graham , Kenneth C. Sevcik, Quantitative system performance: computer system analysis using queueing network models, Prentice-Hall, Inc., Upper Saddle River, NJ, 1984
• 13: Y. Liu and S. Dickey, "Simulation and Analysis of Different Switch Architectures for Interconnection Networks in MIMD Shared Memory Machines," Ultracomputer Note #141, June 1988.
• 14: J. A. Patel, "Performance of Processor-Memory Interconnections for Mulfiprocessors," IEEE "{',am. Comput., Vol. C-30, pp. 771-780, Dec. 1981.
• 15: G.F. Pfister, W. C. Brantley, D. A. George, S. L. Harvey, W. J. KleirLfelder, K. P. McAuliffe, E. A. Melton, V. A. Norton and j. Weiss, "The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture," Proc. 1985 lnt'l Conf. Parallel Processing, pp. 764-771, 1985.
• 16: G.F. Pfister and V. A. Norton, "'Hot Spot' Contention and Combining in Multistage Interconnection Networks," Proc. 1985 Int'l Conf. Parallel Processing, pp. 790-797, 1985.
• 17: Randall Rettberg , Robert Thomas, Contention is no obstacle to shared-memory multiprocessing, Communications of the ACM, v.29 n.12, p.1202-1212, Dec. 1986 [doi>10.1145/7902.7905]

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications; Network topology
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

General Terms:
Design, Measurement, Performance