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）方体子网络可靠性的上下界趋于一致；当顶点可靠性较高时，利用近似评估方法得出的结果更为准确。     

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圈排除问题的递归算法

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

互连网络的新模型:多部群论模型

互连网络是超级计算机的重要组成部分.互连网络在很大程度上决定着超级计算机的性能.在1989年,S.B.Akers等提出了互连网络的群论模型,据此模型设计出了星网络、冒泡排序网络等一大批网络.尤其是星网络具有很多很好的性能,被认为是超立方体的替代品.但它们都有一个弱点:网络规模(结点数)为n!.即随着n的增大,n!增速太快,使得据此网络结构设计出的超级计算机升级较为困难,即扩展性较差.在群论模型的基础上提出了互连网络的多部群论模型,进而,据此模型设计出(n,k)-多部星网络、(n,k)-多部冒泡排序网络等多种网络.并证明星网络是(n,1)-多部星网络,而且(n,k)-多部星网络做到了规模(结点数)增大且增幅固定、直径增大缓慢、结点度不变,即有很好的可扩展性,其它(n,k)-多部网络也有类似的性能.     

3元n立方网络的2阶超连通性

为了度量以3元n立方网络为底层拓扑结构的并行与分布式系统的连通性,通过构造其2阶超割的方法,计算出当n不小于2时,3元n立方网络的2阶超连通度是6n-7。证明了对于以3元n立方网络为底层拓扑结构的并行与分布式计算机系统,当有不超过6n-8个节点发生故障且每个连通分支至少还有3个健康的节点时,该并行与分布式系统的任意两个节点之间仍然有一条无故障的通信线路。     

基于有故障区域的Mesh网络目标结点间的最短路由算法

Mesh网络是较早研究的且现在仍然是最为重要的、最有吸引力的网络模型之一。因其结构、规则简单及良好的可扩展性,易于VLSI(超大规模集成电路)的实现,网格(Mesh)网络不仅成为了许多理论研究的基础模型,而且也是许多大型多处理器并行计算机系统所采用的拓扑结构。给出了两种故障情形下的最短路由算法:1)当Mesh的行数大于等于3且列数大于等于3、出现一个矩形故障区域时,给出了任意两个无故障结点间的最短路由算法,并且计算出了路径长度；2)当Mesh的行数≥3且列数≥3、某个结点及其k跳以内的邻居结点出现故障时,给出了任意两个无故障结点间的最短路由算法,并且计算出了路径长度。     

BCube在2-限制连通度下的容错路由算法

BCube是具有良好性能的数据中心网络.相比传统的树形数据中心网络,BCube在扩展和容错性能方面都表现出很大的优势.目前,对于BCube的研究可以归结为对其逻辑图BCn,k(广义超立方体的一种特例)的研究,其中交换机被视为透明设备.在实际应用中,随着网络规模的不断增加,顶点发生故障已经成为一种常态.因此,研究网络的容错路由很有意义.目前,有不少关于BCn,k容错路由的研究,但其2-限制连通度下的容错路由目前还没有被研究.在提出容错路由算法之前,首先证明了BCn,k的2-限制连通度为3(k+1)(n-1)-2n,其中k≥3且n≥3.然后在此基础上提出了一个时间复杂度为O(κ(BCn,k)3)的容错路由算法,其中κ(BCn,k)=(k+1)(n-1)是BCn,k的连通度.该算法可以在故障顶点个数小于3(k+1)(n-1)-2n且每个无故障顶点至少有两个无故障邻居时找到任意两个不同的无故障顶点之间的一条无故障路径.     

关于修正冒泡排序网络的一簇猜想

修正冒泡排序网络是互连网络设计中的一个重要的Cayley图模型,关于修正冒泡排序网络的一簇猜想如下:对于任意的自然数n≥3,修正冒泡排序网络Yn是i个边不交的哈密尔顿圈以及n-2i个完美对集的并,其中1≤i≤︱n/2︱。证明了当i=1,2时,这个猜想是正确的。     

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方体构建的并行计算机系统指派子网络执行用户任务时,在点故障模型下灵活划分模式相比固定划分模式有着更好的容错能力。     

分布式并行计算在交通网络仿真中的应用*

根据交通网络仿真的并行特征采用域分解方法设计交通并行仿真系统的框架,把交通网络分为几个子网,集群系统的每个节点机分别负责其中的一个子网,提出基于车辆数负载的网络分割算法来平衡各子网的负载量,并分析子网之间的通信机理.同时,在基于MPI 的并行计算平台上实现设计的并行仿真系统.通过实例表明,提出的并行算法能大大提高交通网络仿真的速度和效率.     

基于神经网络的计算机网络性能评价

