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

Abstract: In order to measure the ability of k-ary n-cubes 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. Let n≥2. The exact value of this parameter is established for k-ary n-cubes with even k≥4 and all the corresponding minimum faulty sets are characterized. Moreover, a sharp lower bound and a sharp upper bound on this parameter are obtained for k-ary n-cubes with odd k≥3. 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