Transposing Arrays on Multicomputers Using de Bruijn Sequences

Transposing anN×Narray that is distributed row- or columnwise acrossP=Nprocessors is a fundamental communication task that requires time- consuming interprocessor communication. It is the underlying communication task for the fast Fourier transform of long sequences and multidimensional arrays. It is also the key communication task for certain weather and climate models. A parallel transposition algorithm is presented for hypercube and mesh connected multicomputers with programmable networks. The optimal scheduling of network transmissions is not unique and is known to be nontrivial. Here, scheduling is determined by a single de Bruijn sequence ofNbits. The elements in each processor are first preordered and then, in groups of log₂ Padjacent elements, either transmitted or not transmitted, depending on the corresponding bit in the de Bruijn sequence. The algorithm is optimal both in overall time and the time that any individual element is in the network. The results are extended to other communication tasks including shuffles, bit reversal, index reversal, and general index-digit permutation. The caseP≠Nand rectangular arrays with non-power-of-two dimensions are also discussed. Algorithms for mesh connected multicomputers are developed by embedding the hypercube in the mesh. The optimal implementation of the algorithms requires certain architectural features that are not currently available in the marketplace.     

Scalable Network Architectures Using the Optical Transpose Interconnection System (OTIS)

The Optical Transpose Interconnection System (OTIS) proposed by Marsden et al. (Opt. Lett.18, 13 (July 1993), 1083–1085) makes use of free-space optical interconnects to augment an electronic system by adding nonlocal interconnections. In this paper, we show how these connections can be used to implement a large-scale system with a given network topology using small copies of a similar topology. In particular, we show that, using OTIS, an N² node 4-D mesh can be constructed from N copies of the N-node 2-D mesh, an N² node hypercube can be constructed from N copies of the N-node hypercube, and an (N², α², c/2) expander can be constructed from N copies of an (N, α, c) expanders, all with small slowdown. Finally, we show how this expander construction can be used to build multibutterfly networks in a scalable fashion.     

A new parallel algorithm for lagrange interpolation on a hypercube

We present a new parallel algorithm for computing N point lagrange interpolation on an n-dimensional hypercube with total number of nodes p = 2ⁿ. Initially, we consider the case when N = p. The algorithm is extended to the case when only p (p fixed) processors are available, p < N. We assume that N is exactly divisible by p. By dividing the hypercube into subcubes of dimension two, we compute the products and sums appearing in Lagrange's formula in a novel way such that wasteful repetitions of forming products are avoided. The speed up and efficiency of our algorithm is calculated both theoretically and by simulating it over a network of PCs.     

A Generic Design Methodology for Deadlock-Free Routing in Multicomputer Networks

This paper introduces a generic methodology for defining deadlock-free wormhole routing schemes in any arbitrary network. The basic strategy is to partition a graph into subdigraphs with no cyclic dependencies and selectively assign virtual channels. The usefulness of our scheme is shown for the n-dimensional hypercube, the n-dimensional mesh, and the k-ary n-cube torus by identifying subdigraph characteristics that ensure acyclic routing. Further generalization which allows partial cyclic dependencies without deadlock is achieved by our extended generic methodology. We also illustrate how to identify shortest fixed path and nonminimal adaptive routing schemes using minimum required channels.     

Embedding a family of meshes into twisted cubes

The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. The twisted cube is an important variation of the hypercube. Let TQn denote the n-dimensional twisted cube. In this paper, we consider embedding a family of 2-dimensional meshes into a twisted cube. The main results obtained in this paper are: (1) For any odd integer n?1, there exists a mesh of size 2ײn−1 that can be embedded in the TQn with unit dilation and unit expansion. (2) For any odd integer n?5, there exists a mesh of size 4ײn−2 that can be embedded in the TQn with dilation 2 and unit expansion. (3) For any odd integer n?5, a family of two disjoint meshes of size 4ײn−3 can be embedded into the TQn with unit dilation and unit expansion. Results (1) and (3) are optimal in the sense that the dilations and expansions of the embeddings are unit values.     

