关键词: 并行计算机系统, 互连网络, k元n方体, 完美匹配, 条件故障

Abstract: To measure the ability of k-ary n-cube to remain the property of having a perfect matching or an almost perfect matching in the presence of failures, by analysis of constructions of the fault sets that make the k-ary n-cube having neither a perfect matching nor an almost perfect matching under the conditional fault model, the minimum number of failures that make the k-ary n-cube unmatchable under the conditional fault model was studied. When k ≥ 4 is even and n ≥ 2, the exact value of the fault-tolerant parameter for k-ary n-cube was obtained and all the corresponding minimum fault sets were characterized. When k ≥ 3 is an odd number and n ≥ 2, a sharp lower bound and a sharp upper bound on the fault tolerance parameter for k-ary n-cube were given. The results indicate that the parallel computer system, which takes the k-ary n-cube with odd k as underlying interconnection topology, has good ability to remain the property of having a perfect matching or an almost perfect matching under the conditional fault model. Moreover, this system is still matchable if the number of failures does not exceed 2n and at most 4n-3 failures could make this system unmatchable.

Key words: parallel computer system, interconnection network, k-ary n-cube, perfect matching, conditional failure