A Fast Fault-Identification Algorithm Tailored for Optical Interconnection Networks in High-Performance Computers

Abstract:

Due to integrated positive features of both hypercube and tori, optical multi-mesh hypercube (OMMH) networks in high-performance computers are regarded as a class of promising optical inter-connection networks. This paper firstly derive that the diagnosability of OMMH under the pessimistic strategy is (2n+6)/(2n+6), which shows that the OMMH possesses strong self-diagnosingability. With the improved cycle decomposition method by Yang in J. Parall. Distrib. Comput. [10], a fast diagnosis algorithm to identify all faulty nodes tailored for OMMH, which runs in O(Nlog₂N) time is also proposed, where N is the number of the processors of an OMMH.

• Periodical: Advanced Materials Research (Volume 936)
• Pages: 2307-2312
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.936.2307
• Online since: June 2014
• Authors: He Li
• Keywords: Diagnosability, Diagnosis Algorithm, Optical Interconnection, Optical Multi-Mesh Hypercube Networks, Pessimistic Strategy

References

[1] K.Y. Chwa, S.L. Hakimi, On fault identification in diagnosable systems, IEEE Trans. Computers, 30 (6) (1981) 414-422.

DOI: 10.1109/tc.1981.1675807

[2] J. Fan, Diagnosability of the M¨obius cubes, IEEE Trans. Parallel and Distributed Systems, 9 (9)(1998) 923-928.

DOI: 10.1109/71.722224

[3] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, North-Holland, New York, (1980).

[4] S.L. Hakimi, A.T. Amin, Characterization of the connection assignment of diagnosable systems, IEEE Trans. Comput. 23 (1) (1974) 86-88.

DOI: 10.1109/t-c.1974.223782

[5] E. Kranakis, A. Pelc, Better adaptive diagnosis of hypercubes, IEEE Trans. Comput. 49 (2000) 1013-1020.

DOI: 10.1109/12.888036

[6] X. Li, X. Yang, L. He, Diagnosability of optical multi-mesh hypercube networks under the com- parison diagnosis model, International Journal of Computer Mathematics. in press.

DOI: 10.1080/00207160.2013.766331

[7] A. Louri, H. Sung, An optical multi-mesh hypercube: a scalable optical interconnection network for massively parallel computing, J. Lightwave Technol. 12 (4) (1994) 704-716.

DOI: 10.1109/50.285368

[8] A. Louri, H. Sung, Scalable optical hypercube-based interconnection network for massively- parallel computing, Appl. Opt. 33 (32) (1994) 7588-7598.

DOI: 10.1364/ao.33.007588

[9] F.P. Preparata, G. Metze, R.T. Chien, On the connection assignment problem of diagnosable systems, IEEE Trans. Electron. Comput. 16 (6) (1967) 848-854.

DOI: 10.1109/pgec.1967.264748

[10] X. Yang, A fast pessimistic one-step diagnosis algorithm for hypercube multicomputer systems, J. Parallel Distrib. Comput. 64 (2004) 546-553.

DOI: 10.1016/j.jpdc.2004.02.002