| In recent years,with the development of high-performance computing,the application field of multiprocessor systems has gradually expanded.The performance of the interconnection network has a decisive impact on the realization of the functions of the whole multiprocessor system.The k-ary n-cube network possesses many desirable topological properties,such as easy implementation,high bandwidth and low latency,and it has become one of the most commonly used interconnection network topologies for building multiprocessor systems.When failures occur in the interconnection network,it is expected that there will still be some smaller size subnetworks that can perform their functions normally.Therefore,the maintenance ability of system subnetworks plays an important role for the practical applications of system.However,scholars have only derived the reliability of k-ary(n-1)-cube subnetwork of k-ary n-cube networks,and the research on the reliability evaluation of subnetworks with arbitrary size in a k-ary n-cube network has not been studied deeply,which undoubtedly hinders the application and promotion of k-ary n-cube networks in multiprocessor systems.Based on this consideration,this thesis focuses on the k-ary(n-m)-cube subnetwork reliability of k-ary n-cube networks(k is an odd integer and is bigger than 2)from two perspectives: the existence probability of fault-free subnetworks and the mean time to failure to maintain a fault free state with disjoint subnetworks.Firstly,based on the probabilistic fault model,the existence probability of fault-free k-ary(n-m)-cube subnetworks of the k-ary n-cube networks was analyzed,an upper bound and a lower bound on the probability that at least one k-ary(n-m)-cube subnetwork was fault-free in a k-ary n-cube were established,and an approximate evaluation method of the subnetwork reliability based on Monte Carlo simulation was given.Experimental results show that there is a gradual convergence between the upper bound and lower bound on the k-ary(n-m)-cube subnetwork reliability as the node reliability decreases,and the evaluation result obtained by the approximate method is relatively accurate when the node reliability is large.In addition,the existence probability of fault-free k-ary(n-m)-cube subnetworks of k-ary n-cube networks with the same size but with different topologies was compared and analyzed.The experimental results show that when the size of the k-ary n-cube network is given,the k-ary n-cube network constructed by selecting a smaller n has better subnetwork maintenance ability.Secondly,under the node fault model and the link fault model,the reliability of k-ary(n-m)-cube subnetwork of k-ary n-cube network was evaluated by the fixed partition pattern respectively,the mean time to failure to maintain a fault free state of k-ary(n-m)-cube subnetworks with different numbers were obtained,and accuracy of the theoretical results was verified by simulation experiments.Furthermore,the mean time to failure to maintain a fault free state of k-ary(n-m)-cube subnetworks in k-ary n-cube networks with the same size but with different topologies under the node fault model was compared and analyzed.The experimental results show that when the size of the k-ary n-cube network is given,the mean time to failure to maintain a fault free state of the k-ary(n-m)-cube subnetwork of the k-ary n-cube network constructed by selecting a smaller n is higher.Finally,a reliability analysis system for k-ary(n-m)-cube subnetwork based on Matlab was designed.Using this system,the existence probability of the fault-free k-ary(n-m)-cube subnetworks can be estimated,and the reliability of the k-ary(n-m)-cube subnetwork can also be evaluated based on the mean time to failure.The research results of this thesis can offer a theoretical reference for the design of algorithms of multiprocessor systems constructed with the k-ary n-cube networks as the underlying topology structure. |
