扭立方体连接网络结构的研究与分析

根据交叉立方体（CQn）的结构与关联对的概念,对扭立方体连接网络（TNn）的结构特性进行了分析,证明了当[n5]时,TNn是不连通的,并且不连通的结点数占整个网络结点数的一半。通过分析扭立方体连接网络的错误所在,提出了一种新型网络结构——扭交叉立方体（TCQn）,证明了该网络结构是完全连通的,初步研究了其基本网络性质,如正则性,连通度,容错度,递归性等,表明TCQn具有与CQn同样优秀的网络性质。     

HFCN：一种层次型全连接网

本文以全连接网为基本模块设计了一种适用于局部通信频率较高的网络，在分析了该网的拓扑特性之后，我们构造了一个点对点寻径算法，最后，我们把这种网和超立方体作了详细的比较。     

HCH-立方体的Hamilton连通性

新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究。超立方体及其变型——交叉立方体具有优点,也具有缺点。文献[1]给出了在超立方体与交叉立方体的顶点之间的一种连接——超连接,从而得到了一种称为HCH-立方体的互连网络,文章证明了当n≥4,HCH-立方体任意两个顶点之间存在Hamilton路径,即HCH-立方体是Hamilton连通的,而超立方体不是Hamilton连通的。这表明HCH-立方体具备了交叉立方体在Hamilton连通性方面的性质。文章还给出了在n维HCH-立方体中构造任意两个顶点之间Hamilton路径的算法,该算法的时间复杂度为O(N),其中N=2n,为n维HCH-立方体的顶点个数。     

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

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

Covert Channel Secure Hypercube Message Communication

The hypercube multiprocessor is a popular architecture in parallel computing environments. Recently, computer security and privacy issues have gained significance. This paper considers the security issues of a network of processors connected over a hypercube topology. We demonstrate that a covert channel can be established by exploiting the underlying message communication mechanism of the hypercube, even when the access-control denies such communication. This can occur because node-to-node communication in a hypercube may require multiple hops and two or more disjoint message communications may actually be transmitted along common links. Congestion (and the resulting delay) in such shared links can provide the basis for a covert channel. We introduce security considerations for a multiprocessor by focussing on the covert channel issue in hypercube message communication. A security model for the hypercube routing function is presented. Based on noninterference, we develop sufficient conditions for the routing mechanism to be free of covert channels. Two secure hypercube message routing approaches are proposed for store-and-forward communication strategy. The first approach (Virtual Channel) achieves security by fixed bandwidth partitioning of links, for which the price is paid in delay performance. The second approach (Bypass) prioritizes lower security class messages, for which delay of higher class messages is sacrificed. Performance (i.e., cost of security) of these two approaches are shown using simulation. Finally, a time-out feature is introduced to the Bypass approach, which disallows potential starvation of higher class messages at the expense of limited bandwidth covert channel. Maximum covert channel bandwidth (in terms of the time-out parameter) is analyzed.     

Cross-cube在PMC诊断模型下的可诊断性

可诊断性度是衡量一个互连网络可靠性的重要指标。Cross-cube是超立方体的一种重要变型,与超立方体相比有许多好的性质。PMC模型是并行计算系统中的一种经典的诊断模型,在该模型下有两个著名的诊断策略：精确策略和悲观策略。证明了n维Cross-cube在精确策略下的可诊断性度是[n+1(n≥4)],在悲观策略下的可诊断性度是[2n-2(n≥4)]。证明了Cross-cube在精确策略下的可诊断性度大于超立方体的可诊断性度,在悲观策略下的可诊断性度与超立方体的可诊断性度相同。     

Fault-tolerant routing methodology for hypercube and cube-connected cycles interconnection networks

