k元（n-1）方体子网络可靠性的近似评估方法

多处理器系统互连网络的拓扑性质对系统功能的实现起着重要的作用。k元n方体网络的子网络可靠性是以k元n方体为拓扑结构构建的多处理器系统处理计算任务时需要考虑的一个重要因素。为了精确高效地度量概率故障条件下k元n方体中k元（n-1）方体子网络的可靠性，提出基于反向传播（BP）神经网络的k元（n-1）方体子网络可靠性的近似评估方法。首先，利用蒙特卡洛仿真方法和k元（n-1）方体子网络可靠性的已有上下界给出用于训练BP神经网络的数据集的生成方法；其次，基于生成的训练数据集构造用于评估k元（n-1）方体子网络可靠性的BP神经网络模型；最后，对BP神经网络模型得出的k元（n-1）方体子网络可靠性的近似评估结果进行了分析，并与近似计算公式和基于蒙特卡洛的评估方法的结果进行了对比。与近似计算公式相比，所提方法得出的结果更为精确；与基于蒙特卡洛的评估方法相比，所提方法的评估耗时平均减少了约59%。实验结果表明，所提方法在兼顾精度和效率方面具有一定优势。     

k元n方体的可靠性评估

并行计算机系统功能的实现很大程度上依赖于系统互连网络的性能。为了精确度量以k元n方体为底层拓扑结构的并行计算机系统的容错能力,研究了点故障模型下k元n方体中k元（n-1）方体子网络的可靠性。当k ≥ 3且为奇数时,分别在固定划分模式和灵活划分模式下对k元n方体中不同数目的k元（n-1）方体子网络保持无故障状态的平均失效时间进行了分析,并得出了这一子网络可靠性评估参数的计算公式。结果表明,当基于k为奇数的k元n方体构建的并行计算机系统指派子网络执行用户任务时,在点故障模型下灵活划分模式相比固定划分模式有着更好的容错能力。     

(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)-冒泡排序子网络保持无故障状态的平均失效时间的计算公式,仿真实验表明理论结果与仿真结果趋于一致。     

k元n方体网络的子网络可靠性

并行计算机系统互连网络的拓扑性质对系统功能的实现起着重要的作用。为了衡量基于[k]元[n]方体网络构建的并行计算机系统的容错能力,研究了边故障模型下[k]元[n]方体网络中[k]元[(n-1)]方体子网络的可靠性。当[k(k≥3)]为奇数时,分别在固定划分模式和灵活划分模式下得出了[k]元[n]方体网络中不同数目的[k]元[(n-1)]方体子网络保持无故障状态的平均失效时间的计算公式,并通过仿真实验验证了理论结果的精确性。研究表明,当[k]为奇数的[k]元[n]方体网络中有边故障发生时,相比固定划分模式,在灵活划分模式下不同数目的[k]元[(n-1)]方体子网络保持无故障状态的平均失效时间更大。     

k元n维冒泡排序网络的子网排除

在并行计算机系统中,元器件和线路故障普遍存在,而系统的容错能力可以通过其底层基础网络的拓扑性质衡量。为了精确度量以k元n维冒泡排序网络为底层拓扑结构的并行计算机系统的容错能力,结合其层次结构和子网划分特征,分别提出了节点故障模型和线路故障模型下攻击该网络中所有k－m元n－m维冒泡排序子网络的算法,确定了需要攻击的最优节点集合和最优线路集合。根据算法可得:当2≤k≤n－2,m≤k－1时,攻击k元n维冒泡排序网络中所有的k－m元n－m维冒泡排序子网络,在节点故障模型下需要攻击至少C^m_nm!个节点,在边故障模型下需要攻击至少C^m_nm!条线路。     

边故障[k]元[n]立方体的超级哈密顿交织性

[k]元[n]立方体（记为[Qkn]）是优于超立方体的可进行高效信息传输的互连网络之一。[Qkn]是一个二部图当且仅当[k]为偶数。令[G[V0,V1]]是一个二部图,若（1）任意一对分别在不同部的顶点之间存在一条哈密顿路,且（2）对于任意一点[v∈Vi],其中[i∈{0,1}],[V1-i]中任意一对顶点可以被[G[V0,V1]-v]中的一条哈密顿路相连,则图[G[V0,V1]]被称为是超级哈密顿交织的。因为网络中的元件发生故障是不可避免的,所以研究网络的容错性就尤为重要。针对含有边故障的[Qkn],其中[k4]是偶数且[n2],证明了当其故障边数至多为[2n-3]时,该故障[Qkn]是超级哈密顿交织图,且故障边数目的上界[2n-3]是最优的。     

