Definition and analysis of a class of spanning bus orthogonal multiprocessing systems

ABSTRACT

A graph theoretical representation for a class of interconnection networks is suggested. The idea is based on a definition of orthogonal binary vectors and leads to a construction rule for a class of orthogonal graphs. An orthogonal graph is first defined as a set of 2m nodes, which in turn are linked by 2m-n edges for every link mode defined in an integer set Q*. The degree and diameter of an orthogonal graph are determined in terms of the parameters n, m and the number of link modes defined in Q*. Routing in orthogonal graphs is shown to reduce to the node covering problem in bipartite graphs. The proposed theory is applied to describe a number of well known interconnection networks such as the binary m-cube and spanning-bus meshes. Multi-dimensional access (MDA) memories are shown as examples of orthogonal shared memory multi-processing systems.

REFERENCES

• 1: Alnuweiri, H. M. and Kumar, V. K. P., A Reduced Mesh of Trees Organization for Elficient Solution to Graph Problems, 22nd Annum Conference on Information Science and Systems, March 1988.
• 2: Alnuweiri, H. M. and Kumar, V. K. P., OptlmaI Image Computations on Reduced VI.SI Architectures, IEEE Transactions on Circuits and Systems, September 1989.
• 3: K. E. Batcher, The Multidimensional Access Memory in STARAN, IEEE Transactions on Computers, Vol. C-26, No. 2, February 1977, pp. 172-177.
• 4: 1~. E. Buehrer et al., The ETH Multiprocessot EMPRESS: A Dynamically Reconfigurable MIMD System, IEEE Transactions on Computers, Vol. C-31, No. 11, November 1982, pp. 1035-1044.
• 5: L. N. B huyaa and D. P. Agrawal, Generalized Hypercube and Hyperbus Structures for a Computer Network, IEEE Transactions on Computers, Vol. C-33, No. 4, April 1984, pp. 323- 333.
• 6: G. Ezer, B. Hoyt, S. Sen, J. S. Sreekant and I. D. Scherson, A Parallel Processing Architecture for Image Generation and' Processing, Technical Report No. ECE 84-20, Dept. of ECE, University of California, Santa Barbara~ August 1984.
• 7: F. Harary, Graph Theory, Reading, Addison- Wesley Publishing Co., Inc., 1969.
• 8: K. Hwang and D. Kim, Generalization of OrthogonaI Multiprocessor for Massively Parallel Computation, Proceedings of Frontiers 88, 2nd Symposium on the Frontiers of Massively Parallel Computation.
• 9: K. Hwang , D. Kim , P.-S. Tseng, An Orthogonal Multiprocessor for Parallel Scientific Computations, IEEE Transactions on Computers, v.38 n.1, p.47-61, January 1989 [doi>10.1109/12.8729]
• 10: E. J. McCluskey, Minimization of Boolean Functions, Bell System Technical Journal, Vol. 35~ No. 6~ November 1956, pp. 1417-1444.
• 11: W. V. Quine, The Problem of Simplifying Truth Functions, American Mathematics Monthly, Vol. 59, No. 8, October 1952, pp. 521-531.
• 12: W. V. Quine, A Way to Simplify Truth Functions, American Mathematics Monthly, Vol. 62~ No. 9~ November 1955~ pp. 627-631.
• 13: I. D. Scherson and Y. Ma, Vector Computations in an Orthogonal Memory Access Multiprocessing System, Proceedings of the 8th Symposium on Computer Arithmetic, May 1987, pp. 28-37. February 1989, pp.238-249.
• 14: I. D. Scherson , S. Sen, Parallel Sorting in Two-Dimensional VLSI Models of Computation, IEEE Transactions on Computers, v.38 n.2, p.238-249, February 1989 [doi>10.1109/12.16500]
• 15: I. D. Scherson , Y. Ma, Analysis and applications of the orthogonal access multiprocessor, Journal of Parallel and Distributed Computing, v.7 n.2, p.232-255, October 1989 [doi>10.1016/0743-7315(89)90019-1]
• 16: I. D. Scherson, A Theory for the Description and Analysis of a Class o} Interconnection Networks, Princeton University, Technical Report No. CE-$89-002.
• 17: Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
• 18: P. S. Tseng, K. Hwang and P. K. Kumar, A VLSI-based Multiprocessor Architecture for Implementing Parallel Algorithms, Proceedings of the 13th International Conference on Parallel Processing, August 1985.
• 19: Alan Tucker, Applied combinatorics (3rd ed.), John Wiley & Sons, Inc., New York, NY, 1994

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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)

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Theory