Abstract: The k-ary n-cube is one of the most attractive interconnection network topologies for parallel computing systems.In order to accurately measure the fault tolerance on subnetworks in a k-ary n-cube,the k-ary (n－1)-cube reliability in a k-ary n-cube under the probabilistic fault model is studied.When k is an odd integer and k≥3,a lower bound on the k-ary (n－1)-cube reliability in a k-ary n-cube under the probability fault model is derived by clarifying the intersections of k-ary (n－1)-cube subnetworks in a k-ary n-cube,and an approximate k-ary (n－1)-cube reliability result is obtained.The approximation result is shown to be close to the simulation result,and these two results are getting overlapped as the node reliability decreases.Moreover,an algorithm is given for searching fault-free k-ary (n－1)-cubes in a k-ary n-cube in the presence of node failures,and the experimental results demonstrate the effectiveness of the proposed algorithm.

Key words: k-ary n-cube, Interconnection network, Parallel computer system, Probabilistic failure, Subnetwork reliability