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.     

通过改变开关状态实现多源点多播

在并行和分布式环境中 ,多个结点之间的通讯一直是研究工作的焦点问题 ,这些通讯主要包括置换、多播(Multicast)及多源点多播 (Multiple Multicast) .L ai提出了适用于一类与带缓存的 Cube网相互拓扑等价的网络的置换算法 ,硬件代价为 O(N log N ) ,算法的时间复杂度为 O(N ) .Feng提出的 inside- out算法实现了 Omega- 1 × Omega网上的置换 ,总的路由时间复杂度为 O(N log N) ,硬件代价为 O(N log N) .支持严格无阻塞置换的三级 Clos网的总的交叉点数为O(N32 ) .支持严格无阻塞的多播的三级 Clos网为 O(N32 logrloglogr) .Yang提出了一种新的多播网络 ,硬件复杂度为 O(N log2 N ) .为了支持多源点多播 ,多级互联网硬件代价往往大幅上升 .本文借鉴了 L ai提出的规则改变开关状态的方法 ,并把这种算法推广到了多源点多播的情况 .提出了一种新的多源点多播路由算法 ,此算法也同样适用于这一类相互拓扑等价的多级互联网 ,包括 Baseline、Om ega、Cube等 .在此算法中 ,每个数据流被划分为固定大小的数据包 ,在网络中独立传送 ,网络中的每个开关的状态按照固定的状态每个时步规则变化 ,每个数据包两次经过网络后到达目标结点 .此类的网络的硬件代价为 O(Nlog N ) ,此多源点多播路由算法的时间复杂度为 O(N )     

Routing permutations on baseline networks with node-disjoint paths

Permutation is a frequently-used communication pattern in parallel and distributed computing systems and telecommunication networks. Node-disjoint routing has important applications in guided wave optical interconnects where the optical "crosstalk" between messages passing the same switch should be avoided. In this paper, we consider routing arbitrary permutations on an optical baseline network (or reverse baseline network) with node-disjoint paths. We first prove the equivalence between the set of admissible permutations (or semipermutations) of a baseline network and that of its reverse network based on a step-by-step permutation routing. We then show that an arbitrary permutation can be realized in a baseline network (or a reverse baseline network) with node-disjoint paths in four passes, which beats the existing results [M. Vaez et al., (2000)], [G. Maier et al., (2001)] that a permutation can be realized in an n /spl times/ n banyan network with node-disjoint paths in O(n/sup 1/2/) passes. This represents the currently best-known result for the number of passes required for routing an arbitrary permutation with node-disjoint paths in unique-path multistage networks. Unlike other unique path MINs (such as omega networks or banyan networks), only baseline networks have been found to possess such four-pass routing property. We present routing algorithms in both self-routing style and central-controlled style. Different from the recent work in [Y. Yang et al., (2003)], which also gave a four-pass node-disjoint routing algorithm for permutations, the new algorithm is efficient in transmission time for messages of any length, while the algorithm in [Y. Yang et al., (2003)] can work efficiently only for long messages. Comparisons with previous results demonstrate that routing in a baseline network proposed in this paper could be a better choice for routing permutations due to its lowest hardware cost and near-optimal transmission time.     

Performing permutations on interconnection networks by regularlychanging switch states

In this paper, we present an algorithm for performing permutations of messages on multistage interconnection networks. Permutations of messages are needed in many parallel algorithms. The proposed algorithm is feasible for any networks that can connect each input to each output using a set of N nonblocking connections, where N is the number of ports on the network. Messages are segmented into N submessages that are sent independently in each time step. For any permutation, the settings of switches are changed with fixed patterns. Partitioning of the network into independent subnetworks is also supported, each capable of simultaneously routing a different permutation     

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.     

Wang tilings and distributed verification on anonymous torus networks

