交换超立方网络的嵌入问题研究

交换超立方网络作为超立方网络的一个变种,具有良好的递归性和理想的网络参数。根据交换超立方网络的相关性质研究了E-2DMesh网络和超立方网络的嵌入问题,并得出如下结论:(1)当max(s,t)<7时,不存在dilation=1的EM(2m,2n)到EH(s,t)的嵌入映射(m+n≤s+t+1)。(2)EM(2s,2t)可以expansion=2,dilation=4,load=1嵌入EH(s,t)。(3)当min(s,t)>1时,不存在dilation=1的Qn到EH(s,t)的嵌入映射(n=s+t)。(4)Qn可以ex-pansion=2,dilation=3,congestion=1,load=1嵌入EH(s,t)(n=s+t)。上述结论进一步说明了交换超立方网络具有良好的扩容性。

超立方网络上的平行路径

超立方是分布存储系中最常用的结构．在以往的工作中，人们已经提出了不少容错寻径算法．然而，还没有考虑Ｈｎ中｜Ｆ｜２ｎ－２的情形．在一个含有故障结点集Ｆ的ｎ维超立方网络Ｈｎ中，｜Ｆ｜４ｎ－２４，（ｓ０，ｄ０），（ｓ１，ｄ１）是其中任意两对非故障结点，如果，（１）对于ｖ∈Ｖ（Ｈｎ），有｜Ａ（ｖ，Ｈｎ－Ｆ）｜６．（２）沿着某一维ｋ（０ｋｎ－１），可将Ｈｎ分割成两部分：（ｄ０∈）Ｈｎ－１，０和（ｄ１∈）Ｈｎ－１，１，且｜Ｆ∩Ｈｎ－１，ｉ｜２ｎ－１２（ｉ＝０，１），则一定存在两条互不相交的路径Ｐ（ｓｉ，ｄｉ），使得｜Ｐ（ｓｉ，ｄｉ）｜Ｈ（ｓｉ，ｄｉ）＋１２（ｉ＝０，１）．并且，这两条路径可以并行地求得．我们给出了相应的容错寻径算法，其时间复杂性为ｔ＝Ｏ（ｎ·｜Ｆ｜）．

广义超立方网络的容错寻径算法研究

给定一个广义超立方网络以Ｇ（ｍ，ｒ）：Ｎ＝ｍｒ（ｍ≥２，ｒ≥１），其上有若干条连线发生故障，Ｆ为其故障连线集合，且 Ｇ（ｍ，ｒ）－Ｆ是连通的，Ｓ和 Ｄ是 Ｇ（ｍ，ｒ）中任意两个结点（处理器），其汉明距离 Ｈ（Ｓ， Ｄ）＝ｈ．得出如下结论：（１）当｜ｆ｜＜ｄ时，存在一条非故障路径Ｐ（Ｓ，Ｄ），且｜Ｐ（Ｓ，Ｄ）｜≤ｈ＋２； （２）当ｄ≤｜Ｆ｜＜ｍ（ｄ－ｍ＋１）时，存在一条非故障路径Ｐ（Ｓ，Ｄ），且｜Ｐ（Ｓ，Ｄ）｜≤ ｈ＋４ｍ－２．这里，ｄ是Ｇ（ｍ，ｒ）的度，｜Ｐ（Ｓ，Ｄ）｜ 是路径Ｐ（Ｓ，Ｄ）的长度，Ｐ（Ｓ，Ｄ）是非故障的是指在其上的所有连线均非故障．给出了寻径算法．

加总线超立方网络上的容错寻径算法

研究了加总线超立方网络的容错寻径问题．设 ＢＨｎ为一个已加总线的ｎ维超立方网络， Ｆ为其故障结点集合，｜Ｆ｜≤ｎ．研究了ＢＨｎ上任意两个非故障结点间的容错寻径问题．对于小规模的超立方网络，其直径由ｎ＋２降为３，而对于较大规模的超立方网络而言，其直径降到≤（ｎ／３）＋６．显然，当ｎ＞６时，ｎ＋２＞（ｎ／３）＋６．因此，加总线后的超立方网络同时具有更好的容错性能．

基于比较诊断模型的超立方网络诊断算法