TDM Hypercube and TWDM Mesh Optical Interconnections

We propose the time division multiplexed hypercube (TDM-cube) and the time/wavelength division multiplexed mesh (TWDM-mesh). The TDM-cube is an extension of the earlier work by Thompson on the dilated slipped banyan network, DSB. While the DSB(N) provides the complete connection among N users in O(N) time via the time division multiplexing, the TDM-cube(N) implements the binary hypercube interconnection among N users in O(log₂ N) time. The TWDM-mesh(n²) uses a DSB(n), and combines the TDM and WDM. Like the Bus-Mesh, it requires at most 2 hops to send a packet from one node to any other node. The TWDM-mesh has a much higher network throughput than the Bus-Mesh. Both the TDM-cube and TWDM-mesh require only one fixed-wavelength transmitter/receiver per node, and they have a simple column control and dilated operation. The performance in terms of scalability, delay, and throughput is considered.     

Multiple Graph Embeddings into a Processor Array with Spanning Buses

A processor array with spanning buses (PASB) is a well-known, versatile parallel architecture. A PASB is obtained from a two-dimensional mesh by replacing each linear connection with a bus. In this paper, we show how to optimally embed multiple copies of a graph into a PASB by a labeling strategy. Our embeddings simultaneously achieve an optimal expansion, congestion, and alignment cost. First, we propose a labeling scheme for anN-node graphG, possibly disconnected, such that this labeling makes it possible to optimally embed multiple copies ofGinto anN′×N′ PASB whereN′ is divisible byN. Second, we show that many important classes of graphs admit this labeling: for example, tree, cycle, mesh of trees, and product graphs such as mesh, torus, or hypercube. Finally, we show how to optimally embed multiple copies of a graph into a multidimensional and possibly nonsquare PASB.     

Hamilton-connectivity and cycle-embedding of the Möbius cubes

The recently introduced interconnection network, the Möbius cube, is an important variant of the hypercube. This network has several attractive properties compared with the hypercube. In this paper, we show that the n-dimensional Möbius cube M_n is Hamilton-connected when n?3. Then, by using the Hamilton-connectivity of M_n, we also show that any cycle of length l (4?l?2ⁿ) can be embedded into M_n with dilation 1 (n?2). It is a fact that the n-dimensional hypercube Q_n does not possess these two properties.     

"Hypermeshes": Optical Interconnection Networks for Parallel Computing

A formal model for a class of optical mesh-based interconnection networks called "hypermeshes" is proposed and characterized. Hypermeshes are based on the concept of orthogonal crossbar switches, with N nodes arranged in n-dimensional mesh structure where all nodes aligned along a dimension are interconnected with an optical multichannel switch. The optical multichannel switches can be modeled as hypergraph "hyperedges" which can perform multiple data transfers over their members simultaneously. The hyperedges can be implemented with space division multiplexing (SDM) in the electrical or optical domains or with wavelength division multiplexing (WDM) over a single fiber in the optical domain. The use of WDM over a fiber also reduces the hypermesh "interconnection complexity" to rival that of a 2D mesh. An architectural characterization is performed and the combinatorial properties, including rearrangeability, permutation capability, partitionability, embedding capability, and bisection bandwidth, are characterized. It is shown that every algorithm which can execute conflict-free on an omega network can execute conflict-free on a hypermesh and that every graph which can be embedded into a hypercube with dilation k can be embedded into a hypermesh with dilation ≤ k. Hypermeshes are shown to have high bisection bandwidths, thereby minimizing the time for many common algorithms such as parallel sorting. It is shown that under the constraint of equivalent aggregate bandwidth the hypermeshes are considerably more powerful computational models than meshes, generalized hypercubes, and other orthogonal graphs. Two attractive optical implementations of hypermeshes using optical technology recently advocated in the literature are also proposed.     