This paper presents a fault-tolerant routing methodology for both injured hypercube and cube-connected cycles interconnection topologies. The proposed routing methodology efficiently tolerates any pattern of faulty regions with any number of faulty nodes in the network which is based on the best-first search and backtracking strategy. Deadlock freedom of the proposed routing methodology is obtained by only one virtual channel per physical channel. In order to evaluate the proposed routing methodology, a 7-dimensional hypercube network is simulated in various conditions, i.e., different traffic rates, different number of faulty nodes and different message lengths. Simulation results confirm that the proposed routing methodology in comparison with the previous methods provides acceptable performance while it significantly increases the reliability of the network. It also guarantees delivery of messages between any pair of source and destination while the network is connected.     

A distributed virtual hypercube algorithm for maintaining scalable and dynamic network overlays

Network overlays support the execution of distributed applications, hiding lower level protocols and the physical topology. This work presents DiVHA: a distributed virtual hypercube algorithm that allows the construction and maintenance of a self‐healing overlay network based on a virtual hypercube. DiVHA keeps logarithmic properties even when the number of nodes is not a power of two, presenting a scalable alternative to connect distributed resources. DiVHA assumes a dynamic fault situation, in which nodes fail and recover continuously, leaving and joining the system. The algorithm is formally specified, and the latency for detecting changes and the subsequent reconstruction of the topology is proved to be bounded. An actual overlay network based on DiVHA called HyperBone was implemented and deployed in the PlanetLab. HyperBone offers services such as monitoring and routing, allowing the execution Grid applications across the Internet. HyperBone also includes a procedure for detecting groups of stable nodes, which allowed the execution of parallel applications on a virtual hypercube built on top of PlanetLab. Copyright © 2014 John Wiley & Sons, Ltd.     

Distributed computing on oriented anonymous hypercubes with faulty components

We give efficient algorithms for distributed computation on oriented, anonymous, asynchronous hypercubes with possible faulty components (i.e. processors and links) and deterministic processors. Initially, the processors know only the size of the network and that they are inter-connected in a hypercube topology. Faults may occur only before the start of the computation (and that despite this the hypercube remains a connected network). However, the processors do not know where these faults are located. As a measure of complexity we use the total number of bits transmitted during the execution of the algorithm and we concentrate on giving algorithms that will minimize this number of bits. The main result of this paper is an algorithm for computing Boolean functions on anonymous hypercubes with bit cost , where is the number of faulty components (i.e. links plus processors), is the number of links which are either faulty, or non-faulty but adjacent to faulty processors, and is the diameter of the hypercube with faulty components. Received: October 1992 / Accepted: April 2001     

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

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

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

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

基于比较模型的交换超立方网络的(t,k)诊断度研究

故障诊断问题已经被广泛讨论,许多互连网络的诊断度已被深入研究。(t,k)-诊断为最重要的系统级故障诊断策略之一,在故障节点不大于t的前提条件下,每次迭代均可以识别最少故障节点个数为k。针对如何提高交换超立方网络的诊断度的问题,进行了一个基于比较模型的(t,k)-诊断算法研究,根据连通图的特性对交换超立方网络进行连通分子的划分,并计算交换超立方连通图中连接边与节点间的量化关系,从而证明了交换超立方网络是(t,k)-可诊断的。最终表明,本算法下的诊断度,优于其传统精确诊断s 1。     

超级局部扭立方体互连网络及其性质

局部扭立方体是近年来提出的超立方体的一个变型,由于它的许多优越性质(如低直径),在并行处理领域越来越受到人们的重视.然而,像超立方体一样,它也有一个缺点,即要使局部扭立方体升级,就必须成倍地增加其顶点个数.为了解决这一问题,文中将顶点个数为2的次幂的局部扭立方体推广到具有任意个顶点的互连网络,提出了超级局部扭立方体(SLTC)的定义,并证明它保持了局部扭立方体的最高连通度、对数级的直径和顶点度数、Hamilton性质等方面的优良性质,从而证明了超级局部扭立方体是既保持了局部扭立方体的多种优越性质又易于升级的互连网络.     

“Optimal” Hopfield network for combinatorialoptimization with linear cost function

