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.     

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     

A family of interconnection networks for nonuniform traffic

New networks, called GLO networks, are constructed by adding bus-like links to omega networks, providing additional capacity between cells on momentarily busy paths. Equivalent pin-count GLO and omega networks offered uniform and nonuniform traffic were simulated. GLO networks exhibited lower latency for nonuniform traffic and light to moderate uniform traffic     

Comments on “A new family of Cayley graph interconnectionnetworks of constant degree four”

For original paper see Vadapalli and Srimani, ibid., vol. 7, no. 1, p 26-32, 1996, where the authors have proposed a new family of Cayley graph interconnection networks of constant degree four. Our comments show that their proposed graph is not new but is the same as the wrap-around butterfly graph. The structural kinship of the proposed graph with the de Bruijn graph is also discussed     

Strategies for interconnection networks: Some methods from graph theory

Interconnection networks require dense graphs in the sense that many nodes with relatively few links may be connected with relatively short paths. Some recent constructions of such dense graphs with a given maximal degree Δ and diameter D (known as (Δ, D) graphs) are reviewed here. The paper also contains an updated table of the best known (Δ, D) graphs.     

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.     

A new approach to model virtual channels in interconnection networks

Dealing with virtual channels has always been a critical issue in developing analytical performance models for interconnection networks. Almost all previous studies relied on a method proposed by Dally to capture the effect of virtual channels multiplexing in the performance of interconnection networks. This paper presents a new method to model the effect of virtual channel multiplexing in high-speed wormhole-switched interconnection networks. Dally's method loses its accuracy as the traffic load increases due to blocking nature of wormhole-switched networks. Our new method is based on a finite capacity queue, M/G/1/V and comparing to Dally's method achieves a higher degree of accuracy under low, moderate and high traffic loads. Furthermore, its simplicity eases its employment under different network conditions and setup. The presented model is validated by means of an event driven simulator and a detailed comparison with Dally's method is presented.     

A new approach to improve reliability of the multistage interconnection networks

Because of their cost-effectiveness, multistage interconnection networks are widely used in parallel multiprocessor systems to make a connection among the processors and memory modules. One of the most important requirements for these communication systems is reliability. Adding a number of stages to these networks is one of the main approaches to promote this issue. Despite its modest cost and ease of implementation, this approach improves the reliability only to a small extent, which is not desirable, especially for large-scale systems. In this paper, we propose a new approach to improve reliability of the networks, called reducing nodes. Extensive reliability analyses from two major perspectives, terminal and broadcast, demonstrate that this idea can achieve a tremendous advantage over the aforementioned approach.     

An introduction to the multistage cube family of interconnection networks

The interconnection network in large-scale parallel/distributed supercomputer systems is a crucial component. Three networks are overviewed here. Multistage cube networks represent an important family of networks, which includes the omega, n-cube, multistage shuffle-exchange, delta, baseline, SW-banyan, and Generalized Cube. This family has been used or proposed for use in such systems as staran, pasm, Ultracomputer, the BBN Butterfly, the IBM RP3, and data-flow machines. The multistage cube topology, distributed routing control, and ability to be partitioned into independent subnetworks are examined. The Extra Stage Cube (ESC), a single-fault-tolerant multistage cube network, is described. The structure, control, and partitionability of the ESC, and how it functions when multiple faults occur, are presented. The Dynamic Redundancy (DR) network, a fault-tolerant multistage cube network that supports the incorporation of spare processors for fault tolerance, is discussed. Its structure, control, and partitionability into single-fault-tolerant subnetworks are explained.This research was supported by the Air Force Office of Scientific Research under grant F49620-86-K-0006, the Rome Air Development Center under grant F30602-83-K-0119, and the Purdue Research Foundation David Ross Grant 1985/86 no. 0857.currently with the Supercomputing Research Center, 4380 Forbes Blvd., Lanham, MD 20706 (as of June 1, 1987).currently with Computer Science Department, University of Illinois, Urbana-Champaign, IL 61801.     

