具有不连通子立方体的超立方体中广播路由

基于扩展的局部k—维子立方体连通的超立方体网络Hn,提出了超立方体网络Hn中新的广播容错路由算法。算法分析表明,基于扩展局部k—维子立方体连通的广播路由算法比基于局部k-子立方连通的广播路由算法提高了超立方体网络的容错性和通用性。     

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

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

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

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

具有大量错误结点的超立方体网络中的单播路由算法的设计与分析

本文讨论具有大量错误结点的超立方体网络中的单播路由算法，假定Hn是一个局部3－维子立方体连通的n-维超立方体网络并且每一个基本的3－维子立方体中分别最多有1个和2个错误结点，本文提出的单播路由算法能够在线性时间找到路径长度分别为源结点和目的结点之间大约1．5倍和2倍海明距离的次优路径，我们提出的单播路由算法只需要结点知道其邻结点的状态，而无需知道整个网络信息，也就是说，该算法是基于局部信息的，因而该算法具有很强的实际意义。     

具有混合故障广义超立方体中的容错路由

针对广义超立方体网络中的同时具有大量结点和链路故障模式,提出了两类新的局部连通性概念。在这两类局部连通性概念的基础上给出了两个广义超立方体网络的分布式容错路由算法。基于两类新的局部连通性概念的广义超立方体网络容错路由算法与基于局部连通性的广义超立方体网络容错路由容错路由算法相比较,新算法提高了容错能力。     

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

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

超立方体网络下的自适应容错路由研究*

针对超立方体结构的多处理机系统出现故障的问题,对容错超立方体网络的局部连通性进行了研究。根据局部连通性的特点定义了相邻节点集合类的概念,提出并证明了求解两类相邻节点集合的公式。给出了满足任意子连通性条件的超立方体网络的自适应容错路由算法。该算法是分布式和基于局部信息的,可以预防死锁。仿真实验的结果表明算法是高效的,且构建的路径长度接近于最优路径长度。     

基于局部扭曲立方体的多播路由算法

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

基于超立方体容错路由算法分析*

基于超立方体的优良的拓扑性质,提出了一个应用于超立方体网络的容错路由算法.该容错路由算法是基于局部信息的,因为路由算法在路由过程中,只需要知道其邻节点的信息,而无须知道其他节点的出错情况.对于给定的源节点和目的节点,路由算法均能够找到一条最优容错路径,并且可以预防死锁.模拟实验结果表明,路由算法所构造的路由路径长度接近于两个节点之间的最优路径长度.     

交叉立方体网络上的一种双向搜索路由算法

交叉立方体是近年提出的一种互联网络。虽然直径大约是超立方体直径的一半,但由于节点连接方式比超立方体复杂,所以在交叉立方体中利用节点编码研究路由算法比在超立方体中复杂的多。针对交叉立方体互联网络节点编码的特点,在理论分析的基础上采用双向搜索的方法,给出了一个基于交叉立方体节点编码的多项式路由算法,证明了在交叉立方体上采用该算法求得的任意两节点间的路长不超过该交叉立方体的直径。     

LHL-立方体互连网络及其性质

并行计算系统一直是计算机科学中的重要研究领域,其互连网络的拓扑性质对整个网络的性能起着非常重要的作用.目前已经提出多种互连网络,其中超立方体具有对数级的直径、高连通度、对称性等很好的性质,故被用作多种并行机的处理器连接的拓扑结构.然而,超立方体并非所有性质都是最优的互连网络,且超立方体的许多变型结构具有许多比超立方体更好的性质,其中已经证明了局部扭立方体在直径、Hamilton连通性等方面都优于超立方体.给出在超立方体与局部扭立方体的顶点间的一种连接方式--超连接,从而得到一种称为LHL-立方体的新型网络,并对这种网络的以下性质进行了研究:顶点连通度、边连通度、Hamilton连通性、直径.研究结果表明,一个n维LHL-立方体是一个具有2n个顶点和n2n-1条边的n-正则图,n维LHL-立方体的顶点连通度和边连通度均为n,且是Hamilton连通的,直径上界为[n/2 ]+3.     

Time and work optimal simulation of basic reconfigurable meshes on hypercubes