一个有效的诊断算法对多处理器系统而言极其重要。在多处理器系统中,识别所有故障节点的能力称为诊断系统的诊断度。在比较模型下,诊断的执行是通过一个比较器处理器,给与之相邻的一对处理器发送相同的输入信号,并比较两者间的响应状态。为了提高超立方网络的诊断度,提出了一种新型的基于比较模型的超立方故障诊断算法,其利用超立方网络节点连接的特性生成一个拓扑图ES(k;n),最终得出一个3位二进制的诊断症候集,从而确定系统故障节点。该算法的诊断度最优能达到4n,大于传统超立方的诊断度n。

分层超立方网络的可靠性评估

针对目前关于分层超立方网络的可靠性研究不够系统,严重制约了其应用和推广的问题,以分层超立方网络为研究对象,在得到分层超立方网络相关拓扑性质的基础上,通过理论推导得到了n维分层超立方(HHC_(n))在PMC模型和MM*模型下的h-额外条件诊断度和t/s-诊断度。此外,设计了HHCn在PMC模型和MM*模型下的t/s-诊断算法,并分析了其时间复杂度。研究结果表明,HHCn的h-额外条件诊断度是其传统诊断度的约h+1倍,t/s-诊断度是其传统诊断度约s+1倍。该结果进一步完善了分层超立方网络的可靠性指标,为其应用和推广提供了重要的理论依据。

不完全超立方网络上加总线的方法

本文给出在不完全超立方网络上加总线的方法．加总线后的网络既保存了可扩充性强的优点，又使其直径从n减小到．同时，给出了加总线不完全超立方网络上任意两结点间的寻径算法．对于具有偶数多个结点的不完全超立方网络．给出了加总线后其上任意两结点间的两条平行路径的寻径算法．这样，如果将所要传送的信息复制成两份，分别沿这两条路径传送，则允许有一条路径上有结点或连线发生故障，从而提高了其容错能力．

超立方体网络中路由生成算法的子立方分裂方法

超立方网络拓扑是并行计算中最重要的多处理机互连结构之一,目前对它的研究热点主要集中在当超立方的网络互连结构中具有失效结点时,如何快速计算其上点到点的并行路由.本文提出利用子立方来分解整个空间,使得原来的超立方网络互连结构可以非常规整地分解成若干个子立方,因而若以子立方为路由目的,可以显著简化路由表,从而降低并行计算中的寻路开销.进一步,这种技术应用在具有局部失效结点的超立方网络时,同样能够压缩路由表,避免从整体上计算点到点的最佳路由,将这种计算分布在超立方中的多数正常结点独立完成.这种寻路方式为高度对称的网络互连拓扑中路由的生成提供了新的思路.

一种基于超立方体网络的高效故障诊断并行算法

超立方网络是一种重要的网络拓扑结构。针对现有的超立方网络故障诊断算法复杂度高的问题,引入故障扇的概念,采用并行深度优先搜索策略设计算法,通过算法寻找超立方体网络中的故障扇,确定该网络的故障节点,以便替换或修复,为增强网络的可靠性提供了一条重要的新途径。最后对所提算法的复杂性进行了分析,证明了该算法的时间复杂度不超过O(N),远优于现有复杂度超过平方级的算法。

具有大量错误结点的超立方体网络中的高效路由算法的设计与讨论

该文提出了容错超立方体网络的一个很自然的新概念 :局部连通性 ;讨论了两种类型的局部连通性 :局部k-维子立方体连通性和局部子立方体连通性 .一个局部连通的超立方体网络可容许大量错误结点且能确保超立方体网络是全局连通的 ;给出了满足局部连通性条件的超立方体网络中的几个高效的容错路由算法 .文中的容错路由算法是分布式的和基于局部信息的 。

基于Hamming距离的超立方体网络的寻径算法

本文利用Ｈａｍｍｉｎｇ距离概念，提出两种基于Ｈａｍｍｉｎｇ距离的确定性寻径算法—Ｅ１－ｃｕｂｅｒｏｕｔｉｎｇ和Ｅ２－ｃｕｂｅｒｏｕｔｉｎｇ，分析这两种算法的特点．为了克服确定性寻径算法易出现通道拥挤现象，本文综合上述两种算法，提出一种自适应寻径算法—Ｅ３－ｃｕｂｅｒｏｕｔｉｎｇ．

故障超立方体网络中的高效容错路由算法研究

对超立方体网络中具有大量节点和链路故障模式进行了研究,提出了两类“子连通性”:即k-维子连通性和任意子连通性的概念;基于两类子连通性概念,分别给出了两个满足该两类子连通性条件的超立方体网络的分布式容错路由算法。证明了已有的两类局部连通性概念中的条件“错误节点数小于正确节点数”是不必要的。提出的两个子连通性概念是两类局部连通性概念的最大扩展,可以在更大程度上保证整个超立方体网络的全局连通性,是已有的两类局部连通性概念的一种完全扩展。

