Improved algorithms for computing with faulty SIMD hypercubes

Computation time for various primitive operations, such as broadcasting and global sum, can significantly increase when there are node failures in a h ypercube. In this paper we develop nearly optimal algorithms for computing important basic problems on a faulty SIMD hypercube. In an SIMD hypercube, during a communication step, nodes can exchange information with their neig hbors only across a specific dimension. Our parallel machine model is an n- dimensional SIMD hypercube Q(n) with up to n - 1 node faults. In an SIMD hy percube, during a communication step, nodes can exchange information with t heir neighbors only across a specific dimension. We use the concept of free dimension to develop our algorithms, where a free dimension is defined to be a dimension i such that at least one end node of any i-dimension link is nonfaulty. In an n-cube, with f < n faults, it is known that there exist n - f + 1 free dimensions. Using free dimensions, we show that broadcasting and global sum can be performed in n + 5 steps, thereby improving upon the previously known algorithms for these primitives. The broadcasting algorith ms work independent of the location of source node and faulty nodes.