几类新的笛卡尔乘积互连网络

Star网络、Pancake网络、Bubble sort网络、修正Bubble sort网络(又称圈图)、轮图等都既是Cayley图又是重要的互连网络。利用图的笛卡尔乘积方法构建了几类新的笛卡尔乘积互连网络:环网、循环移数网络、ILLIAC网络、超立方体分别与Star网络、Pancake网络、Bubble sort网络、修正Bubble sort网络、轮图的笛卡尔乘积网络;这些网络的某些性能指标(例如,直径等)比Star网络或超立方体更好。     

关于煎饼网络及层次环煎饼网络的几个猜想

煎饼网络是由互连网络的群论模型设计出来的一类典型的超级计算机互连网络。关于煎饼网络师海忠提出了一个猜想-猜想1,但煎饼网络有一个弱点即结点度随着规模的增大而迅速增大,为了改进这一缺点师海忠提出了互连网络的层次环群论模型。在这篇文章中,首先,汪生龙给出了煎饼网络当n=5时的两种圈分解,其次师海忠提出了关于该网络的一个猜想-猜想2,当Cayley图层次环网络中的Cayley图取煎饼网络时得到煎饼层次环网络的猜想-猜想2/,进而汪生龙证明了猜想2/在低维度情形下是正确的     

关于修正冒泡排序网络的一簇猜想

修正冒泡排序网络是互连网络设计中的一个重要的Cayley图模型,关于修正冒泡排序网络的一簇猜想如下:对于任意的自然数n≥3,修正冒泡排序网络Yn是i个边不交的哈密尔顿圈以及n-2i个完美对集的并,其中1≤i≤︱n/2︱。证明了当i=1,2时,这个猜想是正确的。     

互连网络的m层二进制图模型

超立方体、交叉立方体、Mbius立方体以及折叠立方体等都是著名的互连网络。它们有一个共同的弱点:其结点度随着网络规模(结点数)的增大而增大。这意味着依此互连网络设计出的超级计算机的扩展性很差。能否构建出既能保持它们已有特性又能使结点度固定的互连网络呢？现提出互连网络的m层二进制图模型,并依此模型设计了分别由超立方体、交叉立方体、Mbius立方体以及折叠立方体等生成的m层超立方体、m层交叉立方体、m层Mbius立方体以及m层折叠立方体。特别地,m层超立方体有一个特点:结点度可以不随网络规模的增大而增大,而且具有超立方体的特性。另外,还提出了由已知图生成m层图的概念。     

洗牌交换置换网络SEP的一种新的路由算法

1引言与sEP网络的定义 众所周知,Cayley图和Cayley陪集图在计算机互连网络的设计与分析中起着重要的作用[1～3].例如:熟知的环(ring)网络,圆环面(torus)网络,超圆环面(super-torus)网络[7],星图(star graph)网络,超立方体网络(hypercube),立方体连接圈(cubeconnected cycles)网络[2]均可看作是Cayley图.而de Bruijn网络与洗牌交换网络[8]可作为Cayley陪集图的例子.     

关于冒泡排序连通圈网络猜想的一个注记

冒泡排序连通圈网络BSCC(n)是一类重要的互连网络,它是3正则的.2010年师海忠提出了如下猜想:冒泡排序连通圈BSCC(n)(n≥4)可分解为边不交的一个Hamilton圈和一个完美对集的并.在本文中证明了当nn==5,4时猜想成立,另外,给出了BSCC(6)的一个圈分解.     

2r-正则图连通圈网络的Hamilton分解

互连网络是超级计算机的重要组成部分。互连网络通常模型化为一个图,图的顶点代表处理机,图的边代表通信链路。2010年师海忠提出互连网络的正则图连通圈网络模型,设计出了多种互连网络,也提出了一系列猜想。文中证明了2r -正则图连通圈网络可分解为边不交的一个Hamilton圈和一个完美对集的并,从而证明了当原图为2r-正则连通图时,这一系列猜想成立。     

BC互连网络及其性质

提出一种称为一一对应连接（BC）图的互连网络族，使其包含超立方体、交叉立方体和Mobius立方体作为基具子集，同时又使其具有与超立方体、交叉立立体和Mobius立方体相同的对数级的直径和顶点度数、最高连通（容错）度和相同的可诊断性等性质，从而使对超立方体及与其结构相似的大量互连网络的某些性质的研究合而为一，证明了BC互连网络族中包含一类Hamilton连通图并给出了BC互连网族中的图的直径的一个猜想。     

互连网络的新模型:多部群论模型

