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

Journal of Inforamtion Science and Engineering, Vol.16, No.1, pp.25-40 (January 2000)

A Fault-Tolerant Reconfiguration Scheme
In the Faulty Star Graph

Yuh-Shyan Chen and Jang-Ping Sheu+
Department of Computer Science and Information Engineering
Chung-Hua University
Hsinchu, Taiwan 300, R.O.C.
E-mail: chenys@csie.chu.edu.tw
+ Department of Computer Science and Information Engineering
National Central University
Chungli, Taiwan 320, R.O.C.
E-mail: sheujp@csie.ncu.edu.tw

In this paper, we propose a scheme to identify the maximal fault-free substar-ring. This is the first attempt to derive a reconfiguration scheme with high processor utilization in the faulty n-star graph. The maximal fault-free substar-ring is connected by a ring of fault-free virtual substars and the maximal length of the ring is n(n - 1)(n - 2). Our proposed scheme can tolerate n - 3 faults such that the processor utilization is . This is a near optimal result since the maximal fault-free substar-ring is constructed using all of the possible fault-free (n - 2)-substars. Moreover, our algorithm can still work when the number of faults exceeds n - 3. The simulation results also show that the processor utilization is more than 50% if the number of faults is less than in the n-star graph.

Keywords: fault tolerance, interconnection network, parallel processing, reconfiguration, star graph

Full Text () Retrieve PDF document (200001_02.pdf : 3,563,874 bytes)

Received October 23, 1997; revised March 27, 1998; accepted May 13, 1998.
Communicated by Shing-Tsaan Huang