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!条线路。

(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-m)方体子网络的可靠性

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

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立方体网络中经过匹配的指定二不交路覆盖的存在性问题进行了探讨。设Q_(n)^(k)是一个k元n立方体网络,其中n≥4、k≥4是偶数,M是Q_(n)^(k)的匹配,F是Q_(n)^(k)的故障边集。若(u,u′)和(v,v′)是Q_(n)^(k)中任意2条不相邻的边,满足{u,v}∩V(M)=Ф和(u′,v′)∈M,则当M+F≤2n-7时,在Q_(n)^(k)-F中存在2条顶点不相交的路Pu,u′和Pv,v′,经过匹配M且V(Pu,u′)∪V(Pv,v′)=V(Q_(n)^(k))。

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方体Qkn是设计大规模多处理机系统时最常用的互连网络拓扑结构之一。对于1≤m≤n-1,设F是Qk n中的一个由非空点集V F和非空边集E F构成的故障集,满足Qkn-F中不存在Qkn-m且VF破坏的Qkn-m的集合与EF破坏的Qkn-m的集合互不包含。设f*(n,m)是破坏Qkn中的所有子立方Qkn-m所需要的故障集F的最小基数。证明了对于奇数k≥3,f*(n,1)为k+1,f*(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立方体拓扑的无线传感器网络广播策略

研究了无线传感器网络的广播策略,提出一个冲突避免立方体广播算法CACB(Collision Avoidance Cube Broadcast)。CACB基于对k元n立方体结构的网络研究广播策略。CACB算法采用时钟准同步的方法,按照为序寻径的方式,确定每一个时间步应该如何去路由信息。实验使用OPNET软件进行仿真,仿真结果表明基于k元n立方体的无线传感器网络的广播算法CACB和传统的广播策略相比,能够减少最大端到端的时延,降低网络冲突,减少节点能量消耗,延长整个网络寿命,提高了网络的吞吐量。

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元(n-1)方体子网络的算法,并通过实例验证了该算法的有效性。

一种k元n方网络中的全局自适应负载均衡路由算法

路由算法的设计是后元n方网络研究中的关键问题之一，全局自适应负载均衡路由算法对于各种业务模式都可以达到较高的吞吐率。提出了一种高效的，基于检测的避免路由死锁的新方案，并且给出了一种基于该方案的全局自适应负载均衡路由算法，比已有同类算法具有更强的路由自适应性。仿真实验表明，该算法对于良性业务模式可提高吞吐率18％，对于恶性业务模式可提高吞吐卒10％-24％。

k元n立方体网络的容错路由

本文提出了k元n立方的m子立方体连通图的定义,讨论了该图的连通性。利用k元n立方的m子立方体连通图的概念提出了可容纳大量错误结点的容错路由算法,并对算法的时间复杂度做了分析。

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

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

故障k元n立方体网络中的多播容错路由算法

本文在k元n立方的m子立方体连通的k元n立方体网络中,讨论了多播容错路由算法,使得k元n立方体网络中多播路由不止适合结点故障、也适合链路故障,同时讨论了算法的时间复杂度。

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方体因其良好的拓扑性质和特殊的结构成为多处理机系统最常用的互连网络之一.图的局部连通度是衡量网络可靠性的重要参数.极大局部连通图是以局部连通度为度量指标时最可靠的一类网络.证明了具有至多2n-2个故障点的k元n方体网络仍具有极大局部连通性.

k元n方体网络的4-限制边连通度

l-限制边连通度是边连通度的推广,可更精确地度量网络的可靠性.k元n方体网络因其特殊的结构和良好的性质成为多处理机系统最常用的互连网络之一.证明了k元n方体的4-限制边连通度和它的最小4-度相等,并确定了它们的值.所得结果说明,当用4-限制边连通度作为度量指标时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方体对其可匹配性的保持能力,通过剖析条件故障下使得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立方体Qnk是互连网络设计中最重要的拓扑之一。本文研究了既有故障点又有故障边的情况下,Qnk的边泛圈性,证明了对给定的整数n≥2和奇数k≥3,F是k元n方体Qnk中故障点和故障边的集合。若F中元素个数至多为2n-3,则QQnk-F是(k+1)-边泛圈的。

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