k元n维冒泡排序网络的子网排除
|
摘要
在并行计算机系统中,元器件和线路故障普遍存在,而系统的容错能力可以通过其底层基础网络的拓扑性质衡量。为了精确度量以k元n维冒泡排序网络为底层拓扑结构的并行计算机系统的容错能力,结合其层次结构和子网划分特征,分别提出了节点故障模型和线路故障模型下攻击该网络中所有k-m元n-m维冒泡排序子网络的算法,确定了需要攻击的最优节点集合和最优线路集合。根据算法可得:当2≤k≤n-2,m≤k-1时,攻击k元n维冒泡排序网络中所有的k-m元n-m维冒泡排序子网络,在节点故障模型下需要攻击至少C_n~mm!个节点,在边故障模型下需要攻击至少C_n~mm!条线路。
In the real parallel computer systems,faults of processors and links are inevitable,and the fault tolerance ability of a system can be evaluated by the performance of its interconnection network.In order to measure the fault tolerance abilities of the parallel computers which take(n,k)-bubble-sort networks as underlying topologies,combining the hierarchical structures and sub-network partitions' characters of(n,k)-bubble-sort networks,an algorithm of the problem that destroy all the(n-m,k-m)-bubble-sort networks in the(n,k)-bubble-sort network under the node fault model and the link fault model was proposed,and the optimal attacking nodes set and the optimal attacking links set were obtained.According to the algorithm,to destroy all the(n-m,k-m)-bubble-sort networks in the(n,k)-bubblesort network,at least C_n~mm!nodes or C_n~mm!links ought to be faulty under the node fault model and the link fault model,respectively,where 2≤k≤n-2 and m≤k-1.
In the real parallel computer systems,faults of processors and links are inevitable,and the fault tolerance ability of a system can be evaluated by the performance of its interconnection network.In order to measure the fault tolerance abilities of the parallel computers which take(n,k)-bubble-sort networks as underlying topologies,combining the hierarchical structures and sub-network partitions' characters of(n,k)-bubble-sort networks,an algorithm of the problem that destroy all the(n-m,k-m)-bubble-sort networks in the(n,k)-bubble-sort network under the node fault model and the link fault model was proposed,and the optimal attacking nodes set and the optimal attacking links set were obtained.According to the algorithm,to destroy all the(n-m,k-m)-bubble-sort networks in the(n,k)-bubblesort network,at least C_n~mm!nodes or C_n~mm!links ought to be faulty under the node fault model and the link fault model,respectively,where 2≤k≤n-2 and m≤k-1.
引文
[1]LATIFI S.A study of fault tolerance in star graph[J].Information Processing Letters,2007,102(5):196-200.
[2]LATIFI S,SABERINIA E,WU X.Robustness of star graph network under link failure[J].Information Sciences,2008,178(3):802-806.
[3]WALKER D,LATIFI S.Improving bounds on link failure tolerance of the star graph[J].Information Sciences,2010,180(13):2571-2575.
[4]WANG S,YANG Y.Fault tolerance in bubble-sort graph networks[J].Theoretical Computer Science,2012,421:62-69.
[5]YANG Y X,WANG S Y.Recursive algorithm for k-cycle preclusion problem in k-ary n-cubes[J].Journal of Computer Applications,2013,33(9):2401-2403.(in Chinese)杨玉星,王世英.k元n立方网络的k圈排除问题的递归算法[J].计算机应用,2013,33(9):2401-2403.
[6]YANG Y,WANG S,LI J.Subnetwork preclusion for bubblesort networks[J].Information Processing Letters,2015,115(1):817-821.
[7]WANG S,ZHANG G,FENG K.Fault tolerance in k-ary n-cube networks[J].Theoretical Computer Science,2012,460:34-41.
[8]WANG S,FENG K.Fault tolerance in the arrangement graphs[J].Theoretical Computer Science,2014,533:64-71.
[9]FENG K,WANG S,ZHANG G.Link failure tolerance in the arrangement graphs[J].International Journal of Foundations of Computer Science,2015,26(2):241-254.
[10]WANG M,YANG W,GUO Y,et al.Conditional fault tolerance in a class of Cayley graphs[J].International Journal of Computer Mathematics,2016,93(1):678-682.
[11]SHAWASH N.Relationships among popular interconnection networks and their common generalization[D].Oakland,USA:Oakland University,2008.
[12]CHENG E,LIPTAK L,SHERMAN D.Matching preclusion for the(n,k)-bubble-sort graphs[J].International Journal of Computer Mathematics,2010,87(11):2408-2418.
[13]BONDY J A,MURTY U S R.Graph Theory[M].New York:Springer Press,2008:624-626.
[2]LATIFI S,SABERINIA E,WU X.Robustness of star graph network under link failure[J].Information Sciences,2008,178(3):802-806.
[3]WALKER D,LATIFI S.Improving bounds on link failure tolerance of the star graph[J].Information Sciences,2010,180(13):2571-2575.
[4]WANG S,YANG Y.Fault tolerance in bubble-sort graph networks[J].Theoretical Computer Science,2012,421:62-69.
[5]YANG Y X,WANG S Y.Recursive algorithm for k-cycle preclusion problem in k-ary n-cubes[J].Journal of Computer Applications,2013,33(9):2401-2403.(in Chinese)杨玉星,王世英.k元n立方网络的k圈排除问题的递归算法[J].计算机应用,2013,33(9):2401-2403.
[6]YANG Y,WANG S,LI J.Subnetwork preclusion for bubblesort networks[J].Information Processing Letters,2015,115(1):817-821.
[7]WANG S,ZHANG G,FENG K.Fault tolerance in k-ary n-cube networks[J].Theoretical Computer Science,2012,460:34-41.
[8]WANG S,FENG K.Fault tolerance in the arrangement graphs[J].Theoretical Computer Science,2014,533:64-71.
[9]FENG K,WANG S,ZHANG G.Link failure tolerance in the arrangement graphs[J].International Journal of Foundations of Computer Science,2015,26(2):241-254.
[10]WANG M,YANG W,GUO Y,et al.Conditional fault tolerance in a class of Cayley graphs[J].International Journal of Computer Mathematics,2016,93(1):678-682.
[11]SHAWASH N.Relationships among popular interconnection networks and their common generalization[D].Oakland,USA:Oakland University,2008.
[12]CHENG E,LIPTAK L,SHERMAN D.Matching preclusion for the(n,k)-bubble-sort graphs[J].International Journal of Computer Mathematics,2010,87(11):2408-2418.
[13]BONDY J A,MURTY U S R.Graph Theory[M].New York:Springer Press,2008:624-626.