This paper presents a constant slow-down, optimal and locally normal simulation for basic reconfigurable meshes on hypercubes, if the log-time delay model for broadcasting is assumed. Such a simulation algorithm is based on: (i) an $\text{O}\text{(}\text{log}\text{B)}$ time algorithm for the segmented scan problem on a (2n−1)-node toroidal X-tree, where B is the size of the longest segment; this algorithm is time optimal; (ii) a constant slow-down optimal and locally normal simulation algorithm for basic reconfigurable meshes on the mesh of toroidal X-trees; and (iii) a constant slow-down optimal simulation of locally normal algorithms for meshes of toroidal X-trees on the hypercube.     

Computing biconnected components on a hypercube

We describe two hypercube algorithms to find the biconnected components of a dense connected undirected graph. One is a modified version of the Tarjan-Vishkin algorithm and the other is an adaptation of Read's sequential algorithm. The two hypercube algorithms were experimentally evaluated on an NCUBE/7 MIMD hypercube computer. The two algorithms have comparable performance, and efficiencies as high as 0.7 were observed on dense graphs.This research was supported in part by the National Science Foundation under grants DCR84-20935 and MIP 86-17374.     

On the Communication Structures of Hyper-Ring and Hypercube Multicomputers

The well-known torus an its variants,which we call hyper-rings,as well as hypercube architectures are further studied and evaluated as interconnecion networks for multicomputers,Comparisons are made among hyper-rings and between hyper-ring and hypercube networks under different communication patterns.It is concluded that although it is believed that a hypercube is generally superior to hyper-rings in performance,this is not always the case,paricu larly for locally constrained applications,where communications occur mostly among neighboring nodes.     

Modeling the performance of hypercubes: A case study using the particle-in-cell application

We have mapped onto the iPSC hypercube a particle-in-cell (PIC) algorithm that executes a plasma simulation. PIC simulates the movement of charged particles under the influence of an electrostatic field. This application provides a simple example of the problems associated with load balancing on distributed memory architectures. We present several alternative solutions to mappings of the algorithm onto the hypercube. One solution's performance is modeled and benchmarked with data from an implementation on the iPSC. The model is used to predict performance for larger size problems and a state-of-the-art hypercube architecture. We also introduce the use of provably optimal global communication algorithms that are needed for the PIC implementation on the hypercube.     

A fast pessimistic diagnosis algorithm for generalized hypercube multicomputer systems

The reliability of processors is an important issue for designing a massively parallel processing system for which fault-tolerant computing is crucial. In order to achieve high system reliability and availability, a faulty processor (node) when found should be replaced by a fault-free processor. Within a multiprocessor system, the technique of identifying faulty nodes by constructing tests on the nodes and interpreting the test outcomes is known as system-level diagnosis. The topological structure of a multicomputer system can be modeled by a graph of which the vertices and edges correspond to nodes and links of the system, respectively. This work presents a system-level diagnosis algorithm for a generalized hypercube which is an attractive variance of a hypercube. The proposed algorithm is based on the PMC model and can isolate all faulty nodes to within a set which contains at most one fault-free node. If the total number of nodes to be diagnosed in a generalized hypercube is N, the proposed algorithm can run in O(Nlog?N) time, and being superior to Yang??s algorithm proposed in 2004, it can diagnose not only a hypercube but also a generalized hypercube.     

A parallel hypercube algorithm for discrete resource allocation problems

It has been suggested that parallel processing helps in the solution of difficult discrete optimization problems, in particular, those problems that exhibit combinatorial search and require large-scale computations. By using a number of processors that are connected, coordinated and operating simultaneously, the solutions to such problems can be obtained much more quickly. The purpose of this paper is to propose an efficient parallel hypercube algorithm for the discrete resource allocation problem (DRAP). A sequential divide-and-conquer algorithm is first proposed. The algorithm is then modified for a parallel hypercube machine by exploiting its inherent parallelism. To allocate N units of discrete resources to n agents using a d-dimensional hypercube of p=2/sup d/ nodes, this parallel algorithm solves the DRAP in O((n/p+log/sub 2/p)N/sup 2/) time. A simulation study is conducted on a 32-node nCUBE/2 hypercube computer to present the experimental results. The speedup factor of the parallel hypercube algorithm is found to be more significant when the number of agents in the DRAP is much greater than the number of processing nodes on the hypercube. Some issues related to load balancing, routing, scalability, and mappings of the parallel hypercube algorithm are also discussed.