Optimal Fully Adaptive Minimal Wormhole Routing for Meshes

A deadlock-free fully adaptive minimal routing algorithm for meshes that is optimal in the number of virtual channels required and in the number of restrictions placed on the use of these virtual channels is presented. It is also proved that, ignoring symmetry, this routing algorithm is the only fully adaptive routing algorithm with uniform routers that achieves both of these goals. This new algorithm requires only 4n-2 virtual channels for an n-dimensional mesh. In addition, if more than the minimum number of virtual channels is available, the routing algorithm can use these additional channels with the fewest possible number of restrictions. The proofs are first presented for the 2D mesh and then generalized to n-dimensional meshes.     

Very Efficient Cyclic Shifts on Hypercubes

Cyclic shifts are intrinsic operations in many parallel algorithms. Therefore, it is important to execute them efficiently. In this note, we present and analyze an algorithm for the cyclic shift operation onn-dimensional (distributed memory) hypercubes. On asynchronous hypercubes, we have shown that all previously known algorithms for cyclic shifts need local message buffers. In order to overcome this, we present an algorithm that always uses link-disjoint paths for routing. We prove that by using this algorithm, any cyclic shift can be realized by using at most 4/3nsteps, without using any local message buffers.     

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.     

Routing Permutations on Hypercube Machines with Half-Duplex Links

Algorithms are presented for realizing permutations on a less restrictive hypercube model called the S-MIMD (synchronous MIMD), which allows at most one data transfer on a given communication link at a given time instant, and where data movements are not restricted to a single dimension at a given time. First, an optimal algorithm for bit-permute permutations is developed from a very simple realization of the shuffle on a 3-cube; this algorithm needs 2⌊n/2⌋ routing steps on an n-dimensional hypercube. The technique is then extended to an optimal algorithm for bit-permute-complement permutations, one that needs n routing steps. Also, algorithms are sketched for routing permutations in the classes Ω and Ω⁻¹ in 3⌈n/2⌉ routing steps, yielding an off-line algorithm for routing arbitrary permutations in 3n steps.     

A necessary and sufficient condition for deadlock-free adaptiverouting in wormhole networks

Deadlock avoidance is a key issue in wormhole networks. A first approach by W.J. Dally and C.L. Seitz (1987) consists of removing the cyclic dependencies between channels. Many deterministic and adaptive routing algorithms have been proposed based on that approach. Although the absence of cyclic dependencies is a necessary and sufficient condition for deadlock-free deterministic routing, it is only a sufficient condition for deadlock-free adaptive routing. A more powerful approach by J. Duato (1991) only requires the absence of cyclic dependencies on a connected channel subset. The remaining channels can be used in almost any way. In this paper, we show that the previously mentioned approach is also a sufficient condition. Moreover, we propose a necessary and sufficient condition for deadlock-free adaptive routing. This condition is the key for the design of fully adaptive routing algorithms with minimum restrictions, An example shows the application of the new theory     

The fastcube: a variation on hypercube topology with lower diameter

This paper presents a class of n-dimensional interconnection topologies with N=2ⁿ nodes which we refer to as n-fastcubes. The node degree of the n-fastcube is n and its diameter is ⌈(n+1)/2⌉, which is substantially smaller than that of the same size hypercube. Topological properties as well as several routing algorithms for fastcubes are developed. In addition, a new methodology for the design and analysis of fastcubes is employed. This methodology is based on modeling interconnection networks as finite state automata. The inputs to these particular automata are routing sequences. The routing and embedding algorithms developed in this paper produce routing sequences. The main characteristic of routing sequences is their node independence. A node independent routing sequence, p(H), produces a path between any pair of nodes with the Hamming distance of H. Thus, these sequences can be used, without modification, at any node to establish paths in a fastcube.     

Task migration in n-dimensional wormhole-routed mesh multicomputers

In a mesh multicomputer, performing jobs needs to schedule submeshes according to some processor allocation scheme. In order to assign the incoming jobs to a free submesh, a task compaction scheme is needed to generate a larger contiguous free region. The overhead of compaction depends on the efficiency of the task migration scheme. In this paper, two simple task migration schemes are first proposed in n-dimensional mesh multicomputers with supporting dimension-ordered wormhole routing in one-port communication model. Then, a hybrid scheme which combines advantages of the two schemes is discussed. Finally, we evaluate the performance of all of these proposed approaches.     

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.     

A theory of deadlock-free adaptive multicast routing in wormholenetworks

