An optimal fault-tolerant broadcasting algorithm for a hypercube multiprocessor

ABSTRACT

In this paper we describe an optimal fault-tolerant broadcasting algorithm in the presence of n-1 faulty processors in the hypercube multiprocessor. This algorithm takes log2(N)+1 steps to broadcast the message to all other processors. Our broadcasting algorithm is a procedure by which a processor can pass a message to all other processors in the network non-redundantly.

REFERENCES

• 1: 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]
• 2: J.D. Ullman, Computational A~ts of VLSI, Computer Science Press, 1984
• 3: H.S. Stone, "Parallel Processing with the Perfect Shuffle," IEEE Trans. on Computers, pp. 153- 161, Feb. 1971.
• 4: Herbert Sullivan , T R Bashkow, A large scale, homogeneous, fully distributed parallel machine, I, Proceedings of the 4th annual symposium on Computer architecture, p.105-117, March 23-25, 1977
• 5: J. E. Jang , S. W. Choi , W. K. Cho, A new approach to processor allocation and task migration in an N-cube multiprocessor, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.314-325, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76297]
• 6: M.-S. Chen , K. G. Shin, Processor allocation in an N-cube multiprocessor using gray codes, IEEE Transactions on Computers, v.36 n.12, p.1396-1407, Dec. 1987 [doi>10.1109/TC.1987.5009493]
• 7: M.-S. Chen , K. G. Shin, Task migration in hypercube multiprocessors, Proceedings of the 16th annual international symposium on Computer architecture, p.105-111, April 1989, Jerusalem, Israel
• 8: Ming-Syan Chen , Kang G. Shin, Adaptive Fault-Tolerant Routing in Hypercube Multicomputers, IEEE Transactions on Computers, v.39 n.12, p.1406-1416, December 1990 [doi>10.1109/12.61061]
• 9: B. Becket and H.U. Simon, "How robust is the ncube?", in Proc. 27th Ann. Symp. Foundations of Comp. Sci. Oct. 1986 pp 283-291.
• 10: Howard P. Katseff, Incomplete Hypercubes, IEEE Transactions on Computers, v.37 n.5, p.604-608, May 1988 [doi>10.1109/12.4611]
• 11: A. AI-Dhelaan and B. Bose, "Efficient Fault Tolerant Broadcasting Algorithm for the Hylr~cube", The fourth Conf. on Hypercube Concurrent Comp. and Applications, Monterey, Mar 1989
• 12: P. Ramanathan , K. G. Shin, Reliable Broadcast in Hypercube Multicomputers, IEEE Transactions on Computers, v.37 n.12, p.1654-1657, December 1988 [doi>10.1109/12.9743]
• 13: Youcef Saad , Martin H. Schultz, Topological Properties of Hypercubes, IEEE Transactions on Computers, v.37 n.7, p.867-872, July 1988 [doi>10.1109/12.2234]
• 14: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 15: T. K. Srikanth , Sam Toueg, Optimal clock synchronization, Journal of the ACM (JACM), v.34 n.3, p.626-645, July 1987 [doi>10.1145/28869.28876]
• 16: N. De.o, Graph Theory with applications to Engineering and Computer Science, Prentice-Hall, 1974.
• 17: M.R. Brown, "Implementation and Analysis of Binomial Queue Algorithms", SIAM J. Comput, Vol. 7, Aug. 1978, pp 298-319.
• 18: J.E. Jang and W.K. Cho, "Maximality of Subcube Recognition and Fault-Tolerance in an N-cube multiprocessors", To appear in the 4th SIAM Conferec~n on Parallel Processing, De.x:, 1990

INDEX TERMS

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

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

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

General Terms:
Algorithms, Theory