Ring-connected hypercubes and their relationship to cubical ring connected cycles and dynamic redundancy networks

ABSTRACT

In this paper, we first present a 1-fault-tolerant (1-ft) hypercube model with degree 2r, the ring-connected hypercube (RCH), which has the lowest degree among all 1-ft, one spare node, r-dimensional hypercube architecture yet discovered. Then we propose a zero-time reconfiguration algorithm via an add-and-modulo automorphism. Furthermore, by introducing the equivalence from hypercubes to cube-connected cycles (CCC's) and to butterflies (BF's), we find there is also a corresponding equivalence from RCH's to cubical ring connected cycles (CRCC) and to dynamic redundancy networks (DRN's). From this fact, we find out that once a symmetric fault-tolerant structure has been discovered for one of the three models, then it can apply directly to the other hypercubic networks. Applying the technique, we find a degree 6, 1-ft Benes network. Another point is we think that the strong relationship between hypercubes, CCC's and BF's should be paid more attention, and finally from this equivalence relationship to the RCH's we propose three new bounded-degree k-ft models: k-ft CCC's, k-ft BF's, and k-ft Benes networks.

REFERENCES

• 1: Prithviraj Banerjee, The Cubical Ring Connected Cycles: A Fault Tolerant Parallel Computation Network, IEEE Transactions on Computers, v.37 n.5, p.632-636, May 1988 [doi>10.1109/12.4617]
• 2: J.-C. Bermond , F. Comellas , D. F. Hsu, Distributed loop computer networks: a survey, Journal of Parallel and Distributed Computing, v.24 n.1, p.2-10, Jan. 1995 [doi>10.1006/jpdc.1995.1002]
• 3: N. Biggs, Finite Groups of Automorphisms. Cambridge Univ. Press, Cambridge, 1971.
• 4: F. T. Boesch and R. Tindell, "Circulants and Their Connectivity," J. Graph Theory, Vol. 8, 1984, pp. 487-499.
• 5: J. Bruck, R. Cypher, and C.-T. Ho, "On the Construction of Fault-Tolerant Cube-Connected Cycles Networks," IBM Research Report, RJ 8079, Apr. 1991.
• 6: J. Bruck, R. Cypher, and C.-T. Ho, "Efficient Fault- Tolerant Meshes and Hypercube Architectures," IBM Research Report, RJ 8566, Jan. 1992.
• 7: F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg, "Diogenes: A methodology for designing fault-tolerant VLSI processor arrays," Proc. 13th Fault Tolerant Computing Symposium, June 1983, pp. 26-31.
• 8: Shantanu Dutt , John P. Hayes, Designing fault-tolerant systems using automorphisms, Journal of Parallel and Distributed Computing, v.12 n.3, p.249-268, July 1991 [doi>10.1016/0743-7315(91)90129-W]
• 9: C. Padró , P. Morillo , M. A. Fiol, Comments on "Line Digraph Iterations and Connectivity Analysis of de Bruijn and Kautz Graphs", IEEE Transactions on Computers, v.45 n.6, p.768, June 1996 [doi>10.1109/12.506435]
• 10: J. P. Hayes, "A Graph Model for Fault Tolerant Computing System," IEEE Trans. Comput., Vol. 25, 9, Sep. 1976, pp. 875-884.
• 11: M. Jeng , H. J. Siegel, Design and Analysis of Dynamic Redundancy Networks, IEEE Transactions on Computers, v.37 n.9, p.1019-1029, September 1988 [doi>10.1109/12.2253]
• 12: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 13: Franco P. Preparata , Jean Vuillemin, The cube-connected cycles: a versatile network for parallel computation, Communications of the ACM, v.24 n.5, p.300-309, May 1981 [doi>10.1145/358645.358660]
• 14: D.A. Rennels, "On implementing fault-tolerance in binary hypercubes," Proc. 16th Fault Tolerant Computing Symposium, June 1986, pp. 344-349.
• 15: Howard Jay Siegel, Interconnection networks for large-scale parallel processing: theory and case studies (2nd ed.), McGraw-Hill, Inc., New York, NY, 1990

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Design, Performance