超立方体多处理机系统中基于扩展安全向量的容错路由

针对超立方体结构的多处理机系统中存在链路故障的情况,修改了吴杰提出的安全向量的概念,提出了扩展安全向量的概念,并给出了一个基于扩展安全向量的容错路由算法,与基于安全向量的路由算法相比,基于扩展安全向量的路由算法搜索最优通路的能力有了非常大的提高,即使故障数较多时,它仍能保证把绝大多数源、目的节点间有最优通路和消息沿最优通路传递。超立方体结构中各节点扩展安全向量的赋值可以通过ｎ－１轮邻接点的信息交换     

Hypercube中LIP长度的上下界估计

给出了超立方体网络中LIP容错模型的上下界估计及一个非常有意义的猜想,并且结合已有结果对上下界及猜想进行了验证。验证结果表明,对LIP的上下界估计,当n较小时还是比较好的;此外,猜想当n=2,3,4,5,6,7时均严格成立,具有非常好的理论价值和实际意义,有待进一步证明。     

用最优通路矩阵实现超立方体多处理机系统的容错路由

针对拓扑结构为超立方体的多处理机系统提出了最优通路矩阵（ＯＰＭ）的概念,并约出了一个基于最优通路矩阵的路由算法。存储于超产方体各节点中的最优通路矩阵记录系统中的故障信息,用于判定消息的源节点和目的节点之间是否存在最优通路（长度等于两节点间Ｈａｍｍｉｎｇ距离的通路）。对于ｎ维超方立体,每个节点所需的存储开销为ｎ＾２个字,基于最优通路矩阵的路由算法所选的通路的长度不超过两点间的Ｈａｍｍｉｎｇ距离加２。     

超立方体多处理机系统中基于扩展最优通路矩阵的容错路由

该文在高峰等文章的基础上，提出了针对超立方体结构多处理机系统的扩展最优通路矩阵（Extended Optimal Path Matrices,EOPMs）的概念，并给出了一个建立EIPMs的算法和基于EOPMs的容错路由算法，证明了基于EOPMs的容错路由算法是基于扩展安全向量（ESVs）^[13]和基于最优通路矩阵（OPMs)^[14]容错路由算法的扩展，与原文相比，该算法的存储开销与OPMs,相同，但记录的最优通路的信息，包含了原文所记录的最优通路的信息，使搜索最优通路的能力比它们有进一步的提高。     

超立方体网络的3路结构连通度及子结构连通度

针对以超立方体网络为蓝本的多处理机系统的可靠性和容错能力的精准度量问题，结合多处理机系统遭受计算机病毒攻击时常常发生结构性故障的特点，研究了n维超立方体网络的结构连通性和子结构连通性评价问题。首先，使用构造n维超立方体网络的3路结构割的方法得到其3路结构连通度的一个上界；然后，使用构造n维超立方体网络的3路子结构集的等价变换或约简变换的方法，得到其3路结构子连通度的一个下界；最后，利用任意网络的3路结构连通度不小于3路子结构连通度的性质，证实了超立方体网络的3路结构连通度和子结构连通度均为该超立方体网络维数的一半。这一结果表明，在3路结构故障模型下，破坏敌方以超立方体网络为底层拓扑的多处理系统至少需要攻击该系统中维数一半的3路结构或子结构。     

超立方体系统中基于安全通路向量的容错路由

n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能.随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对系统中存在链路故障的情况,提出了用于记录最优通路的安全通路向量(safety path vectors,简称SPVs)概念,并给出了建立SPVs及其容错路由算法.其中SPVs的赋值可以通过n-1轮邻节点之间的信息交换来完成,且算法中各节点的存储开销仅为n bits,因此,SPVs是安全向量(SVs)与扩展安全向量(ESVs)的一种扩展,具有比SVs和ESVs更好的记录最优通路的能力.另外，与基于最优通路矩阵(optimal path matrices,简称OPMs)及扩展最优通路矩阵(extended optimal path matrices,简称EOPMs)的容错路由算法相比,SPVs呈指数级地降低了算法的存储开销，且能够记录OPMs和EOPMs所不能记录到的最优通路信息.理论分析和仿真实验验证了SPVs的上述性能.     

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

n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能,随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对超立方体结构的多处理机系统中存在链路故障的情况,提出了用于最优通路记录的极大安全通路矩阵(maximum safety path matrices,简称MSPMs)这一概念,给出了一种建立MSPMs及其容错路由算法.证明了MSPMs通过n-1轮邻节点之间的信息交换,能以矩阵的形式记录最多的最优通路     

局部子立方体连通的超立方体网络容错路由算法和概率分析研究

In this paper, first we analyze and give opinions of fault tolerant routing and probabilistic analysis. Then,on the basis of locally subcube-connected hypercube networks, we put forward some ideas to develop efficient fault tolerant routing algorithms and powerful probabilistic analysis techniques to study fault tolerant models and the corre-sponding routing algorithms, which is of great importance to the research of parallel computer interconnection net-works.     

基于LIP和RSC的超立方体网络单播容错路由算法*

基于LIP和RSC的概念,提出了一个有效的超立方体网络单播容错路由算法.该算法不仅能容纳指数级的错误节点,而且算法效率也很高.     

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

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

超立方体并行计算机的一个新型故障诊断算法

