Improved one-to-all broadcasting algorithms on faulty SIMD hypercubes

摘要

Consider an n-dimensional SIMD hypercube H_n with [3n/2} - 1 faulty nodes. With n + 3 log(n - 1) + 7, n + 2 log(n - 1) + 9, n + log(n - 1) + O(log log(n - 1)), n + log(n - 1) + 12, and n + 19 steps, this paper presents some one-to-all broadcasting algorithms on the faulty SIMD H_n. The sequence of dimensions used for broadcasting in each algorithm is the same regardless of which node is the source. The proposed one-to-all broadcasting algorithms can tolerate [n/2] more faulty nodes than Raghavendra and Sridhar's algorithms (J. Parallel Distrb. Comput. 35 (1996) 57) although 8 extra steps are needed. The fault-tolerance improvement of this paper is about 50%.