关键词: 多处理器系统, 互连网络, k元n方体, 子网络可靠性, 概率故障

Abstract: The k-ary n-cube possesses many desirable topological properties, and it has become one of the most commonly used interconnection topologies for building multiprocessor systems. The maintenance ability of existing some fault-free subnetworks in the interconnection network of a multiprocessor system plays an important role for the practical applications in the presence of failures. In order to accurately measure the fault tolerance on subnetworks of arbitrary size in a k-ary n-cube, the reliability of k-ary (n-m)-cube subnetworks in a k-ary n-cube in the presence of node failures was studied. When k is an odd integer and k≥3, an upper bound and a lower bound on the probability that at least one k-ary (n-m)-cube subnetwork is fault-free in a k-ary n-cube were established under the probabilistic fault condition, and an approximate method for evaluating this k-ary (n-m)-cube subnetwork reliability was proposed. The experiments show that the upper bound and the lower bound on the k-ary (n-m)-cube subnetwork reliability are gradually overlapping as the node reliability decreases and the evaluation result obtained by the proposed approximate method is relatively accurate when the node reliability is large.

Key words: multiprocessor system, interconnection network, k-ary n-cube, subnetwork reliability, probabilistic failure