提出了超立方体并行计算机的一个新型系统级故障诊断算法.与现有诊断算法相比,该算法能够在系统中存在较多故障处理器的情况下,正确定位全部故障处理器（代价是至多误诊断三个无故障处理器）.另外,该算法的时间复杂度与最好的现有算法相当.     

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

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

An Efficient Algorithm for Perfect Load Balancing on Hypercube Multiprocessors

This paper proposes a simple yet efficient algorithm to distribute loads evenly on multiprocessor computers with hypercube interconnection networks. This algorithm was developed based upon the well-known dimension exchange method. However, the error accumulation suffered by other algorithms based on the dimension exchange method is avoided by exploiting the notion of regular distributions, which are commonly deployed for data distributions in parallel programming. This algorithm achieves a perfect load balance over P processors with an error of 1 and the worst-case time complexity of O(M log₂ P), where M is the maximum number of tasks initially assigned to each processor. Furthermore, perfect load balance is achieved over subcubes as well—once a hypercube is balanced, if the cube is decomposed into two subcubes by the lowest bit of node addresses, then the difference between the numbers of the total tasks of these subcubes is at most 1.     

超立方体网络连通性的概率分析

超立方体网络是大型多处理器并行计算机系统中极为重要的拓扑结构.本文使用概率分析的方法研究了在给定结点错误概率的情况下,具有子连通性的超立方体网络容错模型的连通性。理论分析和试验结果表明:在具有大量分布结点错误情况下,超立方体网络是子连通的概率非常高。     

局部k-子立方连通的超立方网络中的广播容错算法

基于局部k-子立方体连通性的概念,提出了在局部k-子立方连通的超立方体中的,“播路由算法该算法是分布的、基于局部信息的,在容错性上有了很大的提高,能在线性时间内构造超立方体H1中接近最优的路径。     

On Embedding of a Hypercube in a Completely Overlapping Network

In this paper a new theoretical network called Completely Overlapping Network or CON is introduced. We show that a d-dimensional hypercube network can be embedded into this new network. Taking advantage of faster and more powerful processors and a large gap between communication and computation speeds, we also show that the embedded d-dimensional hypercube can be scaled using latency hiding. Related mathematical properties are also shown for optimal scaling.     

在超立方互联网络中实现anycast通信模式的算法分析

Anycast是网络中一种新的通信方式，是IPv6的一个新特性．它要求数据包被路由到具有相同Anycast地址的一组网络节点中距离用户“最近”的一个节点．通过对anycast这一新型通信模式研究发现，Anycast通信的应用空间非常广阔，不仅可以满足大量地理位置分散的用户的需要，而且在互联网络中也有重要的应用．因此，anycast被引入到互联网络中，提出在超立方互联网络结构中实现anycast通信的有效算法，并对该算法的效率进行分析，结果表明该算法需O（3n-2k＋2）个时间步即可实现anycast通信．通过模拟实验，得到在某一超立方互联网络中实现anycast通信时链路缓冲区个数与丢包率间的关系，为网络设计提供理论指导；同时，通过对比实验结果得到，在超立方互联网络中引入anycast通信能够有效地提高网络性能．     

On approximating the longest path in a graph

We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ratio of an approximation algorithm for this problem, we present both positive and negative results. First, a simple greedy algorithm is shown to find long paths in dense graphs. We then consider the problem of finding paths in graphs that are guaranteed to have extremely long paths. We devise an algorithm that finds paths of a logarithmic length in Hamiltonian graphs. This algorithm works for a much larger class of graphs (weakly Hamiltonian), where the result is the best possible. Since the hard case appears to be that of sparse graphs, we also consider sparse random graphs. Here we show that a relatively long path can be obtained, thereby partially answering an open problem of Broderet al. To explain the difficulty of obtaining better approximations, we also prove hardness results. We show that, for any ε<1, the problem of finding a path of lengthn-n ^ε in ann-vertex Hamiltonian graph isNP-hard. We then show that no polynomial-time algorithm can find a constant factor approximation to the longest-path problem unlessP=NP. We conjecture that the result can be strengthened to say that, for some constant δ>0, finding an approximation of ration ^δ is alsoNP-hard. As evidence toward this conjecture, we show that if any polynomial-time algorithm can approximate the longest path to a ratio of , for any ε>0, thenNP has a quasi-polynomial deterministic time simulation. The hardness results apply even to the special case where the input consists of bounded degree graphs. D. Karger was supported by an NSF Graduate Fellowship, NSF Grant CCR-9010517, and grants from the Mitsubishi Corporation and OTL. R. Motwani was supported by an Alfred P. Sloan Research Fellowship, an IBM Faculty Development Award, grants from Mitsubishi and OTL, NSF Grant CCR-9010517, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, the Schlumberger Foundation, the Shell Foundation, and the Xerox Corporation, G. D. S. Ramkumar was supported by a grant from the Toshiba Corporation. Communicated by M. X. Goemans.     

An efficient parallel algorithm for the longest path problem in meshes

The longest path problem is the problem of finding a simple path with the maximum number of vertices in a given graph, and so far it has been solved polynomially only for a few classes of graphs. This problem generalizes the well-known Hamiltonian path problem, hence it is NP-hard in general graphs. In this paper, first we give a sequential linear-time algorithm for the longest path problem in meshes. Then based on this algorithm, we present a constant-time parallel algorithm for the problem, which can be run on every parallel machine.