DIMENSION ORDERING AND BROADCAST ALGORITHMS IN FAULTY SIMD HYPERCUBES

In this paper, the problem of broadcasting in an n-dimensional SIMD hy percube, Q(n), with up to n - 1 node faults is studied. In an SIMD hyp ercube, during a communication step, nodes can exchange information wi th their neighbors only across a specific dimension. The broadcasting algorithms must work independent of the location of the source node an d faulty nodes. In a fault-free hypercube, any source node can broadca st a message to all nodes in n steps, by successive communication alon g any arbitrary ordering of the n dimensions. Given a set of at most n - 1 faults, an ordering d(1), d(2),..., d(n) of n dimensions is devel oped, depending on where the faults are located. An important and usef ul property of this dimension ordering is the following: if the n-cube is partitioned into k-subcubes using the first k dimensions of this o rdering, namely, d(1), d(2),..., d(k) for any 2 less than or equal to k less than or equal to n, then each k-subcube contains at most k - 1 faults. This result is then used to develop several new algorithms for broadcasting. These algorithms use n + 3 log n, n + 2 log n + 2, n log n + O(log log n), n + log n + 5, and n + 12 time steps respectivel y, and thus improve upon the best known algorithms for this problem. T his ordering of dimensions is also demonstrated in the presence of nod e as well as link faults. In this paper, it is also known how to exten d the dimension ordering theorem for handling up to ((n)(2)) faults. U sing this result, it seems possible to obtain even more fault-tolerant algorithms for the broadcasting problem. (C) 1996 Academic Press, Inc .