The performance of multistage interconnection networks with finite buffers

ABSTRACT

Multistage interconnection networks with crossbar switches are a major component of parallel machines. In this paper we analyze Banyan networks of k by k switches and with finite buffers. The exact solution of the steady state distribution of the first stage is derived in the situation where packets are lost when they encounter a full buffer (Assumption A). The solution is a linear combination of k-1 geometrics. We use this to get an approximation for the steady state distributions in the second stage and beyond. As a side effect, the infinite buffer case is solved, confirming known results. Our results are validated by extensive simulations. An alternate situation of networks where full buffers may block previous switches is also analyzed through an approximation technique (Assumption B).

REFERENCES

• Dias, Jump, 81: Dias D.M., Jump J.R., "Analysis and Simulation of Buffered Delta Networds", IEEE Trans. Computer, Vol. C-30, April 1981, pp. 273-282.
• Kruskal, Snir, 83: Kruskal C.P., Snir M., "The performance of multistage interconnection networks for multiprocessors", IEEE Trans. Computer, Vol C-32, Dec. 1983, pp. 1091-1098.
• Kruskal, Snir, Weiss, 88: 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]
• Patel, 81: Pate1 J.A., "Performance of processor-memory tnterconnecttons for multiprocessors", IEEE Trans. Comput., Vol. C-30, 1981, pp. 771-780.

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: Packet-switching networks
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

General Terms:
Algorithms, Performance