Partial Multinode Broadcast and Partial Exchange Algorithms for d-Dimensional Meshes

In this paper we consider the partial multinode broadcast and the partial exchange communication tasks in d-dimensional meshes. The partial multinode broadcast in an N-processor network is the task in which each of M ≤ N arbitrary nodes broadcasts a packet to all the remaining N − 1 nodes. Correspondingly, in the partial exchange there are M ≤ N nodes that wish to send a separate, personalized packet to each of the other nodes. We propose algorithms for the d-dimensional mesh network that execute the partial multinode broadcast and the partial exchange communication tasks in near-optimal time. No assumption is made concerning the locations of the M source nodes. The communication algorithms proposed are "on line" and distributed. We further look at a dynamic version of the broadcasting problem, where broadcast requests are generated at random times. In particular, we assume that the broadcast requests are generated at each node of the mesh according to a Poisson distribution with rate λ. Based on the partial multinode broadcast algorithm, we propose a dynamic decentralized scheme to execute the broadcasts in this dynamic environment. We find an upper bound on the average delay required to serve each broadcast. We prove that the algorithm is stable for network utilization ρ close to 1, and the average delay is of the order of the diameter for any load in the stability region.     

Optimal Embedding of Multiple Directed Hamiltonian Rings into d-dimensional Meshes

In this paper, we consider the embedding of multiple directed Hamiltonian rings into d-dimensional meshes M_d. Assuming two adjacent nodes in M_d are connected by two directed links with opposite directions, we aim to embed as many directed Hamiltonian rings as possible in a way that they are link-disjoint. In particular, we construct d link-disjoint directed Hamiltonian rings in d-dimensional N₁×…×N_d mesh, where each N_i⩾2d is even.     

A (4n − 9)/3 diagnosis algorithm on n-dimensional cube network

As a generalization of the precise and pessimistic diagnosis strategies of system-level diagnosis of multicomputers, the t/k diagnosis strategy can significantly improve the self-diagnosing capability of a system at the expense of no more than k fault-free processors (nodes) being mistakenly diagnosed as faulty. In the case k ? 2, to our knowledge, there is no known t/k diagnosis algorithm for general diagnosable system or for any specific system. Hypercube is a popular topology for interconnecting processors of multicomputers. It is known that an n-dimensional cube is (4n − 9)/3-diagnosable. This paper addresses the (4n − 9)/3 diagnosis of n-dimensional cube. By exploring the relationship between a largest connected component of the 0-test subgraph of a faulty hypercube and the distribution of the faulty nodes over the network, the fault diagnosis of an n-dimensional cube can be reduced to those of two constituent (n − 1)-dimensional cubes. On this basis, a diagnosis algorithm is presented. Given that there are no more than 4n − 9 faulty nodes, this algorithm can isolate all faulty nodes to within a set in which at most three nodes are fault-free. The proposed algorithm can operate in O(N log₂ N) time, where N = 2ⁿ is the total number of nodes of the hypercube. The work of this paper provides insight into developing efficient t/k diagnosis algorithms for larger k value and for other types of interconnection networks.     

A note on cycle embedding in hypercubes with faulty vertices

Let fv denote the number of faulty vertices in an n-dimensional hypercube. This note shows that a fault-free cycle of length of at least n²−2fv can be embedded in an n-dimensional hypercube with fv=2n−3 and n?5. This result not only enhances the previously best known result, and also answers a question in [J.-S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Computing 29 (2003) 821-832].     

Edge-fault-tolerant vertex-pancyclicity of augmented cubes

The n-dimensional augmented cube, denoted as AQn, a variation of the hypercube, possesses some properties superior to those of the hypercube. In this paper, we show that every vertex in AQn lies on a fault-free cycle of every length from 3 to n², even if there are up to n−1 edge faults. We also show that our result is optimal.     

A Note on Optimal Time Broadcast in Faulty Hypercubes

