Bounds on the Diameter of One-Dimensional Pec Networks

The diameter of a packed exponential connections (PEC) network on N nodes is shown to be Θ([formula] × [formula]).⁴ A routing algorithm which can route between any two nodes in O([formula] × [formula]) steps is shown. A methodology to find a set of links to be used by a shortest path from node 1 to node N − 1 is derived. We also show that semigroup operations can be performed in O([formula] × [formula]) parallel steps.     

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.     

双环Petersen图互联网络及路由算法

Petersen图由于具有短直径和正则性等特性,因此在并行与分布式计算中具有良好的性能.基于双环结构,构造了一个双环Petersen图互联网络DLCPG(k).同时,分别设计了DLCPG(k)上的单播、广播和容错路由算法.证明了DLCPG(k)不但具有良好的可扩展性、短的网络直径和简单的拓扑结构等特性,而且对于10k个节点组成的互联网络,DLCPG(k)还具有比二维Torus以及RP(k)互联网络更小的直径和更优越的可分组性.另外,还证明了其上的单播、广播路由算法的通信效率与RP(k)上的单播和广播路由算法的通信效率相比均有明显的提高.仿真实验表明,新的容错路由算法也具有良好的容错性能.     

Metacube—a versatile family of interconnection networks for extremely large-scale supercomputers

In the next decade, the high-performance supercomputers will consist of several millions of CPUs. The interconnection networks in such supercomputers play an important role for achieving high performance. In this paper, we introduce the Metacube (MC), a versatile family of interconnection network that can connect an extremely large number of nodes with a small number of links per node and keep the diameter rather low. An MC network has a 2-level hypercube structure. An MC(k,m) network can connect 2^2km+k2^{2^{k}m+k} nodes with m+k links per node, where k is the dimension of the high-level hypercubes (classes) and m is the dimension of the low-level hypercubes (clusters). An MC is a symmetric network with short diameter, easy and efficient routing and broadcasting similar to that of the hypercube. However, the MC network can connect millions of nodes with up to 6 links per node. An MC(2,3) with 5 links per node has 16,384 nodes and an MC(3,3) with 6 links per node has 134,217,728 nodes. We describe the MC network’s structure, topological properties, routing and broadcasting algorithms, and the Hamiltonian cycle embedding in the Metacube networks.     

Minimal Adaptive Routing on the Mesh with Bounded Queue Size

An adaptive routing algorithm is one in which the path a packet takes from its source to its destination may depend on other packets it encounters. Such algorithms potentially avoid network bottlenecks by routing packets around “hot spots.” Minimal adaptive routing algorithms have the additional advantage that the path each packet takes is a shortest one. For a large class of minimal adaptive routing algorithms, we present an Ω(n²/k²) bound on the worst case time to route a static permutation of packets on ann×nmesh or torus with nodes that can hold up tok≥ 1 packets each. This is the first nontrivial lower bound on adaptive routing algorithms. The argument extends to more general routing problems, such as theh–hrouting problem. It also extends to a large class of dimension order routing algorithms, yielding an Ω(n²/k) time bound. To complement these lower bounds, we present two upper bounds. One is anO(n²/k+n) time dimension order routing algorithm that matches the lower bound. The other is the first instance of a minimal adaptive routing algorithm that achievesO(n) time with constant sized queues per node. We point out why the latter algorithm is outside the model of our lower bounds.     

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.     

The Flexible Hypercube: A New Fault-Tolerant Architecture for Parallel Computing

This paper presents the new Flexible Hypercube architecture. The Flexible Hypercube is a fault-tolerant network topology that can be constructed for an arbitrary number of nodes and is incrementally expandable. This topology maintains the strong features of the Hypercube while overcoming deficiencies in expandability. It is shown to have strong node connectivity, a small diameter, and to be tolerant of faults. The Flexible Hypercube is a suitable architecture for the design of both tightly coupled parallel systems and distributed systems. Efficient fault-free and fault-tolerant algorithms for message routing and broadcasting are presented for the architecture. The fault-free algorithm guarantees successful routing inO(logN) time, whereNis the number of nodes in the system, and the fault-tolerant algorithm guarantees routing to functioning nodes if a route exists. The fault-free and fault-tolerant broadcasting algorithms have time complexityO(logN), and the fault-tolerant algorithm guarantees success if no two faulty nodes are adjacent and no functioning node is adjacent to two faults.     

