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

Journal of Inforamtion Science and Engineering, Vol.17 No.1, pp.1-21 (January 2001)

Efficient Prefix Computation on Faulty Hypercubes*

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 Sridhars algorithm [4] although 11 extra steps are needed.

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

Full Text () Retrieve PDF document (200101_01.pdf : 3,563,874 bytes)

Received October 11, 1999; revised February 22, 2000; accepted May 3, 2000.
Communicated by Wen-Lian Hsu.
*This reserach was supported in part by the National Science Council, under contract number NSC87-2213-E011-001.