泡形互连网络的条件连通性度量

n维泡形网络是设计大规模多处理机系统时最常用的互连网络拓扑结构之一,它以n维泡形图Bn为数学模型。F是连通图G的顶点子集,使得G-F不再连通且G-F的每个连通分支都有至少有n个顶点的F的势叫做G的Rk连通度。Rk连通度是衡量网络可靠性的一个重要参数。一般来说,网络的Rk连通度越大,其可靠性越高。研究了n维泡形网络的 k连通性;证明了在n维泡形网络中,当n≥3时,其R1连通度为2n-4;当n≥4 时,其R2连通度为4n-12。     

星型网络的3-限制边连通性

星型互连网络是并行与分布式处理领域中最流行的互连网络之一,它以n维星图作为拓扑结构。k-限制边连通度是衡量网络的可靠性的参数之一。一般来说,一个网络的k-限制边连通度越大,其连通性就越好。研究了星型互连网络的k限制边连通度;证明了当n≥3时,n维星型互连网络的3-限制连通度为3n－7。     

k元n方体的条件强匹配排除

为了度量发生故障时k元n方体对其可匹配性的保持能力,通过剖析条件故障下使得k元n方体中不存在完美匹配或几乎完美匹配所需故障集的构造,研究了条件故障下使得k元n方体不可匹配所需的最小故障数。当k ≥ 4为偶数且n ≥ 2时,得出了k元n方体这一容错性参数的精确值并对其所有相应的最小故障集进行了刻画;当k ≥ 3为奇数且n ≥ 2时,给出了该k元n方体容错性参数的一个可达下界和一个可达上界。结果表明,选取k为奇数的k元n方体作为底层互连网络拓扑设计的并行计算机系统在条件故障下对其可匹配性有良好的保持能力;进一步地,该系统在故障数不超过2n时仍是可匹配的,要使该系统不可匹配至多需要4n-3个故障元。     

单向k-元n-立方体网络

单向[k]-元[n]-立方体是指具有单向边的[k]-元[n]-立方体互连网络拓扑。当网络包含的顶点数目较大时,比起传统的双向[k]-元[n]-立方体,单向?[k]-元[n]-立方体对通信硬件复杂性的要求更低一些。提出了[k]-元[n]-立方体的一个定向,使得定向后的单向[k]-元[n]-立方体[UQkn]有一些良好的性质。证明了[UQkn]是正则的,极大弧连通的,具有迭代结构的且[UQkn]的直径是小的。此外,提出了一个简单的多项式时间路由算法。     

带有条件故障边的k元2方体的圈嵌入

[k]元[n]方体已经成为分布式储存并行系统最常用的网络拓扑结构。研究带有条件故障边的[k]元2方体的圈嵌入问题,证明了在[k≥4]为偶整数的[k]元2方体中,若其故障边数不超过3且每个顶点至少与两条非故障边相关联,那么该[k]元2方体存在长度在4到[k2]间的任意偶长的无故障圈。     

在PMC模型下单向k元n立方体的诊断度

图的连通度和诊断度是与互连网络的可靠性密切相关的两个参数,而[g]好邻连通度和[g]好邻诊断度是比连通度和诊断度更精确的指标。[k]元[n]立方体是多处理机系统的最常用网络之一,而单向[k]元[n]立方体是指具有单向边的[k]元[n]立方体。证明了当[k≥3,n≥3]时,单向[k]元[n]立方体在PMC模型下的[1]好邻连通度是[k(n-1)],诊断度是[n]且[1]好邻诊断度是[kn-1]。     

3元◢n◣立方体网络的◢t/k◣可诊断度研究

可诊断度是评估多处理器系统可靠性的一个关键指标.t/k诊断策略通过允许至多k个无故障处理器被误诊为故障处理器,从而极大提高了系统的可诊断度.与t可诊断度和t1/t1可诊断度相比,t/k可诊断度可以更好地反映实际系统的故障模式.3元n立方是一种性质优良并且应用广泛的网络拓扑,在许多分布式多处理器的构建中被用做底层网络.根据一些引理以及确定系统为t/k可诊断的充分条件,研究得出当n≥3及0≤k≤n,3元n立方是tk,n/k-可诊断的,其中tk,n=2(k+1)n-(k+1)(k+2).这个结果显示,在选择恰当的k值时,3元n立方的t/k可诊断度tk,n远大于其t可诊断度2n和t1/t1可诊断度4n-3.     

