The higher radix hypercube as an interconnection and virtual network

ABSTRACT

The HIGHER RADIX HYPERCUBE (HRH) is investigated in this paper as an interconnection network for multiprocessors as well as a virtual network. The HRH is based on a radix higher than two, the radix for the hypercube. We have compared several topological parameters' for the HRH with the hypercube. It can be seen that HRH provides smaller diameter for a small price. A mapping and a partitioning algorithms are proposed for mapping different topologies to the HRH. In our algorithm, we first map the problem topology to a virtual HRH, which is the most natural HRH for the problem. The virtual HRH is then transformed into the actual topology. This algorithm is applicable to HRH used either as an interconnection or a virtual network. The partitioning algorithm reduces a large application topology to the required size by the iterative reduction process. Three examples of mapping topologies onto the HRH are also presented.

REFERENCES

• 1: J.P. Hayes, T.N. Mudge and Q.F. Stout, "Architecture of a Hypercube Supercomputer," Proc. 1986 Intl. conf.- on Parallel Processing, August 1986, p p . 653-660.
• 2: Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
• 3: Kai Hwang and Joydeep Ghosh, "Hypernet Architectures for Parallel Processing," Proc. 1987 Intl. conf. on Parallel Processing, August 1987, pp. 810-819.
• 4: William Tsun-yuk Hsu, Pen-Chung Yew and Chuan-qi Zhu, "An Enhancement Scheme for Hypercube Interconnection Networks," Proc. 1987 Intl. conf. on Parallel Processing, August 1987, pp. 820-823.
• 5: Laxmi N. Bhuyan and Dharma P. Agrawal, "Generalized Hypercube and Hyperbus Structures for a Computer Network," IEEE Tran-s. on Computers, April 1984, Vol. C-33, No. 4, pp. 323-333.
• 6: Shahid E. Bokhari, "On the mapping problem," Proc. 1979 Intl. conf. on Parallel Processing, August 1979, pp. 239-247.
• 7: Francine Berman, Lawrence Snyder, "On mapping algorithms into parallel computers," Intl. conf. on Parallel Processing, August 1984, pp. 307-309.
• 8: D. A. Reed , L. M. Adams , M. L. Partick, Stencils and problem partitionings: their influence on the performance of multiple processor systems, IEEE Transactions on Computers, v.36 n.7, p.845-858, July 1987 [doi>10.1109/TC.1987.1676980]
• 9: Russ Miller and Quentin F. Stout, "Computational Geometry on a meshconnected computer (Preliminary version)", Proc. 1984 Intl. conf. on Parallel Processing, August 1984, pp. 66 -7 3 .
• 10: V.K.P. Kumar and M.M. Eshaghian, "Parallel Geometric Algorithm for Digitized Pictures on Mesh of Trees (Preliminary version)", Proc. 1986 Intl. conf. on Parallel Processing, August 1986, pp. 270-273.
• 11: Russ Miller and Quentin F. Stout, "Convexity algorithms for pyramid computers," Proc. 1984 Intl. conf. on Parallel Processing, August 1984, pp. 177-184.
• 12: Praveen Gupta, "TECHNIQUES FOR MAPPING THE ALGORITHMS INTO THE HIGHER RADIX HYPERCUBE MULTIPROCESSORS", M.S. Thesis, May 1988, The University of Texas at Arlington, Arlington, TX.
• 13: T. C. Lin, "Virtual Network and Mapping Problem", CSE Technical Report TR-03, UTA, May 1987.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

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.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Algorithms, Design