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方体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方体的子网络可靠性研究

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方体互联网络性能分析与研究

从网络的拓朴、路由器、通道3方面分析了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方体的最优条件匹配排除集

设E是图G的一个边子集,若G-E中既不包含孤立点,也没有完美匹配和几乎完美匹配,则称E为G的一个条件匹配排除集.边数最少的条件匹配排除集,称为最优条件匹配排除集.文章给出了k元n方体的最优条件匹配排除集.

概率故障条件下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立方体Qnk是互连网络设计中最重要的拓扑之一。本文研究了既有故障点又有故障边的情况下,Qnk的边泛圈性,证明了对给定的整数n≥2和奇数k≥3,F是k元n方体Qnk中故障点和故障边的集合。若F中元素个数至多为2n-3,则QQnk-F是(k+1)-边泛圈的。

带有条件故障边的3元n方体的圈嵌入

研究了带有条件故障边的3元n方体的圈嵌入问题,证明了对于n≥2的3元n方体,其每个顶点至少与两条非故障边相关联.当它的故障边不超过2n-1且由这些故障边导出的子图不含圈时,该3元n方体存在不含故障边的长度在3到3n间的任意长的圈.