JISE

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Information Science and Engineering, Vol. 17 No. 1, pp. 1-21

Efficient Prefix Computation on Faulty Hypercubes

Yu-Wei Chen and Kuo-Liang Chung⁺
Department of Computer and Information Science
Aletheia University
Tamsui, Taipei, Taiwan 251, R.O.C.
E-mail: ywchen@email.au.edu.tw
⁺Department of Information Management
Institute of Computer Science and Information Engineering
National Taiwan University of Science and Technology
Taipei, Taiwan 106, R.O.C.
E-mail: klchung@cs.ntust.edu.tw

Consider an n-dimensional SIMD hypercube Hn with ?3n/2? - 1 faulty nodes. Given 2n 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.

Keywords: complexity analysis, fault tolerance, parallel algorithm, prefix computation, SIMD hypercube

Retrieve PDF document (JISE_200101_01.pdf)