A new performance measure for characterizing fault rings in interconnection networks

One of the fundamental issues in parallel computers is how to efficiently perform routing in a faulty network where each component fails with some probability. Adaptive fault-tolerant routing algorithms in such systems have been frequently suggested as a means of providing continuous operations in the presence of one or more failures by allowing the graceful system degradation. Many algorithms involve adding buffer space and complex control logic to the routing nodes. However, the addition of extra logic circuits and buffer space makes nodes more liable to failure and less reliable. Further, if the shape of fault pattern is confined, then many non-faulty nodes will be sacrificed and hence their resources are wasted. This is clearly an undesirable solution and motivates solutions that provoke efficient use of non-faulty nodes. One such approach to reducing the number of functional nodes that must be marked as faulty is based on the concept of fault rings to support more flexible routing around rectangular fault regions. Before such schemes can be successfully incorporated in networks, it is necessary to have a clear understanding of the factors that affect their performance potential. In this paper, we propose the first general solution for computing the probability of message facing the fault rings with and without overlapping in the well-known torus networks. We also conduct extensive simulation experiments using various fault patterns, the results of which are used to confirm the good accuracy of the proposed analytical models.     

Isomorphism of degree four Cayley graph and wrapped butterfly andtheir optimal permutation routing algorithm

In this paper, we first show that the degree four Cayley graph proposed in a paper appearing in the January 1996 issue of IEEE Transactions on Parallel and Distributed Systems is indeed isomorphic to the wrapped butterfly. The isomorphism was first reported by Muga and Wei in the proceedings of PDPTA '96. The isomorphism is shown by using an edge-preserving bijective mapping. Due to the isomorphism, algorithms for the degree four Cayley graph can be easily developed in terms of wrapped butterfly and topological properties of one network can be easily derived in terms of the other. Next, we present the first optimal oblivious one-to-one permutation routing scheme for these networks in terms of the wrapped butterfly. Our algorithm runs in time O(√N), where N is the network size     

Biswapped networks: a family of interconnection architectures with advantages over swapped or OTIS networks

We propose a new family of communication architectures called ‘biswapped networks’. Given any n-node basis network Ω, the associated biswapped network Bsw(Ω) is built of 2n copies of Ω, using a simple rule for connectivity that ensures desirable attributes, including regularity, modularity, fault tolerance, and algorithmic efficiency. In particular, if Ω is a Cayley digraph, then so is Bsw(Ω). Our biswapped connectivity provides a systematic scheme for synthesizing large, scalable, modular, and robust parallel architectures. Furthermore, many desirable attributes of the underlying basis network Ω are preserved, as the Bsw(Ω) parameters are related to the corresponding parameters of Ω. We obtain a number of results on internode distances, Hamiltonian cycles, optimal routing, and node-disjoint paths for Bsw(Ω). We explore the relations between biswapped and swapped or optical transpose interconnection system (OTIS) networks, which may use a mix of electronic and optical links. In particular, we demonstrate that the biswapped connectivity removes an inherent asymmetry of swapped/OTIS networks, as well as the attendant complications in analyses and applications. Finally, we show that biswapped networks are complementary to, and offer advantages over, well-known and widely used interconnection architectures for parallel processing.     

A new family of interconnection and damping assignment passivity‐based controllers

The by‐now standard formulation of interconnection and damping assignment passivity‐based control (for input‐affine systems) proposes the solution of a partial differential equation (PDE) that defines the assignable energy functions and computes the control using the input matrix pseudo‐inverse. However, in its original formulation—a more general design procedure was proposed, which was essentially abandoned because of the difficulties in solving the PDE. In this note, a new family of interconnection and damping assignment passivity‐based controls is proposed by extending this method in the following directions: (i) It allows the desired interconnection and damping matrices to depend on the control signal, giving the possibility to shape the PDE to ensure its solvability; (ii) the PDE directly generates the control signal that have, in general, simpler expressions; and (iii) it is applicable for general nonlinear systems possibly not affine in the control. The technique is illustrated with three examples, including the well‐known boost power converter for which it yields a simple, high‐performance controller. Copyright © 2016 John Wiley & Sons, Ltd.     

