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

概率故障条件下k元(n-m)方体子网络的可靠性

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

故障广义4元n方体中不同长度的路嵌入

k元n方体是传输信息的一种重要网络;研究含有故障点的广义4元n方体。证明了当其故障点数f≤n-1时;对每个整数l∈{2n-1;2n;…;4ⁿ-f-1};任意两个非故障点之间存在长度为l的无故障路。     

基于独立元的k近邻故障检测策略

k近邻故障检测(fault detection based on k nearest neighbors,FD–k NN)方法能够提高具有非线性和多模态特征过程的故障检测率.由于系统故障通常由潜隐变量异常变化引起,而该类型故障并不能被观测数据直观表现,因此直接在观测变量上执行FD–k NN方法,其故障检测率降低.本文旨在提高FD–k NN方法针对潜隐变量故障的检测能力,提出基于独立元的k近邻故障检测方法.首先,通过对观测数据应用独立元分析(independent component analysis,ICA)方法,获得独立元矩阵;接下来在独立元矩阵中应用FD–k NN方法进行故障检测.这等同于直接监控过程潜隐变量的变化,可以提高过程故障检测率.通过非线性实例仿真实验,证明本文方法检测潜隐变量故障是有效的;同时,在半导体蚀刻工艺过程的仿真实验中,与主元分析(principal component analysis,PCA)方法、核主元分析(kernel principal component analysis,KPCA)方法、基于主元分析的k近邻故障检测(principal component–based k nearest neighbor rule for fault detection,PC–k NN)方法和FD–k NN方法进行对比,实验结果进一步验证了本文方法的有效性.     

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

k元n方体是并行计算机系统最常用的互连网络拓扑结构之一.为了精确度量k元n方体中子网络的容错能力,研究了概率故障条件下k元n方体中k元(n-1)方体子网络的可靠性.当k(k≥3)为奇整数时,通过厘清k元n方体中不同k元(n-1)方体子网络之间的相交情形,得出了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立方子网。     

k元n方体互联网络性能分析与研究

从网络的拓扑、路由器、通道3方面分析了k元n方体互联网络的体系结构特征,建立了网络性能模型,并讨论了网络体系结构,应用程序和运行环境对网络性能的影响,以及网络性能的改进措施。     

k元n方体的可靠性评估

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

边故障[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]是最优的。     

Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cube

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. Given a set P of at most 2n − 2 (n ? 2) prescribed edges and two vertices u and v, we show that the 3-ary n-cube contains a Hamiltonian path between u and v passing through all edges of P if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as end-vertices. As an immediate result, the 3-ary n-cube contains a Hamiltonian cycle passing through a set P of at most 2n − 1 prescribed edges if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths.     

Conditional edge-fault Hamiltonicity of augmented cubes

The augmented cube is a variation of hypercubes, it possesses many superior properties. In this paper, we show that, for any n-dimensional augmented cube (n?3) with faulty edges up to 4n-8 in which each vertex is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result is optimal with respect to the number of faulty edges tolerated.     

基于位置敏感Embedding的中文命名实体识别

在基于条件随机场的中文命名实体识别任务中,现有表示学习方法学习到的特征存在语义表示偏差,给中文命名实体识别带来噪音。针对此问题,提出了一种基于位置敏感Embedding的中文命名实体识别方法。该方法将上下文位置信息融入到现有的Embedding模型中,采用多尺度聚类方法抽取不同粒度的Embedding特征,通过条件随机场来识别中文命名实体。实验证明,该方法学习到的特征缓解了语义表示偏差,进一步提高了现有系统的性能,与传统方法进行相比,F值提高了2.85%。     

一种彩色视频信息的隐秘传输方法

为了实现数据量较大的流媒体彩色视频信息的隐秘传输,描述了一种将low level MPEG—Ⅱ彩色视频信号隐藏在另一路main level MPEG—Ⅱ彩色视频中,并通过公共信道进行传输的方法。该方法利用人眼视觉特性,在宿主视频图像的DCT域,选择对人眼不敏感的中高频信息作为宿主可修改矢量,并提出了一个新的数据嵌入方法,由于该方法最多修改L bits宿主信息,就可在(2L 1)bits宿主可修改矢量中嵌入2L bits信息,因此有较高的数据嵌入率及较好隐蔽性。该方法也可用于其他流媒体及较大信息量信息的隐秘传输。该方法已在局域网上进行了模拟,并获得了较好的结果。     

Pancyclicity and bipancyclicity of conditional faulty folded hypercubes

A graph is said to be pancyclic if it contains cycles of every length from its girth to its order inclusive; and a bipartite graph is said to be bipancyclic if it contains cycles of every even length from its girth to its order. The pancyclicity or the bipancyclicity of a given network is an important factor in determining whether the network’s topology can simulate rings of various lengths. An n-dimensional folded hypercube FQ_n is an attractive variant of an n-dimensional hypercube Q_n that is obtained by establishing some extra edges between the vertices of Q_n. FQ_n for any odd n is known to be bipartite. In this paper, we explore the pancyclicity and bipancyclicity of FQ_n. For any FQ_n (n ? 2) with at most 2n − 3 faulty edges, where each vertex is incident to at least two fault-free edges, we prove that there exists a fault-free cycle of every even length from 4 to 2ⁿ; and when n ? 2 is even, we prove there also exists a fault-free cycle of every odd length from n + 1 to 2ⁿ − 1. The result is optimal with respect to the number of faulty edges tolerated.     

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

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