| Previous | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] |
Yu-Wei Chen and Kuo-Liang+
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
Received October 11, 1999; revised February 22, 2000; accepted May 3, 2000.
Retrieve PDF document (200101_01.pdf : 3,563,874 bytes)
Communicated by Wen-Lian Hsu.
*This reserach was supported in part by the National Science Council, under contract number NSC87-2213-E011-001.