一种高阶混合互连网络拓扑结构

随着对高性能计算机性能需求的不断提升,高性能计算机的系统规模在逐渐扩大,系统内的互连网络已经成为影响性能的关键因素。如何基于高阶路由器构建更大规模、更低网络延迟以及成本、更高网络吞吐率的互连网络,是目前的主要研究方向。针对目前广泛应用的高阶网络进行特性分析,并对其中的环网以及树网进行综合,提出了一种新型层次化混合互连网络拓扑结构。该结构具有良好的可扩展性以及通信能力,并在网络模拟器NetSim上对其性能进行了仿真和分析。     

TM: a new and simple topology for interconnection networks

The selection of a topology is essential to the performance of interconnection networks, so designing a new, cost-effective topology is very significant. 2D mesh is one of the most popular topologies. However, the diameter and average distance of a 2D mesh are large enough to greatly influence the performance of the network. This paper presents a novel topology called TM, which combines the advantages of both a 2D torus and a 2D mesh. For an n×n network, the total number of links in a TM is the same as that in a mesh, while the diameter of a TM is extremely close to that of a torus. Besides, the average distance of a TM is at the middle of that of a torus and that of a mesh. To prevent deadlocks in TMs, a virtual network partitioning scheme is adopted into the TM network. Moreover, both of the deterministic and fully-adaptive routing techniques in TMs are proposed in this paper. Compared to mesh, the TM network provides average distance and diameter reduction, which contributes to the performance enhancement. Sufficient simulation results are presented to show the effectiveness of the TM network, and the new routing schemes proposed for it, by comparing with the mesh network. Compared to the torus, which requires at least 3 virtual channels to support fully-adaptive routing, the TM network can support fully-adaptive routing with only 2 virtual channels. Seen from the experimental results, in most cases, the performance of TM is worse than the torus, while in some cases, the performance of TM is comparable to torus or even better than the torus.     

Analysis of multiple-bus interconnection networks

The performance of multiple-bus interconnection networks for multiprocessor systems is analyzed, taking into account conflict arising from memory and bus interference. A discrete stochastic model of bandwidth is presented for systems in which each memory is connected either to all the buses or to a subset of the available buses. The effects of the assumptions made concerning independence among requests for different memories (spatial independence) and resubmission of blocked requests (temporal independence) are investigated systematically. The basic bandwidth model is extended to account for spatial dependence, and compared to previously proposed models. Finally, the various analytic models are shown to be in close agreement with simulation results.     

关于互连网络的几个猜想

n-立方体是著名的互连网络,星图、煎饼图和冒泡排序图是由凯莱图模型设计出来的重要的互连网络。对换树（transposition tree）的凯莱图是一类特殊的凯莱图,星图和冒泡排序图分别是对换树为星和路的凯莱图。给出了关于n-立方体、星图、煎饼图、冒泡排序图和对换树的凯莱图的各一个猜想;提出了对换图的凯莱图的概念,进而由这一概念设计出了两个互连网络——圈图和轮图,并证明冒泡排序图和星图分别可嵌入圈图和轮图。     

Topology optimization of interconnection networks

This paper describes an automatic optimization tool that searches a family of network topologies to select the topology that best achieves a specified set of design goals while satisfying specified packaging constraints. Our tool uses a model of signaling technology that relates bandwidth, cost and distance of links. This model captures the distance-dependent bandwidth of modern high-speed electrical links and the cost differential between electrical and optical links. Using our optimization tool, we explore the design space of hybrid Clos-torus (C-T) networks. For a representative set of packaging constraints we determine the optimal hybrid C-T topology to minimize cost and the optimal C-T topology to minimize latency for various packet lengths. We then use the tool to measure the sensitivity of the optimal topology to several important packaging constraints such as pin count and critical distance.