无K3子图的互连网络在PMC模型下的条件可诊断度

可诊断度是衡量一个互连网络可靠性的重要指标,常用来评估当系统中某些结点出现故障时将故障结点准确找出来的能力。PMC模型是一种经典的可诊断模型,被广泛地应用于系统诊断中,到目前为止,已经有很多的研究者基于PMC模型做出了大量研究成果。本文在PMC模型的基础上,对于不存在K3子图的网络的条件可诊断性进行了研究,并证明了当δ(G)≥9且任两个结点的共同邻居数不大于2时,无K3子图的图G是2δ(G)-1条件可诊断的;当δ(G)≥6且任两个结点的共同邻居数不大于2时,二部图G是2δ(G)-1条件可诊断的。     

k元船方体网络的可靠性

[k]元[n]方体[Qkn]是设计大规模多处理机系统时最常用的互连网络拓扑结构之一。对于[1≤m≤n-1],设[F]是[Qkn]中的一个由非空点集[VF]和非空边集[EF]构成的故障集,满足[Qkn-F]中不存在[Qkn-m]且[VF]破坏的[Qkn-m]的集合与[EF]破坏的[Qkn-m]的集合互不包含。设[f＊（n,m）]是破坏[Qkn]中的所有子立方[Qkn-m]所需要的故障集[F]的最小基数。证明了对于奇数[k≥3],[fk（n,1）]为[k＋1],[fk（n,n-1）]为[kn-1-1＋n],[f＊（n,m）]的上下界分别为[Cm-1n-1km＋Cm-1n-2km-1]和[km]。举例说明了上界[Cm-1n-1km＋Cm-1n-2km-1]是最优的。     

k元n树互联网络的2-终点可靠性研究

k元n树是一种用于大规模并行处理的高性能互联网络的拓扑结构。该文提出计算k元n树的2-终点可靠性的递归算法,其计算复杂度为O(n)。结合市场上网络元器件可靠性的实际情况,对k元n树的2-终点可靠性进行了分析。当n趋于无穷大时,计算出k元n树的2-终点可靠性的下限。     

k元n立方网络的k圈排除问题的递归算法

为了度量以k元n立方网络为底层网络拓扑的并行计算机系统的容错能力,通过构造k元n立方网络中使得所有的k元1立方子网都发生故障的最小节点集合的方法,提出求解其k元1立方子网排除点割集的一种递归算法;证明了要使k元n立方网络中所有k元1立方子网都发生故障至少需要破坏掉kn-1个节点。结果表明,在不超过kn-1-1个节点被破坏的情况下,以k元n立方网络为底层拓扑构建的并行计算机系统中依然存在无故障的k元1立方子网。     

星网的4-限制边连通度

星网是并行与分布式处理系统中最流行的互连网络之一,它以n维星图作为拓扑结构。k-限制边连通度是衡量网络可靠性的重要参数之一;一般地,网络的k-限制边连通度越大,它的连通性就越好。研究了星网的k-限制边连通度,证明了当n≥4时,n维星网的4-限制连通度为4n－10。     

PMC诊断模型下的网络条件可诊断度研究

可诊断度是确保互连网络的可靠性的重要指标,是当网络的节点发生故障时,快速准确地找出网络中故障节点的能力。PMC模型是一种传统的系统诊断模型,迄今已有许多相关的研究成果并已被广泛地应用。本论文基于PMC诊断模型,在每个节点都有一个无故障邻居节点的条件下,证明当δ_E (G)≥15 且δ(G)≥5时,无K_3子图的图G δ_E 1条件可诊断;当δ_E (G)≥7且δ(G)≥3时,二部图G δ_E 1条件可诊断。     

BSCC(4,k)的Hamilton圈分解

冒泡排序连通圈网络BSCC(n)是一类重要的互连网络。2010年师海忠提出了如下猜想:冒泡排序连通圈网络BSCC(n)(n≥4)可分解为边不交的Hamilton圈和完美对集的并。记BSCC(n)为BSCC(n,0),对BSCC(n,0)的每个顶点用一个三角形代替,得到新网络BSCC(n,1),对BSCC(n,1)的每个顶点用三角形代替得到BSCC(n,2),类似迭代k次得新网络BSCC(n,k)。师海忠进一步提出猜想2:BSCC(n,k)可分解为边不交的一个Hamilton圈和一个完美对集的并。证明了BSCC(4,k)可分解成边不交的一个Hamilton圈和一个完美对集的并。