Considern ² processors arranged in ann × n torus network in which each processor is connected by direct communication channels with its four neighbours. This paper studies the followingverification problem on anonymousn × n torus networks: verify whether the network is oriented; that is, verify whether there is an agreement, among all processors, on a consistent channel labelling. The problem is to be solved by a distributed algorithm executed by the processors themselves. If processors can label their channels arbitrarily, then there are network labellings that are not oriented but, to the processors, are indistinguishable from ones that are oriented. Hence there is no deterministic distributed verification algorithm. However, a verification algorithm does exist if the initial labellings are suitably restricted. We describe the restrictions placed on the initial labellings by subsets of the permutation groupS ₄. We show that the existence of an algorithm for verification is equivalent to the existence of certain tilings of the torus with Wang tiles. Using this equivalence, we have determined the existence of a distributed algorithm for the verification problem for alln × n torus networks for an important class of restrictions, the subgroups ofS ₄.     

A three-stage construction for multiconnection networks

Summary A multiconnection network of size N is a switching network with N inputs and N outputs which realizes multiconnections, i.e., connections between the N inputs and N outputs in such a way that every output is connected to exactly one input, but an input can be connected to an arbitrary number of outputs. That network is complete if it can realize all N ^N multiconnections. This structure generalizes the permutation network. We consider here the design of multiconnection networks by a three-stage Clos network using complete substitution networks as its building cells and we show that the resulting multiconnection network is complete if and only if the cells in the middle stage have size 2. Moreover, we describe the control algorithm for such a network. This leads to the design of cellular multiconnection networks of arbitrary size with a relatively simple control algorithm.     

Coset networks as connectors in parallel processors

An active area of research regarding parallel computer systems deals with the design of interconnection networks. Among all interconnection networks, permutation networks play a special role as all other networks can be constructed using such networks. It was recently shown that many permutation networks reported in the literature are manifestations of coset decompositions of symmetric groups. This result is generalized here to obtain several other previously unknown permutation networks which satisfy such decompositions. In addition, analyses of the edge-count, propagation delay, fan-out, and setup time of such networks are provided. The results lead to some anomolous behavior as well as several trade-offs among these parameters. For example, it is shown that a complete bipartite graph is the fastest and most economical direct realization of a permutation network. Furthermore, it is shown that the fan-out of a network is inversely proportional to the propagation delay whereas the setup time may or may not relate to the propagation delay at all depending on the network in question. Finally, two constant fan-out implementations of these networks using O (n ^1.59) 2 × 1 multiplexers and 2 × 2 switches are presented.This work is supported in part by the National Science Foundation under Grant No: CCR-8708864.     

The Cayley network of expanded Pancake graphs

Signed permutation group has important applications in genome rearrangement as well as the construction of networks. In this paper, we propose a new interconnection network named extended Pancake graph, we investigate its topological properties, and give a routing algorithm with the diameter upper bounded by 2n?1. Some embedding properties are also derived. In conclusion, we present a comparison of some familiar networks with the Cayley graph EP _n .     

Parallel algorithms for routing in nonblocking networks

We construct nonblocking networks that are efficient not only as regards their cost and delay, but also as regards the time and space required to control them. In this paper we present the first simultaneous weakly optimal solutions for the explicit construction of nonblocking networks, the design of algorithms and data-structures. Weakly optimal is in the sense that all measures of complexity (size and depth of the network, time for the algorithm, space for the data-structure, and number of processor-time product) are within one or more logarithmic factors of their smallest possible values. In fact, we construct a scheme in which networks withn inputs andn outputs have sizeO(n(logn)²) and depthO(logn), and we present deterministic and randomized on-line parallel algorithms to establish and abolish routes dynamically in these networks. In particular, the deterministic algorithm usesO((logn)⁵) steps to process any number of transactions in parallel (with one processor per transaction), maintaining a data structure that useO(n(logn)²) words.     

Fast Generation of Random Permutations Via Networks Simulation

We consider the problem of generating random permutations with uniform distribution. That is, we require that for an arbitrary permutation π of n elements, with probability 1/n! the machine halts with the i th output cell containing π(i) , for 1 ≤ i ≤ n . We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM. The main result of the paper is an algorithm for generating random permutations that runs in O(log log n) time and uses O(n ^1+o(1) ) processors on the CREW PRAM. This is the first o(log n) -time CREW PRAM algorithm for this problem. On the EREW PRAM we present a simple algorithm that generates a random permutation in time O(log n) using n processors and O(n) space. This algorithm outperforms each of the previously known algorithms for the exclusive write PRAMs. The common and novel feature of both our algorithms is first to design a suitable random switching network generating a permutation and then to simulate this network on the PRAM model in a fast way. Received November 1996; revised March 1997.     

