Cluster-Composition Graphs: t/t-Diagnosabilty and its Application

Abstract:

In this paper, we propose a unified approach for computing the t/t-diagnosability of numerous multiprocessor systems under the PMC model, including hypercube-like graphs, star graphs, and pancake graphs. Our approach first defines a superclass of graphs, called j-order cluster-composition graphs, to cover them.We then show that the 1-order simple cluster-composition graph is t/t-diagnosable if it contains no connected component with size less than 2t+1, where t is the minimal number of neighbors of any pair of vertices of the graph. Based on this result, the t/t-diagnosability of the above multiprocessor systems can be computed efficiently.

• Periodical: Applied Mechanics and Materials (Volumes 411-414)
• Pages: 2115-2118
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.411-414.2115
• Online since: September 2013
• Authors: Jheng Cheng Chen, Chang Hsiung Tsai
• Keywords: Cluster-Composition Graphs, Fault Diagnosis, Interconnection Networks, Reliability

References

[1] F. Barsi, F. Grandoni, and P. Maestrini, A theory of diagnosability of digital systems, ', IEEE Transactions on Computers, vol. 25, no. 6, pp.585-593, (1976).

DOI: 10.1109/tc.1976.1674658

[2] G. Y. Chang, G. J. Chang, and G. H. Chen Diagnosabilities of regular networks, ', IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 4, pp.314-323, (2005).

DOI: 10.1109/tpds.2005.44

[3] J. C. Chen, and C. H. Tsai, Diagnosable evaluation of general biswapped networks, ', in Processings of the 29th workshop on combinatorial mathematics and computation theory, pp.272-276, (2012).

[4] J. Fan, Diagnosability of the Möbius cubes, ', IEEE Transactions on Parallel and Distributed Systems, vol. 40, no. 1, pp.88-93, (1991).

[5] A. Kavianpour and A. D. Friedman, Efficient design of easily diagnosable system, ' in: Proceedings of IEEE Computer Society, s 3rd USA-Japan Computer Conference, (1978).

[6] A. Kavianpour and K. H. Kim, Diagnosabilities of hypercubes under the pessimistic one-step diagnosis strategy, ', IEEE Transactions on Computers, vol. 40, no. 2, pp.232-237, (1991).

DOI: 10.1109/12.73595

[7] F. T. Leighton, Introduction to Parallel Algorithms and Architecture: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, (1992).

[8] J. Maeng and M. Malek, A comparison connection assignment for self-diagnosis of multiprocessors systems, ' Proc. 11th Int, l Symp. Fault-Tolerant Computing, pp.173-175, (1981).

[9] F. P. Preparata, G. Metze, and R. T. Chien, On the connection assignment problem of diagnosis systems, ', IEEE Transactions on Electronic Computers, vol. 16, no. 12, pp.848-854, (1967).

DOI: 10.1109/pgec.1967.264748