The Gamma network: A multiprocessor interconnection network with redundant paths

ABSTRACT

The Gamma network is an interconnection network connecting N&equil;2" inputs to N outputs. It consists of log2N stages with N switches per stage, each of which is a 3 input, 3 output crossbar. The stages are linked via “power of two” and identity connections in such a way that redundant paths exist between the input and output terminals. In this network, a path from a source to a destination may be represented using one of the redundant forms of the difference between the source and destination numbers. The redundancy in paths may thus be studied using the theory of redundant number systems. Results are obtained on the distribution of paths connecting inputs to outputs, and the permuting capabilities of the Gamma network. Switch settings for certain frequently used permutations and control mechanisms are also considered in this paper. This network has an interesting application in solving tridiagonal systems using the odd-even elimination algorithm.

REFERENCES

• 1: A. Avizienis, "Signed-Digit Number Representations for Fast Parallel Arithmetic", IRE Trans. EC-10, 1961, pp.389-400.
• 2: T. Feng, "Data Manipulation Functions in Parallel Processors and their Implementations", IEEE Trans. Comp., Vol. C-23, Mar 1974, pp.309-318.
• 3: R. W. Hockney, A Fast Direct Solution of Poisson's Equation Using Fourier Analysis, Journal of the ACM (JACM), v.12 n.1, p.95-113, Jan. 1965 [doi>10.1145/321250.321259]
• 4: R.H. Kuhn, "Transforming Algorithms for Single-Stage and VLSI Architecture", Workshop on Interconnection Networks for Parallel and Distributed Processing, Purdue University, April 1980.
• 5: H.T. Kung, C.E. Leiserson, "Systolic Arrays (for VLSI)", Tech. Rept., Carnegie-Mellon University, Dept. of Comp. Sci., Dec 1978.
• 6: T. Lang, H.S. Stone, "A Shuffle-Exchange Network with Simplified Control", IEEE Trans. Comp., Vol. C-25, Jan 1976, pp.55-65.
• 7: D.H. Lawrie, "Access and Alignment of Data in an Array Processor", IEEE Trans. Comp., Vol. C-24, Dec 1975, pp.1145-1155.
• 8: J. Lenfant, "Parallel Permutations of Data: A Benes Network Control Algorithm for Frequently Used Permutations", IEEE Trans. Comp., Vol. C-27, July 1978, pp.637-647.
• 9: Robert J. McMillen , Howard Jay Siegel, MIMD machine communication using the augmented data manipulator network, Proceedings of the 7th annual symposium on Computer Architecture, p.51-60, May 06-08, 1980, La Baule, United States [doi>10.1145/800053.801909]
• 10: D.C. Opferman, N.T. Tsao-Wu, "On a Class of Rearrangeable Switching Networks", Bell Syst. Tech. Jour., Vol. 50, May-June 1971, pp.1579-1618.
• 11: D.S. Parker, "Notes on Shuffle/Exchange-Type Switching Networks", IEEE Trans. Comp., Vol. C-29, March 1980, pp.213-222.
• 12: D.S. Parker, C.S. Raghavendra, "The Gamma Network", in preparation.
• 13: M.C. Pease, "The Indirect Binary n-Cube Microprocessor Array", IEEE Trans. Comp., Vol. C-26, May 1977, pp.458-473.
• 14: H.J. Siegel, "Interconnection Networks for SIMD Machines", Computer, Vol. 12, June 1979, pp.57-65.
• 15: S.D. Smith, H.J. Siegel, R.J. McMillen, G.B. Adams, "Use of the Augmented Data Manipulator Multistage Network for SIMD Machines," Proc. 1980 International Conf. on Parallel Processing, pp.75-78.
• 16: H.S. Stone, "Parallel Processing with the Perfect Shuffle", IEEE Trans. Comp., Vol. C-20, Feb 1971, pp.153-161.

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:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Design