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)-冒泡排序子网络的...     

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]立方体（记为[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]是最优的。     

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-立方体网络

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

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

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

k元n方体具有许多优良特性,已成为多处理器系统最常用的互连网络拓扑结构之一。当系统互连网络中发生故障时,系统子网络的保持能力对系统实际应用至关重要。为了精确度量k元n方体中任意规模子网络的容错能力,研究了有故障发生时k元n方体中k元（n-m）方体子网络的可靠性。当k(k≥3)为奇整数时,在概率故障条件下得出了k元n方体中存在无故障k元（n-m）方体子网络的概率的上界和下界,并给出了该可靠性的一种近似评估方法。实验结果表明,随着顶点可靠性的降低,k元（n-m）方体子网络可靠性的上下界趋于一致;当顶点可靠性较高时,利用近似评估方法得出的结果更为准确。     

在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]。     

k元n—立方体网络的死锁特征剖析

研究死锁形成几率随网络参数的变化规律 ,对于选择合适的寻径算法、改良网络设计方案都具有重要意义 .环形等多种网络都是 k元 n-立方体网络系列的拓扑同构体 .因此 ,k元 n-立方体网络死锁特征的研究结果具有一定的普遍适用性 .本文根据刻画死锁特征的死锁循环密度属性划分死锁类型 .利用死锁类型分析寻径适应性、物理通道、虚拟通道、缓冲区大小 ,消息长度以及缓冲区结构等参数对死锁形成几率的影响     

CIMS串行生产线可靠性建模与分析的研究

本文对CIMS串行生产线可靠性建模与分析进行了综述，对两级和多级串行生产线的问题进行了讨论和分析，提出了ＣＩＭＳ可靠性研究的一些问题。     

神经网络在容错系统可靠性分析中的应用

由于神经网络具有大规模并行、集团运算等特点,以及强大的自适应、自学习、容错和推广能力,从而使神经网络在可靠性工程的许多领域得到应用,本文将循环前馈神经网络应用到容错系统的可靠性分析中,达到了简化容错系统可靠性分析与设计的目的。并且,由于神经网络具有的学习与自适应的功能,使它在分析较为复杂的容错系统的可靠
靠性时,具有更强的竞争力。