All-to-All Optical Routing in Chordal Rings of Degree 4

We consider the problem of routing in networks employing all-optical routing technology. In such networks, information between nodes of the network is transmitted as light on fiber-optic lines without being converted to electronic form in between. We consider switched optical networks that use the wavelength-division multiplexing (or WDM) approach. A WDM network consists of nodes connected by point-to-point fiber-optic links, each of which can support a fixed number of wavelengths. The switches are capable of redirecting incoming streams based on wavelengths, without changing the wavelengths. Different messages may use the same link concurrently if they are assigned distinct wavelengths. However, messages assigned the same wavelength must be assigned edge-disjoint paths. Given a communication instance in a network, the optical routing problem is the assignment of {routes} to communication requests of the instance, as well as wavelengths to routes so that the number of wavelengths used by the instance is minimal. We focus on the all-to-all communication instance I _A in a widely studied family of chordal rings of degree 4, called optimal chordal rings . For these networks, we prove exact bounds on the optimal load induced on an edge for I _A , over all shortest-path routing schemes. We show an approximation algorithm that solves the optical routing problem for I _A using at most 1.006 times the lower bound on the number of wavelengths. The previous best approximation algorithm has a performance ratio of 8. Furthermore, we use a variety of novel techniques to achieve this result, which are applicable to other communication instances and may be applicable to other networks. Received July 22, 1998; revised October 14, 1999.     

Efficient Communication Strategies for Ad Hoc Wireless Networks

An ad hoc wireless network is a collection of wireless mobile hosts forming a temporary network without the aid of any established infrastructure or centralized administration. This type of network is of great importance in situations where it is very difficult to provide the necessary infrastructure, but it is a challenging task to enable fast and reliable communication within such a network. In this paper we model and analyze the performance of so-called power-controlled ad hoc wireless networks: networks where the mobile hosts are able to change their transmission power. We concentrate on finding schemes for routing arbitrary permutations in these networks. In general, it is NP-hard even to find an n ^1-ε -approximation for any constant ε to the fastest possible strategy for routing a given permutation problem on n mobile hosts. However, we demonstrate here that if we allow ourselves to consider slightly less general problems, efficient solutions can be found. We first demonstrate that there is a natural class of distributed schemes for handling node-to-node communication on top of which online route selection and scheduling strategies can be constructed such that the performance of this class of schemes can be exploited in a nearly optimal way for routing permutations in any static power-controlled ad hoc network. We then demonstrate that if we restrict ourselves to the important case of routing between nodes distributed randomly in a Euclidean space, we can route in a time that is asymptotically optimal for any routing scheme. Received in final form January 31, 2000. Online publication October 10, 2000.     

Hierarchical Hypercube Networks (HHN) for Massively Parallel Computers

The hypercube is one of the most widely used topologies because it provides small diameter and embedding of various interconnection networks. For very large systems, however, the number of links needed with the hypercube may become prohibitively large. In this paper, we propose a hierarchical interconnection network based on hypercubes called hierarchical hypercube network (HHN) for massively parallel computers. The HHN has a smaller number of links than the comparable hypercube and in particular, when we construct networks with 2^Knodes, the node degree of HHN with the minimum node degree isO([formula]) while that of hypercube isO(K). Regardless of its smaller node degree, many parallel algorithms can be executed in HHN with the same time complexity as in the hypercube.     

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.     

Compact Routing on Chordal Rings of Degree 4

