We consider the problem of computing a global commutative and associative operation, also known as semi-group operation, (such as addition and multiplication) on a faulty hypercube. In particular, we study the problem of performing such an operation in an n-dimensional SIMD hypercube, Q/sub n/, with up to n-1 node and/or link faults. In an SIMD hypercube, during a communication step, nodes can exchange information with their neighbors only across a specific dimension. Given a set of at most n-1 faults, we develop an ordering d/sub 1/,d/sub 2/,...,d/sub 1/ of n dimensions, depending on where the faults are located. An important and useful property of this dimension ordering is the following: if the n-cube is partitioned into k-subcubes using the first k dimensions of this ordering, namely d/sub 1/, d/sub 2/,..., d/sub n/ for any 2/spl les/k/spl les/n, then each k-subcube in the partition contains at most k-1 faults. We use this result to develop algorithms for global sum. These algorithms use 3n-2, n+3 log n+3 log log n, and n+log n+d/sub 2/ log log n+O(log log log n) time steps, respectively.

The fundamental question addressed in this paper is that of computing the parallel prefix operation. In particular, we study the problem of performing such an operation in an n-dimensional SIMD hypercube, Q_n, with up to n-1 node faults. In an SIMD hypercube, during a communication step, nodes can exchange information with their neighbors only across a specific dimension. We exhibit an n+5 logn algorithm for this problem. The development of the algorithm is based on the existence of two so-called free dimensions in such a faulty hypercube [6].

The authors introduce a novel class of networks based on the de Bruijn graph. These directed graphs are regular of degree, have N=k/sup n/ vertices for some n, and can tolerate up to k-2 node faults. Their fault-free diameter is n=log/sub k/N, and this is increases by at most 1 hop in the presence of k-2 faults. This class is very rich: for any given N=k/sup n/, one can construct at least 2/sup N/ different graphs. This is in sharp contrast to most other such constructions (including the de Bruijn graph), in which only one graph exists for each N. It is also shown how to implement certain algorithms on these networks.>

The problem of deciding whether two given permutation sequences are conjugate is addressed. The author exhibits an algorithm that solves this problem in time O(N log N), where N is the sum of the sizes of the two sequences. The algorithm can be applied to the problem of deciding whether two permutation networks are equivalent. The time bound for the algorithm is a significant improvement over the O(N/sup 2/) bound of the algorithm due to Y.A. Oruc and M.Y. Oruc (1985). The author's method applies techniques used by the Hopcroft-Tarjan algorithm for deciding planar graph isomorphism.>