Queueing delays in buffered multistage interconnection networks

ABSTRACT

Our work deals with the analysis of the queueing delays of buffered multistage Banyan networks of multiprocessors. We provide tight upper bounds on the mean delays of the second stage and beyond, in the case of infinite buffers. Our results are validated by simulations performed on a network simulator constructed by us. The analytic work for network stages beyond the first, provides a partial answer to open problems posed by previous research.

REFERENCES

• B, 76: Buzen J.P., "Fundamental Operational Laws of Computer Systems Performance", Acta Informatica 7, 167-182, 1976.
• BD, 78: Peter J. Denning , Jeffrey P. Buzen, The Operational Analysis of Queueing Network Models, ACM Computing Surveys (CSUR), v.10 n.3, p.225-261, Sept. 1978 [doi>10.1145/356733.356735]
• DJ, 81: Dias D.M. and Jump J.R., "Packet switching interconnection networks for modular systems", Computer 14, Dec. 1981.
• G, 84: Gottlieb A. Private Communication
• GGKMRS, 82: Allan Gottlieb , Ralph Grishman , Clyde P. Kruskal , Kevin P. McAuliffe , Larry Rudolph , Marc Snir, The NYU Ultracomputer—designing a MIMD, shared-memory parallel machine (Extended Abstract), Proceedings of the 9th annual symposium on Computer Architecture, p.27-42, April 26-29, 1982, Austin, Texas, United States
• GL, 73: 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
• KLEI, 75: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• KS, 83: Kruskal C.P. and Snir M., "The Performance of Multistage Interconnection Networks for Multiprocessors" IEEE Trans on Comp Vol C-32 No 12 Dec. 1983.
• KSW, 84: Kruskal C.P., Snir M. and Weiss A., Unpublished T.R., U. of Urbana-Champaign, ILL.
• P, 81: Patel J.A. , "Performance of processor-memory interconnections for multiprocessors", IEEE Trans. Comp. C-30, 1981.

INDEX TERMS

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)

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

General Terms:
Measurement, Performance, Theory, Verification