为多媒体网络定义一个合理有效的性能分析模型,以描述基于神经网络的计算机网络性能评价过程,其中包括评价指标测量值的预处理、神经网络结构设计、评价仿真以及仿真结果分析4个部分。仿真实验结果表明,基于神经网络的评价方法无须建立复杂的数学模型,能够对多个网络性能指标进行综合考虑,从而实现在给定输入负载下的网络性能判定。     

Development of fault tree for reliability studies of a data-processing system

In this paper a systematic approach is developed for generating the fault-tree logic, which is the basic requirement in any reliability studies of large complex systems using Monte Carlo simulation or deterministic approaches. The entire network is decomposed into sub-networks, each sub-network involving several loops, and it becomes quite easy to determine failure logic for these loops and thus for the subnetworks. Failure of such subnetworks between the source and the sink node leads to a major system failure and therefore this successive development results in a fault tree for the whole network.These loops can be automatically generated.

The failure event for each node in such an approach can also be accounted for. The advantage of the present methodology is that the fault-tree logic is automatically developed, which can be directly used as a sub-programme on a computer for various reliability studies of the system.     

基于神经网络的局域网故障诊断系统设计

为了实现准确有效地排除网络故障，根据局域网的特点，本文在分析现有计算机网络故障诊断方法不足的基础上，结合层次分类神经网络原理，提出了基于层次分类BP神经网络算法的局域网智能故障诊断系统，该系统具有层次分类策略、故障诊断策略、通信数据包采集、网络故障知识数据库、故障显示报警等功能，可以实现已知、未知故障的正确识别。通过对故障诊断算法和故障定位的仿真，结果表明故障诊断系统响应性能良好，故障误报率较低，具有一定的实用性。     

Minimal fault diameter for highly resilient product networks

We present a number of results related to the fault tolerance of Cartesian product networks. We start by presenting a method for building containers (i.e., sets of node-disjoint paths) between any two nodes of a product network based on given containers for the factor networks. Then, we show that the best achievable fault diameter (i.e., diameter under maximum fault conditions), under reasonable network regularity and connectivity conditions, is equal to the fault-free diameter plus one. The concept of high fault resilience is then defined. We then prove that if each factor network is highly resilient, then their Cartesian product has minimal fault diameter. We derive from these results that Cartesian products of several popular networks are highly resilient and have minimal fault diameter equal to diameter plus one. These results spare future efforts that would be needed to individually determine the fault diameter of such networks as has been the practice with previously studied networks.     

基于HSA的并行网络仿真系统设计与实现

为模拟不同激励下的网络行为,评估网络协议对网络结构发生变化时的反应,在研究了路由器及路由选择协议仿真技术的基础上,结合高性能计算机模拟体系结构HSA,提出并实现了一种并行网络环境仿真系统。通过对通用路由器节点、插件式路由协议、可替换流量节点以及网络拓扑生成部分的具体描述,对该系统作了详尽的探讨。最后通过一个环形拓扑,验证了该并行网络仿真系统与基于单机实现的网络仿真软件相比具有显著的优势。     

深海载人潜水器推进器系统故障诊断的新型主元分析算法

针对"蛟龙号"深海载人潜水器多推进器系统的故障检测与快速定位难题,将基于信度分配的模糊小脑神经网络(credit assignment-based fuzzy cerebellar model articulation controller, FCA–CMAC)应用于主元分析模型,提出一种基于主元分析(principal component analysis, PCA)的深海载人潜水器推进器系统故障诊断模型.首先,应用推进器系统正常运行的历史电流样本数据,由主元分析模型得到各推进器的电流预测值.其次,计算出故障检测统计量均方预测误差(squared prediction error, SPE),根据SPE值是否跳变,判断推进器系统有无故障发生.通过分别重构各推进器电流信号的SPE值对故障推进器进行定位和隔离.最后,通过对实际海试数据进行仿真处理说明了该算法的可行性,并通过与多层前馈神经网络(back propagation, BP)和常规小脑神经网络(cerebellar model articulation control-ler, CMAC)神经网络进行比较,说明基于FCA–CMAC神经网络的主元分析模型的优越性.     

Statistical Fault Analysis

Statistical Fault Analysis, or Stafan, is proposed as an alternative to fault simulation of digital circuits. This method defines Controllabilities and observabilities of circuit nodes as probabilities estimated from signal statistics of fault-free simulation. Special Procedures deal with these quantities at fanout and feedback nodes. The computed probabilities are used to derive unbiased estimates of fault detection probabilities and overall fault coverage for the given set of input vectors. Among Stafan's advantages, fault coverage and the undetected fault data obtained for actual circuits are shown to agree within five percent of fault simulator results, yet CPU time and memory demands fall far short of those required in fault simulation. The Computational complexity added to a fault-free simulator by Stafan grows only linearly with the number of circuit nodes.