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

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

作　　者：冯凯[1] 马鑫玉 FENG Kai;MA Xin-yu(School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China)

机构地区：[1]山西大学计算机与信息技术学院,太原030006

出　　处：《计算机科学》2021年第4期43-48,共6页Computer Science

基　　金：国家自然科学基金(61502286)。

摘　　要：并行计算机系统互连网络的拓扑性质对系统功能的实现起着重要的作用。为了精确度量基于(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)-冒泡排序子网络保持无故障状态的平均失效时间的计算公式,仿真实验表明理论结果与仿真结果趋于一致。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.

关 键 词：并行计算机系统 互连网络 (n k)-冒泡排序网络 子网络可靠性 概率故障 平均失效时间 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]