A chordal ring G(n;c) of degree 4 is a ring of n nodes with chords connecting each vertex i to the vertex (i + c) mod n . In this paper we investigate compact routing schemes on such networks. We show an optimal boolean routing scheme for any such network that requires O( log n) bits of storage at each node, and O(1) time to compute a shortest path to any destination. This improves on the results of [16] which gives a linear time algorithm for such networks and [6] where efficient routing schemes for certain fixed values of c were developed. Further, we show several bounds on interval routing schemes for such networks. We show that while every chordal ring has an optimal interval routing scheme with at most intervals on any edge, there exist chordal rings for which any optimal interval routing scheme that labels the vertices around the ring in the graph requires intervals on some edges. Additionally, there are chordal rings which admit no optimal one-interval routing schemes, regardless of the vertex labeling. We also consider interval routing schemes under relaxed requirements for the lengths of paths. Received September 5, 1997; revised December 1, 1997.     

Fast algorithms for bit-serial routing on a hypercube

In this paper we describe anO(logN)-bit-step randomized algorithm for bit-serial message routing on a hypercube. The result is asymptotically optimal, and improves upon the best previously known algorithms by a logarithmic factor. The result also solves the problem of on-line circuit switching in anO(1)-dilated hypercube (i.e., the problem of establishing edge-disjoint paths between the nodes of the dilated hypercube for any one-to-one mapping).Our algorithm is adaptive and we show that this is necessary to achieve the logarithmic speedup. We generalize the Borodin-Hopcroft lower bound on oblivious routing by proving that any randomized oblivious algorithm on a polylogarithmic degree network requires at least (log² N/log logN) bit steps with high probability for almost all permutations.This research was supported by the Defense Advanced Research Projects Agency under Contracts N00014-87-K-825 and N00014-89-J-1988, the Air Force under Contract AFOSR-89-0271, and the Army under Contract DAAL-03-86-K-0171. This work was completed while the third and fourth authors were at the Laboratory for Computer Science, Massachusetts Institute of Technology.     

Throughput bounds for closed queueing networks

Analytical lower and upper bounds for the throughput of closed queueing networks with single and delay (infinite) servers are studied in this paper. The numerical evaluation of these bounds requires a small number of significant operations which is independent of the population N. This is in contrast to the exact computation of the throughput which requires at least O(N) operations as N tends to infinity. The bounds are given by simple closed-form analytical expressions and may be more suitable for various performance studies than the algorithmical form of the exact solution.In this paper, the previously known balanced-job bounds are generalized to networks containing delay servers (terminals) and a hierarchy of bounds is obtained for single and multiple class networks. For the single class network, further new bounds are derived: lower and upper bounds that require the evaluation of one square root and an upper bound that requires a constant number of exponentiations. This upper bound does not employ the balancing of server loadings and is especially useful for asymptotic analysis in the case of a large number of customers N.     

Efficient Parallel Matrix Inversion on Interconnection Networks

In this paper, we present efficient algorithms for the inversion of a triangular matrix on different interconnection networks. For hypercubes, we describe an elegant straightforward implementation of L. Csansky's well known PRAM algorithm [Ph.D. dissertation, Computer Sci. Div., Univ. of California, Berkeley 1974]. The time complexity is (log²n) usingn³processors, i.e., within the same order as the PRAM algorithm. Moreover, we give a general approach for the design of triangular matrix inversion algorithms on a large class of networks. Applied to some of these networks, as, e.g., the de Bruijn network, the shuffle-exchange network, and the cube-connected-cycles, this approach yields triangular matrix inversion algorithms that meet the PRAM complexity bounds of the problem within a small constant.     

Perfect difference networks and related interconnection structures for parallel and distributed systems

In view of their applicability to parallel and distributed computer systems, interconnection networks have been studied intensively by mathematicians, computer scientists, and computer designers. In this paper, we propose an asymptotically optimal method for connecting a set of nodes into a perfect difference network (PDN) with diameter 2, so that any node is reachable from any other node in one or two hops. The PDN interconnection scheme, which is based on the mathematical notion of perfect difference sets, is optimal in the sense that it can accommodate an asymptotically maximal number of nodes with smallest possible node degree under the constraint of the network diameter being 2. We present the network architecture in its basic and bipartite forms and show how the related multidimensional PDNs can be derived. We derive the exact average internode distance and tight upper and lower bounds for the bisection width of a PDN. We conclude that PDNs and their derivatives constitute worthy additions to the repertoire of network designers and may offer additional design points that can be exploited by current and emerging technologies, including wireless and optical interconnects. Performance, algorithmic, and robustness attributes of PDNs are analyzed in a companion paper.     