互连网络是超级计算机的重要组成部分.互连网络在很大程度上决定着超级计算机的性能.在1989年,S.B.Akers等提出了互连网络的群论模型,据此模型设计出了星网络、冒泡排序网络等一大批网络.尤其是星网络具有很多很好的性能,被认为是超立方体的替代品.但它们都有一个弱点:网络规模(结点数)为n!.即随着n的增大,n!增速太快,使得据此网络结构设计出的超级计算机升级较为困难,即扩展性较差.在群论模型的基础上提出了互连网络的多部群论模型,进而,据此模型设计出(n,k)-多部星网络、(n,k)-多部冒泡排序网络等多种网络.并证明星网络是(n,1)-多部星网络,而且(n,k)-多部星网络做到了规模(结点数)增大且增幅固定、直径增大缓慢、结点度不变,即有很好的可扩展性,其它(n,k)-多部网络也有类似的性能.     

一类数据中心网络中顶点独立生成树的一种通用构造方法

数据中心网络设计的新趋势是在互连网络的顶点和边上分别部署交换机和双端口服务器,其逻辑图可以抽象为复合图.顶点独立生成树(node-independent spanning trees,NIST)是数据中心网络中的一种重要结构,可用于设计数据中心网络中的可靠通信协议,容错广播和安全消息分发,IP快速重路由等.给定一个复合图G(Kn),首先表明,如果图G的直径为d,则复合图G(Kn)的直径为2d或2d+1.假设n-正则、n-顶点连通的互连网络G中存在以任一顶点为根的n棵NIST,通过提出一种时间复杂度O(N)的高效算法(其中N是顶点数),给出了G(Kn)中一种构造n棵NIST的通用方法.对复合图Qn(Kn)的顶点分析表明,NIST的最大高度仅为其直径加3.另外,基于增广立方体的数据中心网络上的模拟实验也从另一个方面证明了上述结论的正确性.     

A comparative study of job allocation and migration in the pancake network

Pancake networks are an attractive class of Cayley graphs functioning as a viable interconnection scheme for large multi-processor systems. The hierarchy of the pancake graph allows the assignment of its special subgraphs, which have the same topological features as the original graph, to a sequence of incoming jobs. We investigate the hierarchical structure of the pancake network and derive a job allocation scheme for assigning processors to incoming jobs. An algorithm is presented for job migration. Finally, we compare the assignment scheme to those derived previously for the star network and address the shortcomings of the pancake network.     

Macro-star networks: efficient low-degree alternatives to stargraphs

We propose a new class of interconnection networks, called macro-star networks, which belong to the class of Cayley graphs and use the star graph as a basic building module. A macro-star network can have node degree that is considerably smaller than that of a star graph of the same size, and diameter that is sublogarithmic and asymptotically within a factor of 1.25 from a universal lower bound (given its node degree). We show that algorithms developed for star graphs can be emulated on suitably constructed macro-stars with asymptotically optimal slowdown. This enables us to obtain through emulation a variety of efficient algorithms for the macro-star network, thus proving its versatility. Basic communication tasks, such as the multimode broadcast and the total exchange, can be executed in macro-star networks in asymptotically optimal time under both the single-port and the all-port communication models. Moreover, no interconnection network with similar node degree can perform these communication tasks in time that is better by more than a constant factor than that required in a macro-star network. We show that macro-star networks can embed trees, meshes, hypercubes, as well as star, bubble-sort, and complete transposition graphs with constant dilation. We introduce several variants of the macro-star network that provide more flexibility in scaling up the number of nodes. We also discuss implementation issues and compare the new topology with the star graph and other popular topologies     

Cyclic-cubes: a new family of interconnection networks of evenfixed-degrees

We introduce a new family of interconnection networks that are Cayley graphs with fixed degrees of any even number greater than or equal to four. We call the proposed graphs cyclic-cubes because contracting some cycles in such a graph results in a generalized hypercube. These Cayley graphs have optimal fault tolerance and logarithmic diameters. For comparable number of nodes, a cyclic-cube can have a diameter smaller than previously known fixed-degree networks. The proposed graphs can adopt an optimum routing algorithm known for one of its subfamilies of Cayley graphs. We also show that a graph in the new family has a Hamiltonian cycle and, hence, there is an embedding of a ring. Embedding of meshes and hypercubes are also discussed     

若干多级互连网络的扩展Cayley图模型

使用群论中的半直积作为工具,将已有的若干构建互连网络的方法统一成一种Cayley图模型CSC（q,p,l,k）,使其具有更好的可扩展性。并证明了CSC（q,p,l,k）网络包括了若干重要的互连网络作为它的特殊情形,例如立方连通圈、星连通圈和最近提出并受到关注的k度Cayley图。提出该模型的意义在于为计算机系统的设计者们提供只需要选择合适的参数就可以确定自己需要的互连网络模型。其次,该模型也在一定程度上避免一些在互连网络构建方面的冗余研究工作。     

