The composite binary cube — a family of interconnection networks for multiprocessors

ABSTRACT

A class of interconnection networks called composite binary n-cube networks is presented in this paper for multiprocessors. These networks provide a spectrum of performance levels (measured in terms of message delays or network bandwidth) at different switching costs. At the low end of this spectrum is a structure called the expanded indirect binary n-cube (a multistage network), and at the high end is the well known hypercube structure. All members of this class have the same external connectivity between nodes, but utilize different internal switching architectures within the nodes. The distributed control algorithm for these networks is similar to those for multistage and hypercube architectures. An analytical model for the performance of these networks is also presented in this paper. Results of this model show that message delays decrease by about 40% from the low end architecture to the high end of the spectrum; however, the improvements in performance diminish near the high end. Thus for best performance/cost ratios within this class, our studies indicate that an intermediate architecture needs to be chosen.

REFERENCES

• 1: S. Abraham and K. Padmanabhan, "Performance of the Dixect Binary n-Cube Network for Multiprocessors," Proc. J986 Int. Conf. Parallel Processing, Aug. 1986, pp 636-639.
• 2: G.H. Barnes and S.F. Lundstrom, "Design and Validation of a Connection Network for Many-Processor Multiprocessor Systems," Computer, Vol. 14, No. 12, Dec. 1981, pp 31-41.
• 3: P-Y. Chen, P-C. Yew, and D.H. Lawrie, "Performance of Packet Switching in Buffered Single-Stage Shuffle- Exchange Networks," Proc. 3rd Int. Conf. Distributed Computing, May, 1982, pp 622-627.
• 4: W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 5: Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 6: D. Gajski, D. Kuck, D. Lawrie, and A. Sameh, "Cedar A Large Scale Multiprocessor," Proc. 1983 int. Conf. Parallel Processing, Aug. 1983, pp 524-529.
• 7: A. Gotfiieb and I. Schwartz, "Networks and Algorithms for Very-Large-Scale Parallel Computation," Computer, Vol. 15, No. 1, Jan. 1982, pp 27-36.
• 8: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 9: C.P. Kmskal and M. Snir, "The Performance of Multistage Interconnection Networks for Multiprocessors," IEEE Transactions on Computers, Vol. C-32, No. 12, Dec. 1983, pp 1091-1098.
• 10: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 11: K. Padmanabhan, "Towards a Synthesis of Direct and Indirect Cube Structures for Multiprocessors," Proc. 8th Ann. IEEE Int. Phoenix Conf. on Computers and Communications, March !989,
• 12: J.H. Patel, "Performance of Processor-Memory Interconnecfions for Multiprocessors," IEEE Trans. Computers, Vol. C-30, No. 10, Oct. 1981, pp 771-780.
• 13: M.C. Pease, I~ "The Indirect Binary n-Cube Microprocessor Array," IEEE Trans. Compur, Vol. C-Z~5, No. 5, May 1977, pp 458-473.
• 14: Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
• 15: Herbert Sullivan , T R Bashkow, A large scale, homogeneous, fully distributed parallel machine, I, Proceedings of the 4th annual symposium on Computer architecture, p.105-117, March 23-25, 1977
• 16: C.-L.Wu and T.-Y. Feng, "On a Class of Multistage Interconnection Networks," {EEE Trans. Comput., Vol. C-29, No. 8, Aug. 1980, pp 694-702.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional 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)
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Design, Experimentation, Measurement, Performance, Theory