| Abstract: | Computation time for various primitive operations, such as broadcasting and global sum, can significantly increase when there are node failures in a hypercube. 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 neighbors 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 hypercube, during a communication step, nodes can exchange information with their 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 algorithms work independent of the location of source node and faulty nodes. This revised version was published online in June 2006 with corrections to the Cover Date. |
