并行计算网络中m-ary n-cube的拓扑性

m-ary n-cube是并行计算系统网络中的一个重要拓扑结构.文中证明了m-ary n-cube中的任意点对之间存在n(m-1)条内点不交的路.若点对之间的H amm ing距为d(d<n),则其中有d条长度为d,d(m-2)条长度为d+1,(m-1)(n-d)条长度为d+2的内点不交的路.若点对之间的H amm ing距为n,则其中存在n条长度为n,n(m-2)条长度为n+1的内点不交的路.从而说明了m-ary n-cube中宽度为n(m-1)的直径为n+1.同时利用任意图的点连通度、边连通度、最小度之间的关系证明了m-ary n-cube的点、边连通度都是n(m-1).

k-ary n-cube中的移动气泡流控策略

在k-ary n-cube网络中,气泡流控是一种有效、实用的死锁避免技术,它不必依赖虚通道就能避免环网中出现的死锁问题。如果流控策略能感知到维度内缓冲区的总体使用情况,就能够更加高效地进行调度,从而提高网络性能。为了避免关键气泡机制引起的阻塞,提出了伪报文协议;结合伪报文协议,设计了移动气泡流控策略,它有效实现了维度内的全局资源感知能力。与局部气泡流控相比,路由器每条输入通道仅设置一个报文缓冲区就可以避免环网中的死锁,即最小资源需求减少了一半。网络模拟结果表明,该机制不会出现永久阻塞;在distribute、hotregion和uniform传输模式中,该机制可以有效提高网络吞吐率20%以上,并且在网络饱和后吞吐率依然维持稳定。

K-ary N-cube网络中的维度气泡流控与无死锁完全自适应路由

利用虚跨步切换技术中消息的依存关系只与相邻缓冲区队列相关的特点,设计了一种称为维度气泡流控(DBFC)的新型流控策略.该流控策略建立在虚跨步(VCT)切换和信约流控机制之上,通过分析端口信约值和路由信息实现点点间的流控.在无边带karyncube网络中,如果采用DBFC流控策略,即使网络中存在环相关,设计的自适应维度气泡路由(ADBR)算法仍可实现无死锁的最短距离的路由.对于以上结论,文中提供了详细的证明.最后,通过修改模拟工具RSIM的网络模拟器———NETSIM的代码,实现了DBFC流控策略和ADBR算法.模拟结果显示,ADBR算法在性能上比常用的维序路由优越,在报文延迟上有近17.5%的降低.

INS_面向k-ary n-cube的互联网模拟器

目前流行的mesh、torus和hypercube等互联网均可综合成k-ary n-cube网。为分析k-ary n-cube网的性能，必须建立它的仿真模型，而传统的通用仿真工具不适合对这种互联网的模拟。本文介绍了利用事件推进法建立的互联网模拟器INS(Interconnection Network Simulator)。与其他互联网模拟器的结果比较表明，该模拟器具有较好的应用价值。

概率故障条件下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))。

5元n立方体中指定三条点不交覆盖路

k元n立方体被视为将来候选网络结构之一,它有很多优良性质和参数,被用作度量路由选择,能直接影响网络通信的稳定性和传输时效.本文研究了5元n立方体中一对三条点不交覆盖路问题,运用数学归纳法可得,当n≥2时,在Q_(n)^(5)中任意取四个顶点x,y_(1),y_(2),y_(3),则在Q_(n)^(5)中存在三条内部顶点不交的覆盖路P1=(x,…,y_(1)),P2=(x,…,y_(2)),P3=(x,…,y_(3)).

On Classification of k-Dimension Paths in n-Cube

The shortest k-dimension paths (k-paths) between vertices of n-cube are considered on the basis a bijective mapping of k-faces into words over a finite alphabet. The presentation of such paths is proposed as (n - k + 1)×n matrix of characters from the same alphabet. A classification of the paths is founded on numerical invariant as special partition. The partition consists of n parts, which correspond to columns of the matrix.

k-元n-立方体网络局部通信模式下的性能模型

大规模并行计算机互连网络的设计对并行应用程序的执行效率有重要影响,k-元n-立方体是广泛使用的拓扑结构.局部通信是并行应用的主要通信模式之一,研究局部通信模式下互连网络的性能有重要意义,已有分析模型缺乏对这方面的充分研究.引入局部通信率和局部通信区域半径组成的二元参数,刻画k-元n-立方体网络节点间通信的空间局部性.利用排队论对网络建模,研究延迟和吞吐量随负载的变化规律,比较局部性参数对网络性能的影响强度,针对长、短消息情况分别进行详细讨论.最后采用改进的网络模拟器,验证分析模型具有较高的准确性.为具有局部通信性质的大规模并行应用,提供了一种有效预测延迟和吞吐量的方法.

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

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

n-方体的点可区别全色数的渐近性态

令Qn为n-方体,图G的点可区别全色数为χvt(G),那么limn→∞vχt(Qn)n=1+q*.这里q*=0.293815…是方程(x+1)x+1=2xx的唯一的正根.

N-立方体中一类特殊差错分布的快速容错路由选择

对n-立方体结构的多处理器系统，本文考查了出故障的处理器非常集中时的容错路由对策，给出了一种判断出故障的处理器是否全部或绝大部分集中于某一（n—1）-子立方体的方法，证明了当差错非常集中时任意两个有效处理器之间可在线性时间（即o(n)时间）内找到最光或接近最优路由的有效路由．

k元n方体的可靠性评估

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

k-ary n立方体中的测地泛圈

文中用归纳假设法证明了结论:当n≥2,k≥3,u和v是Qkn中任意2个顶点,由对称性,不妨设u=(0,0,…,0),v=(d1,d2,…,dn),这里0≤di≤k/2,(i=1,…,n),记d=d1+d2+…+dn≤1,N=kn,则对于每个偶数l适合2d+2≤l≤N,则Qkn中有过u和v长为l的圈C,且C上u和v的距离为d.若有i和j满足1≤i≤j≤n,使得di≥1且dj≥1,或有且dj=k/2且dj=0,j≠i,1≤j≤n,则又有l=2d;当n≥2,k≥3是奇数,u和v是Qkn中任意2个顶点,由对称性,不妨设u=(0,0,…,0),v=(d1,d2,…,dn),这里0≤di≤k/2,,(i=1,…,n),记d=d1+d2+…+dn≥1,N=kn,r=max{di},则对于每个奇数l适合2d+k-2r≤l≤N,则Qkn中有过u和v长为l的圈C,且C上u和v的距离为d.

单向k-元n-立方体网络

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

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

基于k元n立方体拓扑的无线传感器网络广播策略

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

n维“格子笼”图的Hamilton问题

对n维"格子笼"图的Hamilton性进行了研究,得到了判定n维"格子笼"图是Hamilton图的一个非常简洁的充分必要条件.