一种基于局部扭曲立方体的无死锁路由算法

局部扭曲立方体是一种新提出来用于并行计算的互连网络.经研究发现,局部扭曲立方体中已有最小路由算法存在着死锁.针对原有算法的特点,提出了一种新的无死锁路由算法并给出了无死锁证明.利用将物理通道分成2条虚拟通道进而形成2个不相交的虚拟网络,将不同的点对之间的路由限定在某一个虚拟网络中,从而有效地避免了死锁的产生.同时,利用一个局部扭曲立方体可由2个低维子立方体和2-扭曲立方体构成这一性质,在局部的低维子立方体和2-扭曲立方体中均采用自适应路由,从而提高了算法的自适应性.     

超立方体中基于安全矩阵的容错路由

超立方体网络拓扑结构是多处理机系统中常见的一种.随着多处理机系统规模的增大,系统出现链路与结点故障的概率也随之增大.针对超立方体结构的容错路由设计在信息传输过程中出现迂回的情况,提出了安全矩阵(safety matrices,简称SMs)这一概念,给出了一种建立SMs的方法及其容错路由算法.n维超立方体每个结点所需的存储开销为n2个字,安全矩阵记录了局部更多的信息.与传统的路由算法相比,该算法可以避免信息在传输过程中出现迂回和死锁,使路径达到最优.     

互联网络RCP(n)的拓扑结构优化设计

提出一种新的互联网络拓扑结构——基于交叉立方体环连接的Petersen图互联网络RCP(n).研究互联网络RCP(n)的通信特性.通过RCP(n)的单播路由算法、广播路由算法、可分组性算法,证明RCP(n)不仅具有环、彼特森图和交叉立方体本身所具有的性质,同时又具有自身独特的拓扑性质.研究结果表明,RCP(n)是一种具有良好拓扑结构和通信特性的互联网络.在通信效率上的花费只有由超立方体构成的互联网络的1/2,而通信效率却是由超立方体构成的互联网络的一倍.     

局部扭曲立方体单播容错路由算法

局部扭曲立方体是一种新型的网络拓扑结构．基于此网络拓扑结构,利用安全级概念以及此种网络拓扑结构自身特有的性质设计了一种单播容错路由算法．通过模拟仿真实验对该算法进行了性能评价与分析．当故障节点的数目达到或超过一半时,仍能保持在一个相当高的容错路由成功率上．另外,该算法所选线路在多数情况下是最短距离．     

HCH-立方体在比较模型下的可诊断性

新型并行处理系统的研制依赖于对新的互连网络的结构和它们的性质的研究,超立方体和交叉立方体是流行的互连网络,它们都有优点也有缺点.对由超立方体和交叉立方体构成的HCH-互连网络的可诊断性进行了研究,证明了当n≥4时,n维HCH-立方体互连网络在比较模型下的可诊断性为n,与超立方体和交叉立方体在比较模型下的可诊断性相同.     

折叠超立方体网络的t/k诊断问题

为提高系统故障诊断的诊断度,Somani 和Peleg提出了t/k诊断故障策略. n维折叠超立方体网络是具有2n个顶点,(n+1)2n-1条边的(n+1)-维正则图,它是n维超立方体网络增加2n-1补边得到的.中证明了当n≥6和1≤k≤n+1时n维超立方体网络是t/k可诊断的,其中t=(k+1)(n+1)-1/2(k+1)(k+2)+1.     

规则互连多处理器系统的容错性分析

多处理器系统中的互连网络为处理器之间相互通信提供了一种有效的机制,是决定系统性能的重要因素之一.互连网络的容错性可以用互连网络中设备出现故障时,网络保持正常工作的概率来刻画.笔者用概率方法对4种规则互连多处理器系统(超立方体,交叉立方体,M(o)bius立方体,局部扭曲立方体)的容错性进行了分析.通过仿真试验,得到结论:基于超立方体或其变体结构的多计算机系统均具有较好的容错性,其中,交叉立方体具有最好的容错性.     

基于局部信息的单播容错路由算法研究

文章提出了局部k维子交叉立方体连通性和局部子交叉立方体连通性的概念,给出交叉立方体互联网络中基于子交叉立方体结构的局部连通性容错模型.以此模型设计了局部信息的高效的单播容错路由算法(文中称之算法B),算法具有很好的通信性能和具体意义.     

