GLOBAL COMMUTATIVE AND ASSOCIATIVE REDUCTION OPERATIONS IN FAULTY SIMD HYPERCUBES

We consider the problem of computing a global commutative and associat ive operation, also known as semi-group operation, (such as addition a nd multiplication) on a faulty hypercube. In particular, we study the problem of performing such an operation in an n-dimensional SIMD hyper cube, Q(n), with up to n - 1 node and/or link faults. In an SIMD hyper cube, during a communication step, nodes can exchange information with their neighbors only across a specific dimension. Given a set of at m ost n - 1 faults, we develop an ordering d(1), d(2), ..., d(n) of n di mensions, 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 th is ordering, 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 in the partition con tains at most k - 1 faults. We use this result to develop algorithms f or global sum. These algorithms use 3n - 2, n + 3 log n + 3 log log n, and n + log n + 4 log log n + O(log log log n) time steps, respective ly.