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

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

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

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

条件故障下3-元n-立方体的容错分析

研究了条件边故障下3-元n-立方体中较大连通分支点的数目,进而证明了3-元n-立方体是(4n-6)-条件边故障强Menger边连通的。最后通过一个反例说明该结果是最优的。

N-立方体消息通信时延的分析

本文利用生灭过程理论 ,对 N-立方体的消息通信延时建立了一个计算模型 ,在存在消息堵塞的情况下 ,对 N-立方体采用虫孔寻径机制和 e- cube算法时的消息通信延迟进行了分析求解 .最后 ,通过模拟实验 ,证明了结果的正确性 .

条件故障下k-元n-立方体的强Menger边连通度

为了更好地度量网络的容错性,运用数学归纳法和反证法,讨论了条件故障下k-元n-立方体的强Menger边连通度问题。证明了当k≥4,n≥2时,k-元n-立方体是(6n-8)-条件边故障容错强Menger边连通的;当k=3,n≥2时,3-元n-立方体是(4n-6)-条件边故障容错强Menger边连通的。最后举了一个反例证明该结论是最优的。通过对这个问题的讨论和证明,可以补充Qiao等关于超立方体(2-元n-立方体)的条件容错强Menger边连通度的结果,同时进一步改进了翟登鑫对这个问题的研究结果。

结构故障下k-元n-立方体网络的容错哈密顿圈嵌入模拟实验

该文给出了在存在结构故障的情况下,k-元n-立方体网络容错哈密顿圈嵌入的构造算法及实验结果。在这些实验中,得到了相应的数据,为互连网络多播算法的应用提供了依据。

k元n-立方体网络的死锁特征剖析

研究死锁形成几率随网络参数的变化规律 ,对于选择合适的寻径算法、改良网络设计方案都具有重要意义 .环形等多种网络都是 k元 n-立方体网络系列的拓扑同构体 .因此 ,k元 n-立方体网络死锁特征的研究结果具有一定的普遍适用性 .本文根据刻画死锁特征的死锁循环密度属性划分死锁类型 .利用死锁类型分析寻径适应性、物理通道、虚拟通道、缓冲区大小 。

一个n-立方体开口电阻计算的新方法

n-立方体的开口电阻,它由相距为n-1的二个顶点组成,对于任何正整数n,可被正确地用公式列出.

Boole函数的线性可分性(Ⅰ)——n-维超立方体的基本理论

Boole函数的线性可分性是前向人工神经网络理论中的一个比较困难的问题之一。目前仅对变量数n≤7的某些问题给予讨论。当n≥8时,尚无判别Boole函数线性可分的一般准则,更无线性可分Boole函数的计数公式。基于此,本文详细地研究了与Boole函数线性可分性有关的n-维超立方体的基本理论,包括n-维超立方体的基本性质、超立方体中的平行线、子超立方体的计数等,并给出了构造n-维超立方体图的一种新方法。

局部不连通广义超立方体中的容错路由

本文我们提出了局部m维子立方体不连通的广义n-维超立方体的概念,讨论了局部m维子立方体不连通的广义n-维超立方体的连通性,给出了基于局部m维子立方体不连通的广义n-维超立方体的路由算法,分析了时间复杂度。

神经网络、纠错码和二元n—立方体上的多项式

本文介绍几种将纠错码的概念和神经网络概念联系起来的方法。证明线性分组码中进行最大似然译码等价于某种神经网中求解能量函数的全局极大值。给定一线性码，可以构造一个神经网络，方法是使能量函数的每个局部极大值都对应于一个码字，而每个码字对应于一个局部极大值。本文还探讨了n-立方体上多项式的极大化和纠错码之间的关系，结果表明译码技术对于解决n-立方体上多项式的极大化问题可能是一种有用的工具。这些结果已被推广到非二进制和非线性码。

超立方体网络环诊断策略的研究

多处理器系统的传统故障诊断策略和条件可诊断策略已经被广泛研究,然而并未解决系统中存在的大量故障结点问题。提出一种新的策略——环诊断策略,即通过环分割方法对汉密尔顿环进行诊断,从而找出系统中存在的所有故障结点,并给出了超立方体网络的环诊断策略及一些重要性质。与此同时,提出了超立方体网络的环快速诊断算法,快速定位系统中的所有故障结点。基于以上策略,得到了在PMC模型下,n-维超立方体网络的环诊断度为(n2+n)/2,时间复杂度为O(n),其中n表示多处理器系统中处理器的个数。与超立方体网络的传统故障诊断策略和条件诊断策略相比较,本文提出的环诊断策略具有诊断度大、时间复杂度小的优点。

关于Weichsel猜想的一点注记(英文)

设P是n-立方体图Q_n的完备控制集．在1994年,Weichsel证明了存在某些整数r_1,r_2,…,r_m使P在Q+n中的诱导子图〈P〉为Q_(r1),Q_(r2),…,Q_(rm)的不交之并,并且猜想r_1=r_2=…=r_m．本文证明了当m≤20时,该猜想正确．

三维MANDELBROT渗流下临界形态

本文研究了三维andelbrot渗流下临界形态,证明了渗流函数θ(p)在pc点是不连续的,同时得到当p<pc时,三维Mandelbrot渗流A的最大连通分支是点,即A是"尘状"的.

三维MANDELBROT过程的渗流下临界状态

本文研究了三维Ｍａｎｄｅｌｂｒｏｔ过程渗流下临界形态，证明了渗流函数θ（Ｐ）在Ｐ＿ｃ点是不连续的，同时得到了当Ｐ＜Ｐ＿ｅ时，三维Ｍａｎｄｅｌｂｒｏｔ渗流Ａ的最大连通分支是点，即Ａ是“尘状”的。