超立方体网络广播容错路由算法

研究了具有大量错误结点的超立方体网络中的广播容错路由算法.假定Hn是一个局部3维子立方体连通的n维超立方体网络,并且每一个基本的3维子立方体中分别最多有1个和2个错误结点,从理论上证明了在最坏情况下基于shouting广播通信模式的广播容错路由算法分别经过最多1.5(n-1)和2(n-1)时间步,就可以将源结点的信息广播到Hn中的所有正确结点中;通过实验验证了在均匀和独立的错误结点分布情况下广播时间步的上界实际上只有n+1,支持了理论分析结果.     

折叠交叉立方体的1-好邻诊断度

诊断度是多处理器系统互连网络能够诊断的最大故障结点的个数,它是度量多处理器系统故障诊断能力的一个重要参数.2012年,Peng等提出了一种新的诊断方法g-好邻诊断度,它要求每个非故障顶点至少有g个非故障邻点.n-维折叠交叉立方体网络FCQ_n是由交叉立方体网络CQ_n增加2^n-1条边后所得.该文利用1-好邻诊断度作为评价可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到折叠交叉立方体网络的1-好邻诊断度.证明了在PMC模型与MM^*模型下FCQ_n的1-好邻诊断度分别等于2n+1,n≥5和2n+1,n≥6.     

局部纽立方体网络的容错泛圈性

n维局部纽立方体网络LTQn是超立方体网络的一种新变型。已经证明：LTQn中就包含任意长度l（4≤l≤2^n）的圈。我们改进了这个结果，证明了：只要网络故障点数fv和故障边数fe之和不超过（n-2），LTQn中就包含任意长度l（4≤l≤2^n-fv）的圈。     

扭立方体连接网络的几乎泛圈性

扭立方体连接网络是超立方体的一个变种,它是由扭立方体生成的一种新的互连网络结构·根据扭立方体连接网络的结构特点,证明了扭立方体连接网络的几乎泛圈性·这一结论说明关于线性阵列和环上的运算均可在扭立方体连接网络上实现·     

扭立方体连接网络中超立方体的同胚嵌入

扭立方体连接网络是超立方体的一个变种,它具有良好的递归结构及网络参数·根据扭立方体连接网络的性质研究了超立方体同胚嵌入到其中的问题,得到的嵌入映射是超立方体嵌入到扭立方体连接网络中扩张率、拥塞度及负载等都最小的嵌入映射     

局部扭曲立方体在一维阵列光网络中的路由与波长分配

探讨局部扭曲立方体LTQ_n通信模式在一维阵列波分复用光网络中的路由与波长分配问题.首先通过LTQ_n的最大导出子图得到拥塞,即所需要的最少波长数;其次给出一个路由与波长分配策略,从而证明了最优波长数为2~(n+1)/3.     

关于Smarandach立方部分数列 和

设n是正整数,a3(n)表示不小于n的最小立方部分,b3(n)表示不超过n的最大立方部分.用初等方法研究了数列a3(n)和b3(n)的渐近性质,给出了关于这两个数列的两个有趣的渐近公式.     

动态线性模拟电路多频故障诊断

本文给出一种非线性计算量较小的动态线性模拟电路多频故障诊断法。该方法采用多频激励建立的非线性故障诊断方程组及其雅克比矩阵,结构简单,计算机容易实现。非线性方程组的求解采用局部收敛的牛顿——拉普逊迭代法,速度较快。本文还研究了电路的可诊断性以及测试频率的选择问题。     

Rn中超平面偶与特殊凸体相交的几何概率问题

利用凸体的均质积分给出了Rn中的超平面偶与n维正方体相交时，其交集也与此正方体相交的几何概率。此概率序列不仅与正方体棱长无关，而且关于维数n单调递增，并收敛于常数π/4。这一系列结果与n维球体时的情形类似。在此基础上，利用初等对称函数以及积分几何理论进一步讨论了棱长不等的n维长方体的情形，并给出了相应的几何概率的最大值。由于此几何概率序列与长方体的棱长有关，因此不再关于维数n单调递增，也不再具有收敛性，然而，当棱长满足一定条件时依然会收敛到常数π/4。