具有大量错误结点的超立方体网络中并行路由算法

本文讨论具有大量错误结点的超立方体网络中的并行路由算法。假定 Hn 是一个局部 k-维子立方体连通的 n-维超立方体网络 ,本文提出的并行路由算法能够找出至少 K=min( Dk( u) ,Dk( v) )条并行路径 ,其中每一条路径的长度不超过 ( d H( Uk,Vk) + 3) 2 k。该算法的时间复杂度为 O( Kn2 k)。这里 ,Dk( u)和 Dk( v)分别代表源结点 u和目的结点 v的正确的邻结点个数 (不考虑 u和 v所在的 k-维子立方体内部的邻结点 ) ,d H( Uk,Vk)代表源结点 u和目的结点 v所在的两个 k-维子立方体 Uk和 Vk之间的海明距离。本文还考察了 k=3的特殊情况 ,在 k=3并且有分别不超过 1 2 .5和 2 5的错误结点的情况下 ,该算法的时间复杂度为 O( Kn) ,并且每一条路径的路径长度分别在大约 1 .5和 2倍源结点和目的结点之间的海明距离之内。该算法只要求结点知道其邻结点的状态 ,而无需知道整个网络信息 ,也就是说 ,该算法是基于局部信息的 。

具有混合故障的超立方体网络中的高效路由

针对容错超立方体网络中的同时具有大量节点和链路故障模式,提出了两类“局部弱连通性”:即k-维局部弱连通性和任意局部弱连通性的概念;并在基于局部弱连通性的基础上,给出了两个满足局部弱连通性条件的超立方体网络的分布式容错路由算法。同时证明了新提出的两个局部弱连通性概念分别是原有的两个局部连通性概念的扩展。

交换超立方体网络的网络嵌入研究

本文主要研究超立方网和星型网嵌入交换超立方体网络的问题。首先,利用图形嵌入的方法,设计了超立方网到交换超立方体网络的嵌入映射,分析并证明了该嵌入映射所具有的评价性能。其次,给出了星型网到交换超立方体网络两种嵌入策略,也就是所谓的优化嵌入映射和奇偶嵌入映射,进而给出了具有更小的扩张率的星型网到另一种交换超立方体网络的嵌入方法。

关于广义超立方体网络的容错性和通信延迟

直径是度量并行计算系统网络的容错性和信息延迟的重要参数 .广义超立方体网络Q(m1,m2 ,… ,mn)是并行计算系统网络中的一个重要拓扑结构 .令k=m1+m2 +… +mn-n .论文证明 :Q(m1,m2 ,… ,mn)的k直径等于n+ 1 .

超立方体网络并行容错路由算法

研究了具有大量错误结点的超立方体网络中的并行容错路由算法 .其步骤是 :首先 ,通过实验分析基于局部k维子立方体连通性容错模型中并行容错路由算法的容错性和效率 ,然后分析k =3且有多达 2 5 .0 %的错误结点时并行容错路由算法的容错性和效率 .研究结果表明 :并行路由算法所能找到的并行路径的数目最多可达到min(D(u) ,D(v) ) ,至少可达到min(Dk(u) ,Dk(v) ) ;如果只考虑k比较小 (如 3 ,4,5等 )而n比较大 (如 1 0 ,1 5 ,2 0等 )的情况 ,则min(D(u) ,D(v) )与min(Dk(u) ,Dk(v) )非常接近 ,说明并行路由算法所能找到的尽可能多的并行路径的能力是接近最优的 ;并行容错路由算法容错性强 。

故障超立方体网络中的路由算法

针对超立方体结构的多处理机系统中存在故障的情况,提出了一个应用于超立方体网络的容错路由算法。该容错路由算法是基于局部信息的,只需要知道邻节点的状态,而无需知道整个网络的运行情况。对于给定的源节点和目的节点,路由算法均能够找到一条最优通路,并且可以预防死锁。模拟实验结果表明,路由算法所构造的路径长度接近于两个节点之间的最优路径长度。

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

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

交换超立方体网络容错路由研究

为了研究交换超立方体网络容错路由问题,引入了相邻结点集合类的概念,提出了相邻结点集的求解公式。对于满足任意子连通性条件的交换超立方体网络,给出了基于相邻结点集合类的自适应容错路由算法及算法的步长上界。仿真实验结果表明算法是有效的。