交换交叉立方网络的g正确邻结点条件诊断度研究
|
摘要
系统级故障诊断是保障多处理器计算机系统运行可靠性的一种重要手段。为了提高系统的诊断能力,增强系统的可靠性,在条件诊断度的基础上Peng等人进一步提出了g正确邻结点条件诊断度,g正确邻结点条件诊断度是一种更加适用于大规模多处理器计算机系统的故障诊断方式。以新型互连网络拓扑结构研究的最新成果——交换交叉立方网络为研究对象,在得到交换交叉立方网络的R_g点连通度的基础上,首次证得交换交叉立方网络(ECQ(s,t))在PMC模型下的g正确邻结点条件诊断度为2~g(s+2-g)-1,其中t≥s> g,进而通过模拟实验验证了结论的正确性和有效性。该研究对于理清交换交叉立方网络的可靠性能并有效推动交换交叉立方网络的应用和推广,有着非常重要的理论价值和现实意义。
System-level diagnosis is an important approach to ensuring the reliability of multiprocessor computer systems.In order to improve diagnostic ability and strengthen reliability, and motivated by the deficiency of the conditional diagnosability, peng et al. introduced a newly diagnosability, which is called g-good-neighbor conditional diagnosability. The g-good-neighbor conditional diagnosability is a new measure of system diagnosability, which is more suitable for massive multiprocessor computer systems. This paper takes exchanged crossed cube(ECQ(s,t)) as the object of study. By exploring the R_g vertex connectivity of ECQ(s,t), it determines, for the first time, the g-good-neighbor conditional diagnosability of ECQ(s,t) under the PMC model is 2~g(s + 2-g)-1 for t ≥ s > g. Furthermore, the correctness and validity of the conclusion are verified by simulation experiments. The research of ECQ(s,t) has important theoretical value and great practical significance for exploring the reliable performance of ECQ(s,t) and promoting the application and popularization of ECQ(s,t).
System-level diagnosis is an important approach to ensuring the reliability of multiprocessor computer systems.In order to improve diagnostic ability and strengthen reliability, and motivated by the deficiency of the conditional diagnosability, peng et al. introduced a newly diagnosability, which is called g-good-neighbor conditional diagnosability. The g-good-neighbor conditional diagnosability is a new measure of system diagnosability, which is more suitable for massive multiprocessor computer systems. This paper takes exchanged crossed cube(ECQ(s,t)) as the object of study. By exploring the R_g vertex connectivity of ECQ(s,t), it determines, for the first time, the g-good-neighbor conditional diagnosability of ECQ(s,t) under the PMC model is 2~g(s + 2-g)-1 for t ≥ s > g. Furthermore, the correctness and validity of the conclusion are verified by simulation experiments. The research of ECQ(s,t) has important theoretical value and great practical significance for exploring the reliable performance of ECQ(s,t) and promoting the application and popularization of ECQ(s,t).
引文
[1] Whitney H.Congruent graphs and the connectivity of graphs[M]//Hassler Whitney collected papers.[S.l.]:Birkhauser Boston,Inc,1992:150-168.
[2] Latifi S,Hegde M,Naraghipour M.Conditional connectivity measures for large multiprocessor systems[J].IEEE Transactions on Computers,1994,43(2):218-222.
[3] Najjar W,Gaudiot J L.Network resilience:A measure of network fault tolerance[J].IEEE Transactions on Computers,1990,39(2):174-181.
[4] Harary F.Conditional connectivity[J].Networks,1983,13(3):347-357.
[5] Esfahanian A,Hakimi S.On computing a conditional edge connectivity of a graph[J].Information Processing Letter,1988,27:195-199.
[6] Preparata F P,Metze G,Chien R T.On the connection assignment problem of diagnosable systems[J].IEEE Transactions on Electronic Computers,1967,16(12):848-854.
[7] Lai P L,Tan J M,Chang C P,et al.Conditional diagnosability measures for large multiprocessor systems[J].IEEE Transactions on Computers,2005,54(2):165-175.
[8] Peng S L,Lin C K,Tan J J M,et al.The g-good-neighbor conditional diagnosability of hypercube under PMC model[J].Applied Mathematics and Computation,2012,218(21):10406-10412.
[9] Wang S,Han W.The g-good-neighbor conditional diagnosability of n-dimensional hypercubes under the MM*model[M].[S.l.]:Elsevier North-Holland,Inc,2016.
[10]刘秀丽,原军,马雪.交换超立方体在PMC模型下的g好邻条件诊断度[J].太原科技大学学报,2014,35(5):390-393.
[11] Yuan J,Liu A,Ma X,et al.The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM*model[J].IEEE Transactions on Parallel and Distributed Systems,2015,26(4):1165-1177.
[12] Yuan J,Liu A,Qin X,et al.g-good-neighbor conditional diagnosability measures for 3-ary n-cube networks[J].Theoretical Computer Science,2016,626:144-162.
[13] Wei Y L,Xu M.The g-good-neighbor conditional diagnosability of locally twisted cubes[J].Journal of the Operations Research Society of China,2017,6:1-15.
[14] Lin L,Xu L,Wang D,et al.The g-good-neighbor conditional diagnosability of arrangement graphs[J].IEEE Transactions on Dependable and Secure Computing,2016,99:1-12.
[15] Li D,Lu M.The g-good-neighbor conditional diagnosability of star graphs under the PMC and MM*model[J].Theoretical Computer Science,2017,674:53-59.
[16] Li K Q,Mu Y P,Li K Q.Exchanged crossed cube:A novel interconnection network for parallel computation[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(11):2211-2219.
[17] Peter K K,Hsu W J,Pan Y.The exchanged hypercube[J].IEEE Transactions on Parallel and Distributed Systems,2005,16(9):866-874.
[18] Efe K.The crossed cube architecture for parallel compution[J].IEEE Transactions on Parallel and Distributed Systems,1992,3(5):513-646.
[19] Ning W T,Feng X L,Wang L.The connectivity of exchanged crossed cube[J].Information Processing Letters,2015,115(2):394-396.
[20] Ning W T.The super connectivity of exchanged crossed cube[J].Information Processing Letters,2016,116(2):80-84.
[21]郭晨,冷明,彭硕,等.交换交叉立方网络在MM模型下的条件诊断度研究[J].通信学报,2017,38(9):106-124.
[22]张大方,江招生.基于集团的系统级故障诊断研究[J].计算机学报,1998,21(4):308-314.
[2] Latifi S,Hegde M,Naraghipour M.Conditional connectivity measures for large multiprocessor systems[J].IEEE Transactions on Computers,1994,43(2):218-222.
[3] Najjar W,Gaudiot J L.Network resilience:A measure of network fault tolerance[J].IEEE Transactions on Computers,1990,39(2):174-181.
[4] Harary F.Conditional connectivity[J].Networks,1983,13(3):347-357.
[5] Esfahanian A,Hakimi S.On computing a conditional edge connectivity of a graph[J].Information Processing Letter,1988,27:195-199.
[6] Preparata F P,Metze G,Chien R T.On the connection assignment problem of diagnosable systems[J].IEEE Transactions on Electronic Computers,1967,16(12):848-854.
[7] Lai P L,Tan J M,Chang C P,et al.Conditional diagnosability measures for large multiprocessor systems[J].IEEE Transactions on Computers,2005,54(2):165-175.
[8] Peng S L,Lin C K,Tan J J M,et al.The g-good-neighbor conditional diagnosability of hypercube under PMC model[J].Applied Mathematics and Computation,2012,218(21):10406-10412.
[9] Wang S,Han W.The g-good-neighbor conditional diagnosability of n-dimensional hypercubes under the MM*model[M].[S.l.]:Elsevier North-Holland,Inc,2016.
[10]刘秀丽,原军,马雪.交换超立方体在PMC模型下的g好邻条件诊断度[J].太原科技大学学报,2014,35(5):390-393.
[11] Yuan J,Liu A,Ma X,et al.The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM*model[J].IEEE Transactions on Parallel and Distributed Systems,2015,26(4):1165-1177.
[12] Yuan J,Liu A,Qin X,et al.g-good-neighbor conditional diagnosability measures for 3-ary n-cube networks[J].Theoretical Computer Science,2016,626:144-162.
[13] Wei Y L,Xu M.The g-good-neighbor conditional diagnosability of locally twisted cubes[J].Journal of the Operations Research Society of China,2017,6:1-15.
[14] Lin L,Xu L,Wang D,et al.The g-good-neighbor conditional diagnosability of arrangement graphs[J].IEEE Transactions on Dependable and Secure Computing,2016,99:1-12.
[15] Li D,Lu M.The g-good-neighbor conditional diagnosability of star graphs under the PMC and MM*model[J].Theoretical Computer Science,2017,674:53-59.
[16] Li K Q,Mu Y P,Li K Q.Exchanged crossed cube:A novel interconnection network for parallel computation[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(11):2211-2219.
[17] Peter K K,Hsu W J,Pan Y.The exchanged hypercube[J].IEEE Transactions on Parallel and Distributed Systems,2005,16(9):866-874.
[18] Efe K.The crossed cube architecture for parallel compution[J].IEEE Transactions on Parallel and Distributed Systems,1992,3(5):513-646.
[19] Ning W T,Feng X L,Wang L.The connectivity of exchanged crossed cube[J].Information Processing Letters,2015,115(2):394-396.
[20] Ning W T.The super connectivity of exchanged crossed cube[J].Information Processing Letters,2016,116(2):80-84.
[21]郭晨,冷明,彭硕,等.交换交叉立方网络在MM模型下的条件诊断度研究[J].通信学报,2017,38(9):106-124.
[22]张大方,江招生.基于集团的系统级故障诊断研究[J].计算机学报,1998,21(4):308-314.