A theory for the design of deadlock-free adaptive routing algorithms for wormhole networks, proposed by the author (1991, 1993), supplies sufficient conditions for an adaptive routing algorithm to be deadlock-free, even when there are cyclic dependencies between channels. Also, two design methodologies were proposed. Multicast communication refers to the delivery of the same message from one source node to an arbitrary number of destination nodes. A tree-like routing scheme is not suitable for hardware-supported multicast in wormhole networks because it produces many headers for each message, drastically increasing the probability of a message being blocked. A path-based multicast routing model was proposed by Lin and Ni (1991) for multicomputers with 2D-mesh and hypercube topologies. In this model, messages are not replicated at intermediate nodes. This paper develops the theoretical background for the design of deadlock-free adaptive multicast routing algorithms. This theory is valid for wormhole networks using the path-based routing model. It is also valid when messages with a single destination and multiple destinations are mixed together. The new channel dependencies produced by messages with several destinations are studied. Also, two theorems are proposed, developing conditions to verify that an adaptive multicast routing algorithm is deadlock-free, even when there are cyclic dependencies between channels. As an example, the multicast routing algorithms of Lin and Ni are extended, so that they can take advantage of the alternative paths offered by the network     

Proof Pearl: A Formal Proof of Dally and Seitz’ Necessary and Sufficient Condition for Deadlock-Free Routing in Interconnection Networks

Avoiding deadlock is crucial to interconnection networks. In ’87, Dally and Seitz proposed a necessary and sufficient condition for deadlock-free routing. This condition states that a routing function is deadlock-free if and only if its channel dependency graph is acyclic. We formally define and prove a slightly different condition from which the original condition of Dally and Seitz can be derived. Dally and Seitz prove that a deadlock situation induces cyclic dependencies by reductio ad absurdum. In contrast we introduce the notion of a waiting graph from which we explicitly construct a cyclic dependency from a deadlock situation. Moreover, our proof is structured in such a way that it only depends on a small set of proof obligations associated to arbitrary routing functions and switching policies. Discharging these proof obligations is sufficient to instantiate our condition for deadlock-free routing on particular networks. Our condition and its proof have been formalized using the ACL2 theorem proving system.     

On the performance of multicomputer interconnection networks

Several researchers have analysed the performance of k-ary n-cubes taking into account channel bandwidth constraints imposed by implementation technology, namely the constant wiring density and pin-out constraints for VLSI and multiple-chip technology respectively. For instance, Dally [IEEE Trans. Comput. 39(6) (1990) 775], Abraham [Issues in the architecture of direct interconnection networks schemes for multiprocessors, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1992], and Agrawal [IEEE Trans. Parallel Distributed Syst. 2(4) (1991) 398] have shown that low-dimensional k-ary n-cubes (known as tori) outperform their high-dimensional counterparts (known as hypercubes) under the constant wiring density constraint. However, Abraham and Agrawal have arrived at an opposite conclusion when they considered the constant pin-out constraint. Most of these analyses have assumed deterministic routing, where a message always uses the same network path between a given pair of nodes. More recent multicomputers have incorporated adaptive routing to improve performance. This paper re-examines the relative performance merits of the torus and hypercube in the context of adaptive routing. Our analysis reveals that the torus manages to exploit its wider channels under light traffic. As traffic increases, however, the hypercube can provide better performance than the torus. Our conclusion under the constant wiring density constraint is different from that of the works mentioned above because adaptive routing enables the hypercube to exploit its richer connectivity to reduce message blocking.     

A Necessary and Sufficient Condition for Deadlock-Free Wormhole Routing

An important open problem in wormhole routing has been to find a necessary and sufficient condition for deadlock-free adaptive routing. Recently, Duato has solved this problem for a restricted class of adaptive routing algorithms. In this paper, a necessary and sufficient condition is proposed that can be used for any adaptive or nonadaptive routing algorithm for wormhole routing, as long as only local information is required for routing. The underlying proof technique introduces a new type of dependency graph, thechannel waiting graph, which omits most channel dependencies that cannot be used to create a deadlock configuration. The necessary and sufficient condition can be applied in a straightforward manner to most routing algorithms. This is illustrated by proving deadlock freedom for a partially adaptive nonminimal mesh routing algorithm that does not require virtual channels and a fully adaptive minimal hypercube routing algorithm with two virtual channels per physical channel. Both routing algorithms are more adaptive than any previously proposed routing algorithm with similar virtual channel requirements.     

A classification of generic families of control-affine systems and their bifurcations

We study control-affine systems with n − 1 inputs evolving on an n-dimensional manifold for which the distribution spanned by the control vector fields is involutive and of constant rank (equivalently, they may be considered as 1-dimensional systems with n − 1 inputs entering nonlinearly). We provide a complete classification of such generic systems and their one-parameter families. We show that a generic family for n > 2 is equivalent (with respect to feedback or orbital feedback transformations) to one of nine canonical forms which differ from those for n = 2 by quadratic terms only. We also describe all generic bifurcations of 1-parameter families of systems of the above form.     

Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks

We consider the problem of permutation routing on a star graph, an interconnection network which has better properties than the hypercube. In particular, its degree and diameter are sublogarithmic in the network size. We present optimal randomized routing algorithms that run in O(D) steps (where D is the network diameter) for the worst-case input with high probability. We also show that for the n-way shuffle network with N = nⁿ nodes, there exists a randomized routing algorithm which runs in O(n) time with high probability. Another contribution of this paper is a universal randomized routing algorithm that could do optimal routing for a large class of networks (called leveled networks) which includes the star graph. The associative analysis is also network-independent. In addition, we present a deterministic routing algorithm, for the star graph, which is near optimal. All the algorithms we give are oblivious. As an application of our routing algorithms, we also show how to emulate a PRAM optimally on this class of networks.     

