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

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

超立方体网络容错性的概率分析

用概率分析的方法研究在给定结点错误概率的情况下超立方体网络容错性的概率，证明了一个具有1024个结点的10维超立方体网络能够容许多达10％的错误结点而具有99％的概率确保正确结点的连通性；如果结点的错误概率不超过0.1%，则所有实际规模的超立方体网络（结点数可多达1万亿个）能够具有99.9%的概率确保正确结点的连通性。研究结果表明，所提出的方法也能够用于研究其他层次结构的网络和其他网络通信问题。     

广义超立方体网络的容错路由分析

讨论了广义超立方体网络的容错路由问题。并在此基础上证明了当无效点很多时,只要存在某个（n-1）-维广立方体中无效节点不超过两个,则该n-维广义超立方体中的任意两个有效节点x和y之间的有效路由长度区间为[H（x,y）,0（x,y）＋4]。这里H（x,y）表示x到y的汉明距离,0（x,y）表示x到y的最优距离。     

用OPSBOPMs实现超立方体系统的容错路由

提出了针对超立方体结构多处理机系统的最优通路集的新概念和建立基于最优通路集的最优通路矩阵（OPSBOPMs）的新算法，并给出了基于OPSBOPMs的容错路由算法，证明了该算法是基于最优通路距阵（OPMs）和基于扩展最优通路矩阵（EOPMs）容错路由算法的扩展，研究结果表明：该算法的存储开销与OPMs的相同，但记录的最优通路的信息包含了它们所记录的最优通路的信息，使搜索最优通路的能力增强。     

Mesh网络容错单播路由算法

基于k-Mesh子网连通的概念，提出一个简单的Mesh网络容错单播路由算法．该容错单播路由算法是基于局部信息的，因为路由算法在路由的过程中，只需要知道其相邻结点的信息而无需知道其他结点出错的情况．对于给定的源结点和目的结点，当路由路径扩展到每一个k-Mesh子网中时，该子网均可独立地完成算法的操作而无需考虑算法在其他k-Mesh子网中的操作状态．所以，路由算法是高度分布式的．容错单播路由算法的时间复杂性是最优的．模拟结果表明，路由算法所构造的路由路径长度非常接近于2个结点之间的最优路径长度．     

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

超立方体网络拓扑结构是多处理机系统中常见的一种.随着多处理机系统规模的增大,系统出现链路与结点故障的概率也随之增大.针对超立方体结构的多处理机系统中存在链路故障的情况,提出了用于最优通路记录的极大安全链路矩阵(maximum safety-link matrices,MSLMs)这一概念,给出了一种建立MSLMs及其容错路由算法.通过n-1轮邻结点的信息交换,用矩阵的形式记录最优通路;与已有的容错路由算法相比,极大安全链路矩阵解决了如何用矩阵的形式来记录最多最优通路数的问题.     

扭立方体网络到交换超立方体网络嵌入问题研究

网络的可嵌入性常常被作为衡量一个网络通用性的重要指标.交换超立方体网络是近年来提出的一种超立方体网络重要变种,为了证明交换超立方体网络具有很好的通用性,体现其摸拟其它网络的能力,利用图论方法,以邻接表方式给出了扭立方体网络（TQn）到交换超立方体网络（EHu＋v＋1）的嵌入映射,分析并证明了该嵌入映射所具有的评价性能.     

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

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

一种面向2D-Mesh拓扑结构的片上网络容错路由算法设计与分析

介绍了片上网络的拓扑结构和路由算法和故障模型,提出了一种适用于NoC 2D-Mesh结构的容错性路由算法,可以根据邻居节点的状态动态的选择路由。通过仿真证明了在均匀随机流量模式下,相对于XY路由算法,使用该算法吞吐量更高,平均端到端时延更小。     

超立方体计算机上的最近点对算法

给出了在超立方体结构的计算机上求平面点集最近点对的一个算法，分析了算法的正确性和时间复杂性。     

一种并行/容错系统的任务调度算法

任务调度算法是并行容错系统的重要问题之一,针对具有并行处理与容错任务的多单片机系统提出了一种新的任务调度算法,并结合系统的实际情况进行算法仿真并对算法进行了性能分析。     

环型算法到超立方体机的Gray码嵌入

