Performance evaluation of reduced bandwidth multistage interconnection networks

ABSTRACT

This paper presents and evaluates a class of buffered interconnection networks which provide performance and cost levels intermediate to a bus and a delta network. These networks, referred to as hybrid networks, are formed by beginning with a delta network and substituting buses for the final stages of the network. The choice of the number of stages replaced determines the bandwidth of the network. The reduction of network bandwidth is accompanied by a corresponding reduction in network cost. Hybrid networks provide the system architect with a cost-effective solution to design problems in which the required interconnection bandwidth is greater than that of a bus but less than that of a full delta network. The performance of hybrid networks is investigated by developing a numerical model and by using simulation. Two features of the model, buffers of arbitrary length at network switches and resource service times greater than interstage transfer delays, have not been included in previous analytical models of delta networks. Results show that in some cases, the expense of a multistage network is not required in order to maintain the maximum level of system performance.

REFERENCES

• 1: Daniel M. Dias and J. Robert Jump, "Packet Switching Interconnection Networks for Modular Systems," IEEE Computer, Vol. 14, no.12, pp. 43-53, December 1981.
• 2: Clyde P. Kruskal and Marc Snir, "The Performance of Multistage Interconnection Networks for Multiprocessors," IEEE Transactions on Computers, Vol.C-32, no.12, pp. 1091-1098, December 1983.
• 3: Clyde P. Kruskal, Marc Snir, and Alan Weiss, "The Distribution of Waiting Times in Clocked Multistage Interconnection Networks," Proceedings of the 1986 International Conference on Parallel Processing, pp. 12-19, 1986.
• 4: F. A. Briggs, King-Sun Fu, Kai Hwang, and B. W. Wah, "PUMPS Architecture for Pattern Analysis and Image Database Management," IEEE Transactions on Computers, Vol.C-31, no.10, pp. 969-982, October 1982.
• 5: J. R. Jump, J. D. Wise, and D. T. Harper III, "An Interleaved Array Processing Architecture," AFIPS Conference Proceedings, National Computer Conference, Vol.53, pp. 93-100, 1984.
• 6: Janak H. Patel, "Performance of Processor-Memory Interconnections for Multiprocessors," IEEE Transactions on Computers, Vol.C-30, no.10, pp. 771-780, October 1981.
• 7: Suchai Thanawastien and Victor P. Nelson, "Interference Analysis of Shuffle/Exchange Networks," IEEE Transactions on Computers, Vol.C-30, no.8, pp. 545-556, August 1981.
• 8: Erhan Cinlar, Introduction to Stochastic Processes, 1975.
• 9: Daniel M. Dias and Manoj Kumar, " "Comments on "Interference Analysis of Shuffle/Exchange Networks"," IEEE Transactions on Computers, Vol.C-31, no.6, pp. 546-547, June 1982.
• 10: D. T. Harper III, "Reduced Bandwidth Delta Networks," Ph.D Dissertation (in preparation), Rice University, Houston, TX, May 1987.

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

General Terms:
Design, Measurement, Performance