An optimal time bound for oblivious routing

The problem of routing data packets in a constant-degree network is considered. A routing scheme is calledoblivious if the route taken by each packet is uniquely determined by its source and destination. The time required for the oblivious routing ofn packets onn processors is known to be Θ(√n). It is demonstrated that the presence of extra processors can expedite oblivious routing. More specifically, the time required for the oblivious routing ofn packets onp processors is Θ(n/√p + logn).     

Reconfiguration of Rings and Meshes in Faulty Hypercubes

In this paper we present schemes for reconfiguration of embedded task graphs in hypercubes. Previous results, which use either fault-tolerant embedding or an automorphism approach, can be expensive in terms of either the required number of spare nodes or reconfiguration time. Using the free dimension concept, we combine the above two approaches in our schemes which can tolerate about n faulty nodes under the worst case while keeping task migration time small. With expansion-2 initial embedding, three distributed reconfiguration schemes are presented in this paper. The first scheme, applied to chains and rings, can tolerate any ƒ ≤ n − 2 faulty nodes in an n-dimensional hypercube. The second and third schemes are applied to meshes or tori. For a mesh or torus of size 2^m₁ 1 ··· 1 2^m_d, the second scheme can tolerate any ƒ ≤ m_i − 1 faulty nodes, where m_i is the largest direction of the mesh and n = m₁ + ··· + m_d + 1. By embedding two copies of meshes or tori in cube, the third scheme can tolerate any ƒ ≤ n − 1 faulty nodes with the dilation of embedding after reconfiguration degraded to 2. The third scheme is quite general and can be applied to any task graph.     

Towards understanding optimal MIMD queueless routing of arbitrary permutations on hypercubes

This paper addresses the problem of the offline routing of arbitrary permutations on hypercubes under the MIMD queueless communication constraints which imposes that only one message can be located in each node of the hypercube right through the routing. According to e-cube routing, this kind of communication may require in the worst cases at least n exchanges steps on an n-dimensional hypercube. It has been conjectured that in the general case n steps suffice. The conjecture has been proved either by enumeration or by program for the particular cases of n??3. We revisit the problem through the k-partitioning paradigm based on maximum matching of bipartite graphs concept to take advantage of the recursive structure of the hypercube topology. The paradigm consists in looking for each message a transition node distant of at most say k<n hops from its current node such that all the messages can be routed to their transition nodes in k hops then finally routed to their final destination nodes in n?k hops on two disjoints hypercubes. In others words, the paradigm consists to determine an upstream permutation routable in k steps and which leads to two independent downstream permutations routable in n?k steps on two disjoint hypercubes. With this purpose, we give a characterization of the non-1-partitionable permutations from which the proof of the conjecture comes straightforwardly for n??2 and the non-1-partitionable permutations can be built whatever n may be. For n=3, we thus confirm the existence of exactly three classes of non-1-partitionable permutations and prove that there are two classes of upstream permutations to avoid when 2-partitioning any non-1-partitionable permutation. The process to avoid such upstream permutations is presented, and leads to a formal proof of the conjecture for n=3. For n>3, experiences gained in routing permutations on 4D-hypercubes allow conjecturing that in these cases, too, any non-1-partitionable permutation is 2-partitionable. Indeed, the analysis carried out for the 3D-hypercubes is repeatable to identify, certainly more laboriously given their combinatory, the upstream permutations to avoid when 2-partitioning a non-1-partitionable permutation on a 4D-hypercube. The proof that resulting downstream permutations on a 3D-hypercube can be routed in 2 steps is a consequence of the fact that for n=2 and 3 any permutation on a nD-hypercube can be routed in n steps.     

A Study of Permutation Networks: New Designs and Some Generalizations

Permutation networks have been used in the literature to model interprocessor and processor-memory interconnections in parallel computers. This paper introduces new permutation network designs and generalizes the notion of a permutation network to provide a more flexible model of such interconnections. The new designs are based concentrators and superconcentrators, and for n inputs they can be optimized to obtain self-routing permutation networks with O(n lg n) cost, O(lg n) depth, and O(lg²n) routing time. The main feature of these new network designs is that they do not require complex routing schemes such as Clos networks since they are inherently self-routing. Generalizations of these designs are also given to obtain permutation networks in which the numbers of inputs and outputs may be different, and/or the maximum number of parallel routes between inputs and outputs can be less than the number of inputs or outputs, or both. For n inputs, αn outputs, and O(n^ϵ) parallel routes, where 0 < α ≤ 1, 0 < ϵ < 1, these generalized designs can be optimized to have permutation networks with O(n) cost, O(lg n), depth, and O(lg²n) routing time. It is shown that the previously known designs, such as Clos networks, result in inferior realizations when compared with these new designs.