One-to-Many Embeddings of Hypercubes into Cayley Graphs Generated by Reversals

Among Cayley graphs on the symmetric group, some that have a noticeably low diameter relative to the degree of regularity are examples such as the ``star' network and the ``pancake' network, the latter a representative of a variety of Cayley graphs generated by reversals. These diameter and degree conditions make these graphs potential candidates for parallel computation networks. Thus it is natural to investigate how well they can simulate other standard parallel networks, in particular hypercubes. For this purpose, constructions have previously been given for low dilation embeddings of hypercubes into star networks. Developing this theme further, in this paper we construct especially low dilation maps (e.g., with dilation 1, 2, 3, or 4) of hypercubes into pancake networks and related Cayley graphs generated by reversals. Whereas obtaining such results by the use of ``traditional' graph embeddings (i.e., one-to-one or many-to-one embeddings) is sometimes difficult or impossible, we achieve many of these results by using a nontraditional simulation technique known as a ``one-to-many' graph embedding. That is, in such embeddings we allow each vertex in the guest (i.e., domain) graph to be associated with some nonempty subset of the vertex set of the host (i.e., range) graph, these subsets satisfying certain distance and connection requirements which make the simulation possible. Received July 30, 1997, and in revised form July 18, 2001. Online publication October 30, 2001.     

Structural properties of Cayley digraphs with applications to mesh and pruned torus interconnection networks

Despite numerous interconnection schemes proposed for distributed multicomputing, systematic studies of classes of interprocessor networks, that offer speed-cost tradeoffs over a wide range, have been few and far in between. A notable exception is the study of Cayley graphs that model a wide array of symmetric networks of theoretical and practical interest. Properties established for all, or for certain subclasses of, Cayley graphs are extremely useful in view of their wide applicability. In this paper, we obtain a number of new relationships between Cayley (di)graphs and their subgraphs and coset graphs with respect to subgroups, focusing in particular on homomorphism between them and on relating their internode distances and diameters. We discuss applications of these results to well-known and useful interconnection networks such as hexagonal and honeycomb meshes as well as certain classes of pruned tori.     

Optimal information dissemination in star and pancake networks

This paper presents a new decomposition technique for hierarchical Cayley graphs. This technique yields a very easy implementation of the divide and conquer paradigm for some problems on very complex architectures as the star graph or the pancake. As applications, we introduce algorithms for broadcasting and prefix-like operations that improve the best known bounds for these problems. We also give the first nontrivial optimal gossiping algorithms for these networks. In star-graphs and pancakes with N=n! processors, our algorithms take less than [log N]+1.5n steps     

A new family of interconnection networks of fixed degree three

A new family of interconnection networks WGn is proposed, that is constant degree 3 Cayley graph, and is isomorphic to a Cayley graph of the wreath product Z2 Sn when the generator set is chosen properly. Its different algebraic properties is investigated and a routing algorithm is given with the diameter upper bounded by 3n2 - 6n 4. The embedding properties and the fault tolerance are devired. In conclusion, we present a comparison of some familiar networks with constant degree 3.     

The Hyperstar Interconnection Network

In this paper, a multiprocessor interconnection topology, the hyperstar, based on the Cartesian product of star graphs is studied. The basic properties of the hyperstar are discussed and proved. This includes reduced degree and diameter, hierarchical structure, vertex symmetry, optimal routing, and shortest path characterization. The hyperstar is shown to be a member of the Cayley class of symmetric graphs. Embeddings of hypercubes, star graphs, and meshes are discussed. An optimal one-to-all broadcasting algorithm is obtained and analyzed. Some results on fault tolerance, parallel paths, Hamiltonian cycles, and VLSI layouts are obtained. Furthermore, a comparative study between the hyperstar and seven related networks is conducted. The comparison is based on scalability, broadcasting cost, link requirements, cost/performance ratio, and other static parameters such as degree, diameter, and average diameter.     

An accurate mathematical performance model of adaptive routing in the star graph

Analytical modelling is indeed the most cost-effective method to evaluate the performance of a system. Several analytical models have been proposed in the literature for different interconnection network systems. This paper proposes an accurate analytical model to predict message latency in wormhole-switched star graphs with fully adaptive routing. Although the focus of this research is on the star graph but the approach used for modelling can be, however, used for modelling some other regular and irregular interconnection networks. The results obtained from simulation experiments confirm that the proposed model exhibits a good accuracy for various network sizes and under different operating conditions.