Subnetwork reliability analysis in \(k\)-ary \(n\)-cubes. (English) Zbl 1422.68012
Summary: The \(k\)-ary \(n\)-cube is one of the most attractive interconnection network topologies for parallel computing systems. In this paper, we derive an upper bound on the \(k\)-ary \((n - 1)\)-cube reliability in a \(k\)-ary \(n\)-cube with odd \(k \geq 3\) using the probability fault model. An approximate \(k\)-ary \((n - 1)\)-cube reliability result is also obtained using the fixed partitioning. The numerical results show that the \(k\)-ary \((n - 1)\)-cube reliabilities under the probability fault model and the fixed partitioning are in good agreement. The numerical results are also shown to be consistent with and close to the simulation results.
MSC:
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
Keywords:
interconnection network; subnetwork reliability; probability fault model; \(k\)-ary \(n\)-cubeReferences:
| [1] | Adiga, N. R.; Blumrich, M. A.; Chen, D.; Coteus, P.; Gara, A.; Giampapa, M. E.; Heidelberger, P.; Singh, S.; Steinmacher-Burow, B. D.; Takken, T.; Tsao, M.; Vranas, P., Blue Gene/L torus interconnection network, IBM J. Res. Dev., 49, 2-3, 265-276 (2005) |
| [2] | Ed Anderson, Jeff Brooks, Charles Grassl, Steve Scott, Performance of the CRAY T3E Multiprocessor,in:Proceedings of Supercomputing, ACM/IEEE 1997 Conference, 1997, pp. 1-17.; Ed Anderson, Jeff Brooks, Charles Grassl, Steve Scott, Performance of the CRAY T3E Multiprocessor,in:Proceedings of Supercomputing, ACM/IEEE 1997 Conference, 1997, pp. 1-17. |
| [3] | Billinton, R.; Allan, R., Reliability Evaluation of Engineering Systems (1992), Plenum Press: Plenum Press New York · Zbl 0837.62074 |
| [4] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer New York · Zbl 1134.05001 |
| [5] | Chang, Y.; Bhuyan, L., A combinatorial analysis of subcube reliability in hypercube, IEEE Trans. Comput., 44, 7, 952-956 (1995) · Zbl 1057.68526 |
| [6] | Chen, Xie-Bin, Paired 2-disjoint path covers of faulty \(k\)-ary \(n\)-cubes, Theoret. Comput. Sci., 609, 494-499 (2016) · Zbl 1331.68032 |
| [7] | Chen, Huey-Ling; King, Chung-Ta, Efficient dynamic processor allocation for \(k\)-ary \(n\)-cube massively parallel processors, Comput. Math. Appl., 33, 8, 59-73 (1997) |
| [8] | Das, C.; Kim, J., A unified task-based dependability model for hypercube computers, IEEE Trans. Parallel Distrib. Syst., 3, 3, 312-324 (1992) |
| [9] | Hsieh, Sun-Yuan; Chang, Ying-Hsuan, Extraconnectivity of \(k\)-ary \(n\)-cube networks, Theoret. Comput. Sci., 443, 63-69 (2012) · Zbl 1246.68172 |
| [10] | Hsieh, Sun-Yuan; Kao, Chi-Ya, The conditional diagnosability of \(k\)-ary \(n\)-cubes under the comparison diagnosis model, IEEE Trans. Comput., 62, 4, 839-843 (2013) · Zbl 1365.68085 |
| [11] | Hsieh, Sun-Yuan; Lin, Tsong-Jie; Huang, Hui-Ling, Panconnectivity and edge-pancyclicity of \(3\)-ary \(n\)-cubes, J. Supercomput., 42, 2, 225-233 (2007) |
| [12] | Yamin Li, Wanming Chu, Adjusting parameters of \(kn\); Yamin Li, Wanming Chu, Adjusting parameters of \(kn\) |
| [13] | Li, Xiaowang; Zhou, Shuming; Xu, Xiang; Lin, Limei; Wang, Dajin, The reliability analysis based on subsystems of \((n, k)\)-star graph, IEEE Trans. Reliab., 65, 4, 1700-1709 (2016) |
| [14] | Lin, Limei; Xu, Li; Zhou, Shuming; Wang, Dajin, The reliability of subgraphs in the arrangement graph, IEEE Trans. Reliab., 64, 2, 807-818 (2015) |
| [15] | Mao, Weizhen; Nicol, David M., On \(k\)-ary \(n\)-cubes: theory and applications, Discrete Appl. Math., 129, 1, 171-193 (2003) · Zbl 1048.68063 |
| [16] | Peterson, Craig; Sutton, James; Wiley, Paul, iWarp: a 100-MOPS, LIW microprocessor for multicomputers, IEEE Micro, 11, 3, 26-29 (1991) |
| [17] | Soh, S.; Rai, S.; Trahan, J. L., Improved lower bounds on the reliability of hypercube architectures, IEEE Trans. Parallel Distrib. Syst., 5, 4, 364-378 (1994) |
| [18] | Wang, Shiying; Feng, Kai; Zhang, Guozhen, Strong matching preclusion for \(k\)-ary \(n\)-cubes, Discrete Appl. Math., 161, 18, 3054-3062 (2013) · Zbl 1287.05122 |
| [19] | Wang, Fan; Zhang, Heping, Matchings extend to Hamiltonian cycles in \(k\)-ary \(n\)-cubes, Inform. Sci., 305, 1-13 (2015) · Zbl 1360.68652 |
| [20] | Wang, Shiying; Zhang, Guozhen; Feng, Kai, Fault tolerance in \(k\)-ary \(n\)-cube networks, Theoret. Comput. Sci., 460, 34-41 (2012) · Zbl 1252.68044 |
| [21] | Wu, Xiaolong; Latifi, Shahram, Substar reliability analysis in star networks, Inform. Sci., 178, 2337-2348 (2008) · Zbl 1146.68348 |
| [22] | Yang, Yuxing; Li, Jing; Wang, Shiying, Embedding various cycles with prescribed paths into \(k\)-ary \(n\)-cubes, Discrete Appl. Math., 220, 161-169 (2017) · Zbl 1355.05236 |
| [23] | Yang, Ming-Chien; Tan, Jimmy J. M.; Hsu, Lih-Hsing, Hamiltonian circuit and linear array embeddings in faulty \(k\)-ary \(n\)-cubes, J. Parallel Distrib. Comput., 67, 4, 362-368 (2007) · Zbl 1115.68032 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