An "optimal" Hopfield network is presented for combinatorial optimization problems with linear cost function. It is proved that a vertex of the network state hypercube is asymptotically stable if and only if it is an optimal solution to the problem. That is, one can always obtain an optimal solution whenever the network converges to a vertex. In this sense, this network can be called the "optimal" Hopfield network. It is also shown through simulations of assignment problems that this network obtains optimal or nearly optimal solutions more frequently than other familiar Hopfield networks.     

交换超立方网中的最短路径路由算法

针对交换超立方网络的最短路由问题,提出一个交换超立方网中的最短路径路由算法.利用图论的方法,通过引进子网的概念,研究交换超立方网的拓扑性质,给出节点各边可进行最短路径路由的充要条件,得到其时间复杂度为O(s+t)2).理论分析和仿真结果表明,该算法可输出交换超立方网中任意两节点间的一条最短路径.     

The scalability of FFT on parallel computers

The authors present the scalability analysis of a parallel fast Fourier transform (FFT) algorithm on mesh and hypercube connected multicomputers using the isoefficiency metric. The isoefficiency function of an algorithm architecture combination is defined as the rate at which the problem size should grow with the number of processors to maintain a fixed efficiency. It is shown that it is more cost-effective to implement the FFT algorithm on a hypercube rather than a mesh despite the fact that large scale meshes are cheaper to construct than large hypercubes. Although the scope of this work is limited to the Cooley-Tukey FFT algorithm on a few classes of architectures, the methodology can be used to study the performance of various FFT algorithms on a variety of architectures such as SIMD hypercube and mesh architectures and shared memory architecture     

Adaptive routing in wormhole-switched necklace-cubes: Analytical modelling and performance comparison

The necklace hypercube has recently been introduced as an attractive alternative to the well-known hypercube. Previous research on this network topology has mainly focused on topological properties, VLSI and algorithmic aspects of this network. Several analytical models have been proposed in the literature for different interconnection networks, as the most cost-effective tools to evaluate the performance merits of such systems. This paper proposes an analytical performance model to predict message latency in wormhole-switched necklace hypercube interconnection networks with fully adaptive routing. The analysis focuses on a fully adaptive routing algorithm which has been shown to be the most effective for necklace hypercube networks. The results obtained from simulation experiments confirm that the proposed model exhibits a good accuracy under different operating conditions.     

超级Mbius立方体──一类最优容错的小直径互连网络

文中将具有２ｎ个顶点的Ｍｏｂｉｕｓ立方体的拓扑结构加以改变,得到了包含任意个顶点的互连网络——超级Ｍｏｂｉｕｓ立方体,并证明它保持了Ｍｏｂｉｕｓ立方体的高连通度、对数级的直径和顶点度数等优良性质,并且当顶点个数Ｎ＝２ｎ＋２ｎ－１时,０－型超级Ｍｏｂｉｕｓ立方体是一个（ｎ＋１）－正则图;更进一步地,由于它包含任意个顶点,所以其升级只需增加任意个顶点,从而克服了Ｍｏｂｉｕｓ立方体的升级必须成倍增加其顶点个数的缺点．     

Finding cycles in hierarchical hypercube networks

The hierarchical hypercube network, which was proposed as an alternative to the hypercube, is suitable for building a large-scale multiprocessor system. A bipartite graph G=(V,E) is bipancyclic if it contains cycles of all even lengths ranging from 4 to |V|. In this paper, we show that the hierarchical hypercube network is bipancyclic.     

在超立方体上并行仿真BP神经网

本文研究在超立方体上并行仿真ＢＰ神经网的方法，报告我们在Ｉｎｔｅｌ ｉＰＣＳ／８６０超立方上开发的一个ＢＰ神经仿真器。文章着重讨论如何把ＢＰ神经网均衡地分配到超立方体的结点以及如何在超立方体上并行实现ＢＰ算法等问题。