The Hamiltonicity of swapped (OTIS) networks built of Hamiltonian component networks

A two-level swapped (also known as optical transpose interconnect system, or OTIS) network with n² nodes is built of n copies of an n-node basis network constituting its clusters. A simple rule for intercluster connectivity (node j in cluster i connected to node i in cluster j for all i≠j) leads to regularity, modularity, packageability, fault tolerance, and algorithmic efficiency of the resulting networks. We prove that a swapped network is Hamiltonian if its basis network is Hamiltonian. This general closure property for Hamiltonicity under swap or OTIS composition replaces a number of proofs in the literature for specific basis networks and obviates the need for proving Hamiltonicity for many other basis networks of potential practical interest.     

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.     

Swapped (OTIS) Networks Built of Connected Basis Networks Are Maximally Fault Tolerant

An optical transpose interconnection system (OTIS) network with n^2 nodes is a two-level swapped architecture built of n copies of an n-node basis network that constitute its clusters. A simple rule for intercluster connectivity (node j in cluster i connected to node i in cluster j) leads to regularity, modularity, packageability, fault tolerance, and algorithmic efficiency of the resulting networks. We prove that an OTIS (swapped) network with a connected basis network possesses maximal fault tolerance, regardless of whether its basis network is maximally fault tolerant. We also show how the corresponding maximal number of node-disjoint paths between two nodes of a swapped network can be algorithmically constructed in a manner that is independent of the existence and construction of node-disjoint paths within its basis network. Our results are stronger than previously published results and they replace a number of proofs and constructions in the literature for specific basis networks. Additionally, we use our parallel path constructions to establish that the fault diameter and wide diameter of an OTIS network is no more than 4 units greater than its diameter.     

Swapped interconnection networks: Topological,performance, and robustness attributes

Interconnection architectures range from complete networks, that have a diameter of $D=1$ but are impractical except when the number $n$ of nodes is small, to low-cost, minimally connected ring networks whose diameter $D=\lfloor n/2\rfloor$ is unacceptable for large $n$. In this paper, our focus is on swapped interconnection networks that allow systematic construction of large, scalable, modular, and robust parallel architectures, while maintaining many desirable attributes of the underlying basis network comprising its clusters. A two-level swapped network with $n^2$ nodes is built of $n$ copies of an $n$-node basis network using a simple rule for intercluster connectivity (node $j$ in cluster $i$ connected to node $i$ in cluster $j$) that ensures its regularity, modularity, packageability, fault tolerance, and algorithmic efficiency. We show how key parameters of a swapped interconnection network are related to the corresponding parameters of its basis network and discuss implications of these results to synthesizing large networks with desirable topological, performance, and robustness attributes. In particular, we prove that a swapped network is Hamiltonian (respectively, Hamiltonian-connected) if its basis network is Hamiltonian (Hamiltonian-connected). These general results supersede a number of published results for specific basis networks and obviate the need for proving Hamiltonicity or Hamiltonian connectivity for many other basis networks of practical interest.     

Load-balancing on swapped or OTIS networks

Existing local iterative algorithms for load-balancing are ill-suited to many large-scale interconnection networks. The main reasons are complicated Laplace spectrum computations and flow scheduling strategies. Many large-scale networks are modular and/or hierarchically structured, a prime example being the class of swapped or OTIS networks that have received much attention in recent years. We propose a new local scheme, called DED-X, for load-balancing on homogeneous and heterogeneous swapped/OTIS networks. Our scheme needs spectral information only for the much smaller basis or factor graph, which is of size O(n)$O\left(n\right)$ rather than O(n²)$O\left(n^2\right)$, and it schedules load flow on intragroup and intergroup links separately. We justify the improvements offered by DED-X schemes over traditional X schemes analytically and verify the advantages of our approach, in terms of efficiency and stability, via simulation.     

Optical transpose k-ary n-cube networks

This paper derives a number of results related to the topological properties of OTIS k-ary n-cube interconnection networks. The basic topological metrics of size, degree, shortest distance, and diameter are obtained. Then results related to embedding in OTIS k-ary n-cubes of OTIS k-ary (n−1)-cubes, cycles, meshes, cubes, and spanning trees are derived. The OTIS k-ary n-cube is shown to be Hamiltonian. Minimal one-to-one routing and optimal broadcasting algorithms are proposed. The OTIS k-ary n-cube is shown to be maximally fault-tolerant. These results are derived based on known properties of k-ary n-cube networks and general properties of OTIS networks.     

Biswapped网络(BSN)的拓扑性质研究:点对称性和极大容错性

Biswapped网络(BSN)是一类两层结构的互连网络,它以任意图为模块且模块间采用一种完全两部图方式互连.BSN的互连形式与OTIS网络(即Swapped网络)类似但互连规则更一致,使得BSN展现出更好的性能.文中主要研究BSN的点传递性和容错性能.首先证明BSN能继承因子网络的点传递性质,为BSN上的分析和算法简单性找到理论依据.其次,通过直接构造网络中两点间最大数目的点不相交路径证明以任意连通图为因子网络的BSN是一致极大容错的.这些结果表明BSN既能继承因子网络的理想性能还展现某些好的新特性.最后,通过与OTIS网络、卡式积网络等层次类网络比较表明,BSN提供了一种构建可扩展性、模块化、容错性的大规模并行计算机系统的潜在有竞争力的体系结构形式.     