Efficient Deadlock-Free Wormhole Routing and Virtual-Channel Reduction in Shuffle-Based Networks

Many aspects of shuffle-based networks have recently been studied by numerous researchers. However, no attention has been paid to deadlock-free wormhole routing algorithms. In this paper, for a set of shuffle-based networks, we introduce a graph-partitioning technique that enables a deadlock-free routing algorithm with fewer virtual channels than the known algorithms. This is achieved for the de Bruijn digraphs which are shown to require a maximum ofm− ⌊(m− 1)/r⌋ virtual channels per physical channel, wheremis the diameter andris the radix. Algorithms for the generalized de Bruijn graph, the de Bruijn Cube (dBCube) graph and the Shuffle–Exchange network are introduced, and virtual channel requirements are determined. The dBCube graph of size (r,N_b,n) requires a maximum ofm− ⌊(m− 1)/r⌋ virtual channels for the outcluster channels, and a maximum ofm+ 1 − ⌊m/r⌋ virtual channels for the incluster channels in most cases, wherem= ⌊log_rN_b⌋,ris the radix of a generalized de Bruijn graph of sizeN_b, andnrepresents the number of dimensions in a binary hypercube. We also show that a maximum ofm− ⌊(m− 1)/2⌋ virtual channels are required in shuffle-exchange networks with 2^mnodes.     

Beating the Logarithmic Lower Bound: Randomized Preemptive Disjoint Paths and Call Control Algorithms

We consider the maximum disjoint paths problem and its generalization, the call control problem, in the on-line setting. In the maximum disjoint paths problem, we are given a sequence of connection requests for some communication network. Each request consists of a pair of nodes, that wish to communicate over a path in the network. The request has to be immediately connected or rejected, and the goal is to maximize the number of connected pairs, such that no two paths share an edge. In the call control problem, each request has an additional bandwidth specification, and the goal is to maximize the total bandwidth of the connected pairs (throughput), while satisfying the bandwidth constraints (assuming each edge has unit capacity). These classical problems are central in routing and admission control in high speed networks and in optical networks.We present the first known constant-competitive algorithms for both problems on the line. This settles an open problem of Garay et al. and of Leonardi. Moreover, to the best of our knowledge, all previous algorithms for any of these problems, are (logn)-competitive, where n is the number of vertices in the network (and obviously noncompetitive for the continuous line). Our algorithms are randomized and preemptive. Our results should be contrasted with the (logn) lower bounds for deterministic preemptive algorithms of Garay et al. and the (logn) lower bounds for randomized non-preemptive algorithms of Lipton and Tomkins and Awerbuch et al. Interestingly, nonconstant lower bounds were proved by Canetti and Irani for randomized preemptive algorithms for related problems but not for these exact problems.     

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     

RCC-Full: An Effective Network for Parallel Computations

A new interconnection network is proposed for the construction of a massively parallel computer system. The systematic construction of this interconnection network, denoted RCC-FULL, is performed by methodically connecting together a number of basic atoms where a basic atom is a set of fully interconnected nodes. Key communication characteristics are derived and evaluated for RCC-FULL and efficient routing algorithms, which need only local information to route messages between any two nodes, are also derived. AnO(log (N)) sorting algorithm is shown for RCC-FULL and RCC-FULL is shown to emulate deterministically the CRCW PRAM model, with onlyO(log (N)) degradation in time performance. Finally, the hardware cost for the RCC-FULL is estimated as a function of its pin requirements and compared to that of the binary hypercube and most instances of RCC-FULL have substantially lower cost. Hence, RCC-FULL appears to be a particularly effective network for PRAM emulation, and might be considered as a universal network for future supercomputing systems.