Nai-Wen Chang
Skip Abstract Section
Abstract
Processor fault diagnosis plays an important role in measuring the reliability of multiprocessor systems and the diagnosis of many well-known interconnection networks. The conditional diagnosability, which is more general than the classical diagnosability, is to measure the diagnosability of a multiprocessor system under the assumption that all of the neighbors of any node in the system cannot fail at the same time. This study shows that the conditional diagnosability for k-ary n-cubes under the PMC model is 8n − 7 for k ≥ 4 and n ≥ 4.
- Armstrong, J. R. and Gray, F. G. 1981. Fault diagnosis in a boolean n cube array of multiprocessors. IEEE Trans. Comput. 30, 8, 587--590. Google Scholar
Digital Library
- Ashir, Y. A. and Stewart, I. A. 2002. Fault-Tolerant embeddings of Hamiltonian circuits in k-ary n-cubes. SIAM J. Discr. Math. 15, 3, 317--328. Google ScholarDigital Library
- Bae, M. M. and Gray, B. 2003. Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes. IEEE Trans. Comput. 52, 10, 1271--1284. Google ScholarDigital Library
- Bose, B., Broeg, B., Kwon, Y., and and Ashir, Y. 1995. Lee distance and topological properties of k-ary n-cubes. IEEE Trans. Comput. 44, 8, 1021--1030. Google ScholarDigital Library
- Chan, M. Y. and Gray, S. J. 1991. FOn the existence of Hamiltonian circuits in faulty hypercubes. SIAM J. Discr. Math. 4, 4, 511--527. Google ScholarDigital Library
- Chang, G. Y., Chang,G. J., and Chen, G. H. 2005. Diagnosabilities of regular networks. IEEE Trans. Parallel Distrib. Syst. 16, 4, 314--323. Google ScholarDigital Library
- Chang, N. W. and Hsieh, S. Y. 2012. Conditional diagnosability of augmented cubes under the PMC model. IEEE Trans. Depend. Secure Comput. 9, 1, 46--60. Google ScholarDigital Library
- Dahbura, A. T. and Masson, G. M. 1984. An O(n2.5) fault identification algorithm for diagnosable systems. IEEE Trans. Comput. 33, 6, 486--492. Google ScholarDigital Library
- Day, K. and Ai-Ayyoub, A. E. 1997. Fault diameter of k-ary n-cube networks. IEEE Trans. Parallel Distrib. Syst. 8, 9, 903--907. Google ScholarDigital Library
- Fan, J. 1998. Diagnosability of the M̈obius cubes. IEEE Trans. Parallel Distrib. Syst. 9, 9, 923--928. Google ScholarDigital Library
- Ghafoor, A. 1989. A class of fault-tolerant multiprocessor networks. IEEE Trans. Reliabil. 38, 1, 5--15.Google ScholarCross Ref
- Ghafoor, A. 1990. Partitioning of even networks for improved diagnosability. IEEE Trans. Reliabil. 39, 3, 281--286.Google ScholarCross Ref
- Ghozati, S. A. and Wasserman, H. C. 1999. The k-ary n-cube network: Modeling, topological properties and routing strategies. Comput. Electric. Engin. 25, 3, 155--168.Google ScholarCross Ref
- Hsieh, S. Y. and Chen, Y. S. 2008a. Strongly diagnosable product networks under the comparison diagnosis model. IEEE Trans. Comput. 57, 6, 721--732. Google ScholarDigital Library
- Hsieh, S. Y. and Chen, Y. S. 2008b. Strongly diagnosable systems under the comparison diagnosis model. IEEE Trans. Comput. 57, 12, 1720--1725. Google ScholarDigital Library
- Hsieh, S. Y. and Lin, T. J. 2009. Panconnectivity and edge-pancyclicity of k-ary n-cubes. Netw. 54, 1, 1--11. Google ScholarDigital Library
- Hsu, G. H., Chiang, C. F., Shih, L. M., Hsu, L. H., and Tan, J. J. M. 2009. Conditional diagnosability of hypercubes under the comparison diagnosis model. J. Syst. Archit. 55, 2, 140--146. Google ScholarDigital Library
- Ishida, Y., Adachi, N., and Tokumaru, H. G. 1987. Diagnosability and distinguishability analysis and its applications. IEEE Trans. Reliabil. 36, 5, 531--538.Google ScholarCross Ref
- Kavianpour, A. and Kim, K. H. 1992. A comparative evaluation of four basic system-level diagnosis strategies for hypercubes. IEEE Trans. Reliabil. 41, 1, 26--37.Google ScholarCross Ref
- Lai, P. L., Tan, J. J. M., Chang, C. P., and Hsu, L. H. 2005. Conditional diagnosability measures for large multiprocessor systems. IEEE Trans. Comput. 54, 2, 165--175. Google ScholarDigital Library
- Lin, C. K., Tan, J. J. M., Hsu, L. H., Cheng, E., and Lipták, L. 2008. Conditional diagnosability of Cayley graphs generated by transposition trees. J. Interconnect. Netw. 9, 1--2, 83--97.Google ScholarCross Ref
- Maeng, J. and Malek, M. 1981. A comparison connection assignment for self-diagnosis of multiprocessors systems. In Proceedings of the 11th International Symposium on Fault-Tolerant Computing. 173--175.Google Scholar
- Malek, M. 1980. A comparison connection assignment for diagnosis of multiprocessors systems. In Proceedings of the 7th International Symposium on Computer Architecture. 31--36. Google ScholarDigital Library
- Preparata, F. P., Metze, G., and Chien, R. T. 1967. On the connection assignment problem of diagnosis systems. IEEE Trans. Comput. 16, 12, 848--854.Google ScholarCross Ref
- Sengupta, A. and Dahbura, A. 1992. On self-diagnosable multiprocessor system: Diagnosis by the comparison approach. IEEE Trans. Comput. 41, 11, 1386--1396. Google ScholarDigital Library
- Wang, D. 1999. Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model. IEEE Trans. Comput. 48, 12, 1369--1374. Google ScholarDigital Library
- Wang, D., An, T., Pan, M., Wang, K. and Qu, S. 2005. Hamiltonian-Like properies of k-ary n-cubes. In Proceedings of the 6th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT05). 1002--1007. Google ScholarDigital Library
- Xu, M., Thulasiraman, K., and Hu, X. D. 2009. Conditional diagnosability of matching composition networks under the PMC model. IEEE Trans. Circ. Syst. II 56, 11, 875--879. Google ScholarDigital Library
- Zhu, J. R. 2008. On conditional diagnosability and reliability of the BC networks. J. Supercomput. 45, 2, 173--184. Google ScholarDigital Library
- Zhu, Q., Liu, S. Y., and Xu, M. 2008. On conditional diagnosability of the folded hypercubes. Inf. Sci. 178, 4, 1069--1077. Google ScholarDigital Library
Index Terms
- Conditional Diagnosability of k-Ary n-Cubes under the PMC Model
Recommendations
Determining the conditional diagnosability of k-ary n-cubes under the MM* model
SIROCCO'11: Proceedings of the 18th international conference on Structural information and communication complexityProcessor fault diagnosis plays an important role for measuring the reliability of multiprocessor systems, and the diagnosability of many well-known interconnection networks has been investigated widely. Conditional diagnosability is a novel measure of ...
Conditional diagnosability and strong diagnosability of Split-Star Networks under the PMC model
An interconnection network's diagnosability is an important measure of its self-diagnostic capability. The classical problems of fault diagnosis are explored widely. The conditional diagnosability is proposed by Lai et al. as a new measure of ...
Conditional Diagnosability of Augmented Cubes under the PMC Model
Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system, and the diagnosability of many well-known multiprocessor systems has been widely investigated. The conditional diagnosability is a novel ...
Comments