This note describes an algorithm for broadcasting a message on the n-dimensional hypercube in optimal time (n time units) and optimal communication (2ⁿ − 1 messages) in the presence of up to n − 2 arbitrary node or edge faults, assuming the set of faults is known to all nodes of the hypercube.     

Constrained piecewise linear systems with disturbances: Controller design via convex invariant sets

This paper presents two control strategies under the time optimal control and model predictive control frameworks for constrained piecewise linear systems with bounded disturbances (PWLBD systems). Each of the proposed approaches uses an inner convex polytopal approximation of the non‐convex domains of attraction and results in simplified control laws that can be determined off‐line via multi‐parametric programming. These control strategies rely on invariant sets of PWLBD systems. Thereby, approaches for the computation of the disturbance invariant outer bounds of the minimal disturbance invariant set, F_∞, and convex polytopal disturbance invariant sets are presented. The effectiveness of the approaches is assessed through numerical examples. Copyright © 2007 John Wiley & Sons, Ltd.     

Polytope-based computation of polynomial ranges

Polynomial ranges are commonly used for numerically solving polynomial systems with interval Newton solvers. Often ranges are computed using the convex hull property of the tensorial Bernstein basis, which is exponential size in the number n of variables. In this paper, we consider methods to compute tight bounds for polynomials in n variables by solving two linear programming problems over a polytope. We formulate a polytope defined as the convex hull of the coefficients with respect to the tensorial Bernstein basis, and we formulate several polytopes based on the Bernstein polynomials of the domain. These Bernstein polytopes can be defined by a polynomial number of halfspaces. We give the number of vertices, the number of hyperfaces, and the volume of each polytope for n=1,2,3,4, and we compare the computed range widths for random n-variate polynomials for n?10. The Bernstein polytope of polynomial size gives only marginally worse range bounds compared to the range bounds obtained with the tensorial Bernstein basis of exponential size.     

Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations

It has been shown that for every perfect matching M of the d-dimensional n-vertex hypercube, d?2, n=d², there exists a second perfect matching M^′ such that the union of M and M^′ forms a Hamiltonian circuit of the d-dimensional hypercube. We prove a generalization of a special case of this result when there are two dimensions that do not get used by M. It is known that the number Md of perfect matchings of the d-dimensional hypercube satisfies and, in particular, (2d/n)^n/2(n/2)!?Md?(d!)^n/(2d). It has also been shown that the number Hd of Hamiltonian circuits of the hypercube satisfies 1?limd→∞(logHd)/(logMd)?2. We finally strengthen this result to a nearly tight bound ((dlog2/(eloglogd))(1−on(1)))?Hd?(d!)^n/(2d)((d−1)!)^n/(2(d−1))/2 proving that limd→∞(logHd)/(logMd)=2. This means that the bound Hd?Md is improved to a nearly tight , so the number of Hamiltonian circuits in the hypercube is nearly quadratic in the number of perfect matchings. The proofs are based on a result for graphs that are the Cartesian product of squares and arbitrary bipartite regular graphs that have a Hamiltonian cycle. We also study a labeling scheme related to matchings.     

An improved upper bound on the queuenumber of the hypercube

In this note, we show that the n-dimensional hypercube Q(n) can be laid out using n−2 queues for all n?5. Our result improves the previously known result for the case n?5.     

A discrete methodology for controlling the sign of curvature and torsion for NURBS

This paper develops a discrete methodology for approximating the so-called convex domain of a NURBS curve, namely the domain in the ambient space, where a user-specified control point is free to move so that the curvature and torsion retains its sign along the NURBS parametric domain of definition. The methodology provides a monotonic sequence of convex polyhedra, converging from the interior to the convex domain. If the latter is non-empty, a simple algorithm is proposed, that yields a sequence of polytopes converging uniformly to the restriction of the convex domain to any user-specified bounding box. The algorithm is illustrated for a pair of planar and a spatial Bézier configuration.