A fast diagnosis algorithm for interconnection network in high performance computers
Li He, Furong Li · International Journal of Parallel Emergent and Distributed Systems · 2014
In high performance computers, a popular interconnection network, the folded hypercube (FHC), possesses smaller diameter, larger connectivity, better reliability and fault tolerance capability as compared with a hypercube counterpart. This paper addresses the fault identification of FHC multiprocessor interconncection systems under the MM* model. The pessimistic one-step diagnosability of FHC networks is first determined. On the basis, a pessimistic one-step diagnosis algorithm tailored for FHC multiprocessor systems is proposed. The presented algorithm can isolate all faulty nodes to within a set which has at most one fault-free node, and can run in linear time.