关键词: 并行计算机系统, 互联网络, 容错, k元n立方, 节点故障, 可靠性

Abstract: In order to measure the fault tolerance ability of the parallel computers which take the k-ary n-cube as underlying topology, by constructing the minimum node set whose removal will lead to every k-ary 1-cube in the k-ary n-cube faulty, a recursive algorithm for finding the k-ary 1-cube subnet preclusion node cut of the k-ary n-cube was proposed. It is proved that at least kn-1 nodes need to be damaged if a rival wants to destroy all k-ary 1-cubes in the k-ary n-cube. The result indicates that there are still undamaged k-ary 1-cubes in the parallel computers which take the k-ary n-cube as underlying topology if the number of the faulty nodes does not exceed kn-1-1.

Key words: parallel computer system, interconnection network, fault tolerance, k-ary n-cube, node failure, reliability