(n,k)-冒泡排序网络的子网络可靠性

并行计算机系统互连网络的拓扑性质对系统功能的实现起着重要的作用。为了精确度量基于(n,k)-冒泡排序网络构建的并行计算机系统的子网络容错能力,建立了(n,k)-冒泡排序网络中(n-m,k-m)-冒泡排序子网络与特定字符串之间的一一对应关系,研究了点故障模型下(n,k)-冒泡排序网络中(n-m,k-m)-冒泡排序子网络的可靠性。当2≤k≤n-2,1≤m≤k-1时,首先在概率故障条件下给出了(n,k)-冒泡排序网络中存在无故障的(n-m,k-m)-冒泡排序子网络的概率估计,并通过仿真实验验证了所得结果的精确性;其次,得出了不同数目的(n-m,k-m)-冒泡排序子网络保持无故障状态的平均失效时间的计算公式,仿真实验表明理论结果与仿真结果趋于一致。

Subnetwork Reliability of (n,k)-bubble-sort Networks

Topological properties of the interconnection network of a parallel computer system play an important role in realizing functions of the system.In order to measure the fault tolerance abilities of subnetworks in the parallel computer system which is built based on the(n,k)-bubble-sort network,the one-to-one relation between(n-m,k-m)-bubble-sort subnetworks of the(n,k)-bubble-sort network and specific strings is constructed,and the reliability of(n-m,k-m)-bubble-sort subnetworks in the(n,k)-bubble-sort network is studied under the node fault model.Assuming that 2≤k≤n-2 and 1≤m≤k-1,the probability that at least one(n-m,k-m)-bubble-sort subnetwork is fault-free in an(n,k)-bubble-sort network under the probabilistic fault condition is firstly given,and the simulation experiments demonstrate the accuracy of the given results.Then the calculation formula of the mean time to failure to maintain the fault-free status of different number of(n-m,k-m)-bubble-sort subnetworks is obtained,and the theoretical results are shown to be in accordance with the simulation results.