Fault tolerance of a class of connecting networks

ABSTRACT

Several proposals have been made for using a class of connecting networks called &bgr;-networks in multicomputer systems, such as systems containing large numbers of microprocessors. A &bgr;-network is a network of 2 × 2 crossbar switches called &bgr;-elements. This paper presents an analysis of the fault tolerance of &bgr;-networks intended for multicomputer applications. A fault model is used which allows &bgr;-elements to be stuck in either of their two normal states. A new connectivity property called dynamic full access (DFA) is introduced which serves as the criterion for fault tolerance. A &bgr;-network is said to have the DFA property if each of its inputs can be connected to any of its outputs in a finite number of passes through the network. A fault is called critical if it destroys the DFA property. Two graph-theoretical characterizations of the critical faults of a &bgr;-network are presented. It is shown that there is a one-to-one correspondence between minimal critical faults and the cutsets of the circuit adjacency graphs derived from the &bgr;-network. It is further shown that a fault is critical if and only if it is incompatible with all Eulerian circuits associated with the &bgr;-network. Some applications of the theory are discussed.

REFERENCES

• 1: Swan, R.J., S.H. Fuller, and D.P. Siewiorek, "Cm* - A Modular, Multi-Microprocessor," AFIPS Conf. Proc., vol. 46, 1977, pp. 637-644.
• 2: Pease, M.C., "The Indirect Binary n-Cube Microprocessor Array," IEEE Trans. Computers, vol. C-26, May 1977, pp. 458-473.
• 3: K. Hurakami , S. Nishikawa , M. Sato, Poly-Processor System analysis and design, Proceedings of the 4th annual symposium on Computer architecture, p.49-56, March 23-25, 1977
• 4: Burrough's Corp., Final Report: Numerical Aerodynamic Simulation Facility Feasibility Study, Paoli, PA, March 1979.
• 5: Masson, G.M., G.C. Gingher, and S. Nakamura, "A Sampler of Circuit Switching Networks," Computer, June 1979, pp. 32-48.
• 6: Howard Jay Siegel , S. Diane Smith, Study of multistage SIMD interconnection networks, Proceedings of the 5th annual symposium on Computer architecture, p.223-229, April 03-05, 1978 [doi>10.1145/800094.803052]
• 7: Thurber, K.J., "Circuit Switching Technology: A State-of-the-Art Survey," Proc. COMPCON, Fall 1978, pp. 116-124.
• 8: Benes, V.E., Mathematical Theory of Connecting Networks and Telephone Traffic, New York, Academic Press, 1965.
• 9: Tse-yun Feng , Chuan-lin Wu , Dharma P. Agrawal, A microprocessor-controlled asynchronous circuit switching network, Proceedings of the 6th annual symposium on Computer architecture, p.202-215, April 23-25, 1979 [doi>10.1145/800090.802911]
• 10: Siegel, H.J., "Interconnection Networks for SIMD Machines," Computer, June 1979, pp. 57-65.
• 11: Batcher, K.E., "The Flip Network in STARAN," Proc. 1976 Int'l. Conf. Parallel Processing, Aug. 1976, pp. 65-71.
• 12: Stone, H.S., "Parallel Processing with the Perfect Shuffle," IEEE Trans. Computers, vol. C-20, no. 2, Feb. 1971, pp. 153-161.
• 13: Janak H. Patel, Processor-memory interconnections for multiprocessors, Proceedings of the 6th annual symposium on Computer architecture, p.168-177, April 23-25, 1979 [doi>10.1145/800090.802906]
• 14: Levitt, K.N., M.W. Green, and J. Goldberg, "A Study of the Data Commutation Problems in a Self-Repairable Multiprocessor," Proc. 1968 SJCC, 1968, pp. 515-527.
• 15: Opferman, D.C. and N.T. Tsao-Wu, "On a Class of Rearrangeable Switching Networks, Part II: Enumeration Studies and Fault Diagnosis," Bell Sys. Tech. Jour., May/June 1971, pp. 1601-1618.
• 16: Harary, F. and E.M. Palmer, Graphical Enumeration, New York, Academic Press, 1973.
• 17: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 18: Mayeda, W., Graph Theory, New York, Wiley-Interscience, 1972.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

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)

General Terms:
Design, Reliability