Using the dual path property of omega networks to obtainconflict-free message routing

A strategy for dealing with communication conflicts that occur in omega networks is presented. The strategy operates by implementing the dual path property of omega networks, which allows the source and destination processors to reverse roles for some of the messages that are being transmitted. For certain message patterns, such a reversal produces a modified message pattern for which the network routes are disjoint. For a circuit switching mode in which the network links and switches are bidirectional, the disjoint set of routes for modified message pattern can be used to achieve conflict-free message transmission for the original message pattern. This strategy is investigated, and an efficient algorithm to determine whether it can be successfully applied to a given message pattern is presented     

Energy efficient routing algorithm for fiber-wireless access networks: A network formation game approach

New multimedia services and ubiquitous networking pose great challenges on existing access network infrastructures. To cope with such requirements new access technologies, such as the fiber-wireless (FiWi), are being developed. Together with the emergence of new access networks, efforts are being made to reduce the amount of energy required to provide services. Indeed, this issue plays an increasingly important role. Here we propose an energy efficient routing algorithm for FiWi access networks. The main idea is to exploit the multipath capabilities of the wireless mesh front end of FiWi access networks to create energy efficient routes that optimize the sleeping and active periods of all ONUs and wireless nodes. To achieve this goal, an energy efficient network model based on network formation game theory is used. This model allows several network formation processes to be compared in regard to the energy efficiency of the routes they generate. Our results reveal that the farsighted network formation process establishes the most energy efficient routes, meaning that the choices done by this formation process were the best ones. However, this farsighted process is computationally expensive. For this reason a heuristic algorithm is developed, which explores the most energy efficient choices taken by the network formation processes, and farsighted process in particular. Results show that the proposed heuristic is able to obtain results close to the farsighted process.     

Efficient Parallel Algorithms for Permutation Graphs

In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs.     

O(n) routing in rearrangeable networks

In (2n−1)-stage rearrangeable networks, the routing time for any arbitrary permutation is Ω(n²) compared to its propagation delay O(n) only. Here, we attempt to identify the sets of permutations, which are routable in O(n) time in these networks. We define four classes of self-routable permutations for Benes network. An O(n) algorithm is presented here, that identifies if any permutation P belongs to one of the proposed self-routable classes, and if yes, it also generates the necessary control vectors for routing P. Therefore, the identification, as well as the switch setting, both problems are resolved in O(n) time by this algorithm. It covers all the permutations that are self-routable by anyone of the proposed techniques. Some interesting relationships are also explored among these four classes of permutations, by applying the concept of ‘group-transformations’ [N. Das, B.B. Bhattacharya, J. Dattagupta, Hierarchical classification of permutation classes in multistage interconnection networks, IEEE Trans. Comput. (1993) 665–677] on these permutations. The concepts developed here for Benes network, can easily be extended to a class of (2n−1)-stage networks, which are topologically equivalent to Benes network. As a result, the set of permutations routable in a (2n−1)-stage rearrangeable network, in a time comparable to its propagation delay has been extended to a large extent.     

Bulk Synchronous Parallel Algorithms for the External Memory Model

Abstract. Blockwise access to data is a central theme in the design of efficient external memory (EM) algorithms. A second important issue, when more than one disk is present, is fully parallel disk I/ O. In this paper we present a simple, deterministic simulation technique which transforms certain Bulk Synchronous Parallel (BSP) algorithms into efficient parallel EM algorithms. It optimizes blockwise data access and parallel disk I/ O and, at the same time, utilizes multiple processors connected via a communication network or shared memory. We obtain new improved parallel EM algorithms for a large number of problems including sorting, permutation, matrix transpose, several geometric and GIS problems including three-dimensional convex hulls (two-dimensional Voronoi diagrams), and various graph problems. We show that certain parallel algorithms known for the BSP model can be used to obtain EM algorithms that meet well known I /O complexity lower bounds for various problems, including sorting.     

Deterministic broadcasting in ad hoc radio networks