Calculation of coordinates from molecular geometric parameters and the concept of a geometric calculator

Three different geometric parameters, distance r(i,j), angle θ(i,j, k), and dihedral (or torsion) angle φ(i,j, k, l), are commonly used to specify the shape of a molecule. Given Cartesian coordinates it is simple to calculate such parameters. The, non-trivial, inverse problem of finding coordinates when given such parameters is considered here. When a triple of such geometric parameters is given to specify the position of an atom, n, relative to reference atoms i,j, k,…, with known positions, five qualitatively different cases arise: r(n, i), θ(n, i,j), φ(n, i,j, k), θ(j, n, i) and φ(k, n, i,j). Each such geometric coordinate specifies n to lie on a certain type of surface. To calculate its position one must find the point of intersection of three such surfaces. A program, Evclid, that can perform these calculations is integrated with an interactive set of routines that constitute a geometric calculator and editor. It works on (three-dimensional) points and has a number of input, display and output options. It can translate, rotate, reflect, invert and scale as well as edit the point set or subsets.     

Conditional edge-fault-tolerant Hamiltonicity of dual-cubes

The dual-cube is an interconnection network for linking a large number of nodes with a low node degree. It uses low-dimensional hypercubes as building blocks and keeps the main desired properties of the hypercube. A dual-cube DC(n) has n + 1 links per node where n is the degree of a cluster (n-cube), and one more link is used for connecting to a node in another cluster. In this paper, assuming each node is incident with at least two fault-free links, we show a dual-cube DC(n) contains a fault-free Hamiltonian cycle, even if it has up to 2n − 3 link faults. The result is optimal with respect to the number of tolerant edge faults.     

Thek-track assignment problem

