Efficient Prefix Computation on Faulty Hypercubes
Yu-Wei Chen, Kuo‐Liang Chung · 2001
Consider an n-dimensional SIMD hypercube Hn with ⎣3n/2 ⎦ − 1 faulty nodes. Given 2 n operands, this paper presents an efficient algorithm for prefix computation on the faulty Hn. Employing the newly proposed delay-update technique and the subcube partition scheme, the proposed algorithm takes n+5logn+7 steps, and it tolerates ⎣n/2⎦ more faulty nodes than does Raghavendra and Sridhar’s algorithm [4] although 11 extra steps are needed.