We consider the problem of distributed deterministic broadcasting in radio networks of unknown topology and size. The network is synchronous. If a node u can be reached from two nodes which send messages in the same round, none of the messages is received by u. Such messages block each other and node u either hears the noise of interference of messages, enabling it to detect a collision, or does not hear anything at all, depending on the model. We assume that nodes know neither the topology nor the size of the network, nor even their immediate neighborhood. The initial knowledge of every node is limited to its own label. Such networks are called ad hoc multi-hop networks. We study the time of deterministic broadcasting under this scenario. For the model without collision detection, we develop a linear-time broadcasting algorithm for symmetric graphs, which is optimal, and an algorithm for arbitrary n-node graphs, working in time . Next we show that broadcasting with acknowledgement is not possible in this model at all. For the model with collision detection, we develop efficient algorithms for broadcasting and for acknowledged broadcasting in strongly connected graphs. Received: January 2000 / Accepted: June 2001     

Efficient routing and sorting schemes for de Bruijn networks

We consider the problems of routing and sorting on a de Bruijn network. First, we show that any deterministic oblivious routing scheme for permutation routing on a d-ary de Bruijn network with N=dⁿ nodes, in the worst case, will take Ω(√N) steps under the single-port model. This improves the existing lower bounds provided d is not a constant. We also show that the lower bound is indeed a tight one. Second, we present a deterministic nonoblivious permutation routing algorithm which runs in O(d.n²) time on a d-ary de Bruijn network with N=dⁿ nodes. This algorithm is currently the fastest known nonoblivious deterministic routing algorithm for de Bruijn networks of arbitrary degree. Finally, we present an efficient general sorting algorithm for the de Bruijn networks of arbitrary degree. This algorithm is the best sorting algorithm known so far. It runs in O((log d).d.n²) time for directed de Bruijn network with dⁿ nodes, degree d, and diameter n. As a corollary, we show that on a binary de Bruijn network of Nnodes, our sorting scheme requires at most 2 log² Nsteps     

Massive MIMD neural network simulations: The connections dilemma

We present two strategies for the simulation of massive neural networks on message-passing MIMD machines. In the first strategy all interconnections between neurons are stored explicitly in interconnection matrices. During simulation, every processor is responsible for certain submatrices of these interconnection matrices. The fact that message-passing MIMD processors do not provide virtual memory seriously limits the size of the networks that can be simulated, since interconnection matrices require huge amounts of memory. An alternative strategy is not to store the connections explicitly, but generate the interconnections as they are needed. This circumvents memory limitations, but because interconnections need to be generated multiple times, it is inherently slower than the first implementation. This yields the connections dilemma: the choice between fast simulation of small networks as against slower simulation of massive networks. We present, analyze and bench-mark parallel implementations for both strategies. An efficient connection-look-up algorithm, which can be used for any network with static interconnections, ensures that simulation times for the second strategy are only marginally longer than for the first strategy. We show that for our users the connections dilemma is no longer a dilemma: by means of our look-up algorithm the simulation of massive networks becomes possible; furthermore the time to design and construct a network, prior to simulation, is considerably shorter than it is for the matrix version, and in addition this time is independent of network size. Although we have implemented both strategies on a parallel computer, the algorithms presented here can be used on any machine with memory limitations, such as personal computers.     

Design and analysis of a multi-candidate selection scheme for greedy routing in wireless sensor networks

Sleep and wake-up scheduling of sensor nodes is an efficient solution to prolong the network lifetime. However, existing scheduling algorithms may significantly decrease the number of active nodes so that the network may be intermittently connected. In such networks, traditional geographic routing protocols are inappropriate to obtain low latency routes due to route discovery and data forwarding latency. In this paper, we propose a novel multi-candidate selection (MCS) scheme for greedy routing that makes the best effort to find minimum latency routes in the sensor networks. In MCS, each source node sends an RREQ to a list of first wake-up forwarder candidates and selects a route with minimum estimated delivery latency based on their replies. The route found by MCS may be longer than that of distance-based greedy forwarding (DGF) (Finn, 1987). Hence, we introduce a latency-adaptive distance-based multi-candidate selection scheme for greedy forwarding to find routes with a small number of hops and acceptable delivery latency. Probabilistic analysis and simulation results demonstrate that MCS increases the routing performance significantly compared with DGF and ODML (Su et al., 2008) in terms of delivery latency.