Thek-track assignment problem is a scheduling problem withn jobs andk machines. Each machinej has a certain operational period (track) which starts at timea _j and ends at timeb _j . Each jobi has a specific start times _i and a specific finish timet _i . A schedule is an assignment of certain jobs to machines such that the intervals [s _i ,t _i [assigned to the same machinej do not overlap and fit into track [a _j ,b _j [. We are interested in a schedule which maximizes the number of assigned jobs. AO(n ^k?1 k!k ^k+1 )-algorithm which solves this problem is presented. Furthermore it is shown that the more general problem, in which for each track only a given set of jobs can be scheduled on that track, can be solved inO(n ^k k!k ^k )-time.     

The analysis of Range Quickselect and related problems

Range Quickselect, a simple modification of the well-known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Range Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm.The key element appearing in the analysis of Range Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us.In particular, we have been able to carry out a precise analysis of the expected number of moves of the pth element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results.Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.     

A parallel routing algorithm on recursive cube of rings networks employing Hamiltonian circuit Latin square

Recursive cube of rings (RCR) networks [Y. Sun, P. Cheung, X. Lin, Recursive cube of rings: a new topology for interconnection networks, IEEE Trans. Parallel Dist. Syst. 11 (3) (2000) 275-286] can be widely used in the design and implementation of parallel processing architectures. In this paper, we investigate the routing of a message on RCR networks, that is a key to the performance of this network. We would like to transmit k+1 packets from a source node to a destination node simultaneously along paths on RCR networks, the ith packet will traverse along the ith path (1?i?k+1). In order for all packets to arrive at a destination node quickly and securely, the ith path must be node-disjoint from all other paths. For construction of these paths, employing Hamiltonian circuit Latin square (HCLS), we present O(n²) parallel routing algorithm on RCR networks.     

Star reduction among minimal length addition chains

An addition chain for a natural number n is a sequence \({1=a_0 < a_1 < \cdots < a_r=n}\) of numbers such that for each 0 < i ≤ r, a _i  = a _j  + a _k for some 0 ≤ k ≤ j < i. The minimal length of an addition chain for n is denoted by ?(n). If j = i ? 1, then step i is called a star step. We show that there is a minimal length addition chain for n such that the last four steps are stars. Then we conjecture that there is a minimal length addition chain for n such that the last \({\lfloor\frac{\ell(n)}{2}\rfloor}\)-steps are stars. We verify that the conjecture is true for all numbers up to 2¹⁸. An application of the result and the conjecture to generate a minimal length addition chain reduce the average CPU time by 23–29% and 38–58% respectively, and memory storage by 16–18% and 26–45% respectively for m-bit numbers with 14 ≤ m ≤ 22.     

On embedding cycles into faulty dual-cubes

A dual-cube uses low-dimensional hypercubes as basic components such that keeps the main desired properties of the hypercube. Each hypercube component is referred as a cluster. A (n+1)-connected dual-cube DC(n) has ²2n+1 nodes and the number of nodes in a cluster is n². There are two classes with each class consisting of n² clusters. Each node is incident with exactly n+1 links where n is the degree of a cluster, one more link is used for connecting to a node in another cluster. In this paper, we show that every node of DC(n) lies on a cycle of every even length from 4 to ²2n+1 inclusive for n?3, that is, DC(n) is node-bipancyclic for n?3. Furthermore, we show that DC(n), n?3, is bipancyclic even if it has up to n−1 edge faults. The result is optimal with respect to the number of edge faults tolerant.     

Properties of a hierarchical network based on the star graph

This paper introduces a new class of interconnection networks named star-pyramid. An n-level star-pyramid is formed by piling up star graphs of dimensions 1 to n in a hierarchy, connecting any node in each i-dimensional star, 1 < i ? n, to a node in the (i − 1)-dimensional star whose index is reached by removing the i symbol from the index of the former node in the i-dimensional star graph. Having extracted the properties of the new topology, featuring topological properties, a minimal routing algorithm, a simple but efficient broadcast algorithm, Hamiltonicity and pancyclicity, we then compare the network properties of the proposed topology and the well-known pyramid topology. We show that the star-pyramid has some more attractive properties than its equivalent pyramid. Finally, we propose two variants of star-pyramid, namely the generic star-pyramid and wrapped star-pyramid, as topologies with improved scalability, fault-tolerance, and diameter.     

An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges

In this paper, we study fault-tolerant routing in bijective connection networks with restricted faulty edges. First, we prove that the probability that all the incident edges of an arbitrary node become faulty in an n-dimensional bijective connection network, denoted by X_n, is extremely low when n becomes sufficient large. Then, we give an O(n) algorithm to find a fault-free path of length at most n+3⌈log₂∣F∣⌉+1 between any two different nodes in X_n if each node of X_n has at least one fault-free incident edge and the number of faulty edges is not more than 2n−3. In fact, we also for the first time provide an upper bound of the fault diameter of all the bijective connection networks with the restricted faulty edges. Since the family of BC networks contains hypercubes, crossed cubes, Möbius cubes, etc., all the results are appropriate for these cubes.     

Parametric analysis of overall min-cuts and applications in undirected networks

The overall min-cut problem in a capacitated undirected network is well known. Recently Stoer and Wagner gave an elegant algorithm for finding such a cut. In this paper we present a parametric analysis of such a cut where the capacity of an arc {i,j} in the network is given by min{b_ij,λ}, where λ is a parameter ranging from 0 to ∞. Letting function v(λ) denote the min-cut capacity, we develop an algorithm to describe v(λ) which involves at most n applications of Stoer and Wagner scheme, where n denotes the number of nodes in the network. We use v(λ) to determine an overall min-cut for multiroute flows as defined by Kishimoto. Such multi-route flows have interesting applications in communication networks.     

A symbolic test for (i,j)-uniformity in reduced zero-dimensional schemes

Let Z denote a finite collection of reduced points in projective n-space and let $\mathbf{I}$ denote the homogeneous ideal of Z. The points in Z are said to be in (i,j)-uniform position if every cardinality i subset of Z imposes the same number of conditions on forms of degree j. The points are in uniform position if they are in (i,j)-uniform position for all values of i and j. We present a symbolic algorithm that, given $\mathbf{I}$, can be used to determine whether the points in Z are in (i,j)-uniform position. In addition it can be used to determine whether the points in Z are in uniform position, in linearly general position and in general position. The algorithm uses the Chow form of various d-uple embeddings of Z and derivatives of these forms. The existence of the algorithm provides an answer to a question of Kreuzer.     

A New Topology with Odd Degree for Multiprocessor Systems

A new topology for interconnection networks has been proposed. The underlying network graph hasN= 4ⁿnodes (n≥ 2) and isalmostregular with maximum degree 5 and diameter ≤ ⌊3/4 log₂N⌋ + 1. Algorithms for point-to-point routing and single node broadcast have also been developed. It has also been shown that various algorithms for real life applications, e.g., matrix transpose, matrix multiplication, finding the sum/average/maximum/minimum of a set of data elements and ASCEND/DESCEND types of algorithms can be efficiently implemented on this topology. Finally, the underlying idea of constructing this network has been generalized to define a family ofalmost regularodd degree graphs of maximum degree 2j+ 1, (j> 2) withN= (2j)ⁿnodes and diameter ⌊3/4 log_jN⌋ + 1.     

Some bounds on multiparty communication complexity of pointer jumping

We introduce the model of conservative one-way multiparty complexity and prove lower and upper bounds on the complexity of pointer jumping.? The pointer jumping function takes as its input a directed layered graph with a starting node and k layers of n nodes, and a single edge from each node to one node from the next layer. The output is the node reached by following k edges from the starting node. In a conservative protocol, the ith player can see only the node reached by following the first i–1 edges and the edges on the jth layer for each j > i. This is a restriction of the general model where the ith player sees edges of all layers except for the ith one. In a one-way protocol, each player communicates only once in a prescribed order: first Player 1 writes a message on the blackboard, then Player 2, etc., until the last player gives the answer. The cost is the total number of bits written on the blackboard.?Our main results are the following bounds on k-party conservative one-way communication complexity of pointer jumping with k layers:? (1) A lower bound of order for any .?(2) Matching upper and lower bounds of order for . received March 22, 1996