介绍了环算法到超立方体机的算法映射,实际上就是Ｇｒａｙ码嵌入。分析了现行的Ｇｒａｙ码的求法,并给出了两种简单,高效的Ｇｒａｙ码计算方法。     

超立方体计算机上的平面凸壳算法

给出了在超立方体结构的计算机上，求平面点集的凸壳的一个算法，并分析了算法的正确性和时间复杂性。     

折叠超立方体网络的自适应诊断

自适应性诊断的目的是正确辨别结点的性质,没有公共点的两对结点可以在同一个诊断周中出现.在Bjoklund[1]的基础上对超立方体网络的另一种变形——折叠超立方体网络(FHn)的自适应诊断进行了研究,对n(n≥3)维折叠超立方体FHn构造了一个递归的哈密尔顿3-并行诊断周算法,利用归纳法证明了在错误结点数不超过n的情况下FHn可以在4个并行诊断周内完成诊断,并且至多需要2n+n-1次诊断.     

全互连立方体网络的路由算法研究

一种应用于大规模并行处理系统的结点度等于常数的递归多级分层互连网络,称为全互连立方体网络(FCCN,Fully Connected Cubic Network)．FCCN具有可扩展性好、延伸性能好等优点．一个m-FCCN可以由8个(m-1)-FCCN来递归得到,FCCN网络的结点度与网络的规模大小无关,网络的直径和平均结点距离都与结点数的立方根成正比．提出了FCCN中的简单自寻路算法．并与最短路由算法进行比较研究,计算结果表明,在85％以上的情况下,自寻路算法可以得到最短距离;并证明了FCCN在信息局部性系统中具有比较高的并行处理效率．     

超立方体上0／1背包问题的并行算法

文中提出了在超立方体计算机上解０／１背包问题的并行算法。如果Ｐ表示超立方体上处理器地的数目，Ｔ是在一个处理器上解决给定问题所需要的时间，那私这一算法的时间特性为）（Ｔ／Ｐ）。     

一种高吞吐低延时NoC容错路由算法

为了提高片上网络(Network-on-Chip,NoC)系统的可靠性及故障情况下的网络性能,基于转弯模型(Turn Model)的思想对现有的XY路由算法进行了改进,提出了一种容错路径短,且在故障情况下具有信息均衡能力的无虚通道容错路由算法(TXY路由算法)。OPNET仿真结果表明,该算法与同类算法相比具有较好的吞吐及时延性能。     

一种片上网络容错路由算法

为解决片上网络的可靠性问题,以2D-Mesh拓扑结构为基础,将片上网络中的节点划分为边缘节点和内部节点两大类,并分别针对这两大类节点的各自特征有针对性地提出相对快捷的路径决策模型和转弯模型,从而帮助路由节点更为快捷地确定符合自身特征的当前任务最佳传送路径,算法大幅缩减了重复运算时间,并减少了数据计算量。通过容错偏转路由算法进行仿真实验,应用本文算法和XY路由算法、Flooding路由算法进行比较分析,实验结果证明算法可以有效的避免产生死锁和拥塞,具有很好的传输效率。     

死锁恢复的多维交换结构容错路由算法

在高性能路由器中采用多维交换结构是解决可扩展性的一种方法。在实现这种交换结构时,随着节点数目的增多,交换结构出现故障的概率也随之增加。该文在mesh/torus结构上提出了一种基于死锁恢复策略的容错路由算法MMAR。基于各非故障节点周围链路的状态,MMAR能容错任意形状的故障模型且所需虚拟通道数少。通过在凹形区域表面节点中设置该凹形区域内节点位置信息表,该算法能避免消息进入与其目的节点无关的凹形区域以使绕道路径最短。该文给出了在256个节点的二维torus中的仿真结果,验证了算法的有效性。     

一种新的通信网络动态路由算法

针对通信网络中的路由问题,提出了一种虚令牌动态路由算法,并用Ｈｏｐｆｉｅｄｌ神经网络实现该算法。该Ｈｏｐｆｉｅｌｄ神经网络,其神经元之间的连接强度固定不变,通信网络的物理逻路值和呼叫请求被反映到神经元的偏置电流中,地用硬件实现。同时,当通信网络中的业务量发生变化时,算法能够自动调整最短路径与负载均衡之间的关系,计算机仿真结果表明,该算法能接入更多的网络连接。