Broadcast-efficient protocols for mobile radio networks

The main contribution of this work is to present elegant broadcast-efficient protocols for permutation routing, ranking, and sorting on single-hop Mobile Radio Networks with p stations and k radio channels, denoted by MRN(p,k). Clearly, any protocol performing these tasks on n items must perform ⁿ/_k broadcast rounds because each item must be broadcast at least once. We begin by presenting an optimal off-line permutation routing protocol using ⁿ /_k broadcast rounds for arbitrary k, p, and n. Further, we show that optimal on-line routing can be performed in ⁿ/ _k broadcast rounds, provided that either k=1 or p=n. We then go on to develop an online routing protocol that takes 2ⁿ/ _k+k-1 broadcast rounds on the MRN(p,k), whenever k⩽√^p/₂. Using these routing protocols as basic building blocks, we develop a ranking protocol that takes 2ⁿ /_k+o(ⁿ/_k) broadcast rounds as well as a sorting protocol that takes 3ⁿ/_k+o(ⁿ/_k) broadcast rounds, provided that k ϵ o(√n) and p=n. Finally, we develop a ranking protocol that takes 3ⁿ/_k+o(ⁿ/ _k) broadcast rounds, as well as a sorting protocol that takes 4ⁿ/_k+o(ⁿ/_k) broadcast rounds on the MRN(p,k), provided that k⩽√^p/₂ and p ϵ o(n). Featuring very low proportionality constants, our protocols offer a vast improvement over the state of the art     

Two packet routing algorithms on a mesh-connected computer

We give two algorithms for the 1-1 routing problems on a mesh-connected computer. The first algorithm, with queue size 28, solves the 1-1 routing problem on an n×n mesh-connected computer in 2n+O(1) steps. This improves the previous queue size of 75. The second algorithm solves the 1-1 routing problem in 2n-2 steps with queue size 12 t_s/s where t_s is the time for sorting an s×s mesh into a row major order for all s⩾1. This result improves the previous queue size 18.67 t_s/s     

基于增量计算的信息系统属性粒结构计算方法

针对不可分离信息系统的属性粒结构计算问题,提出一种利用分治和增量计算相结合的计算方法。首先,研究了在信息系统函数依赖集上增加新的函数依赖(FD)后,信息系统属性粒结构的变化规律,证明了信息系统结构增量定理;其次,通过移除部分函数依赖,使不可分离信息系统成为可分离信息系统,利用分解定理计算出可分离信息系统结构;然后,将移除的函数依赖加入可分离信息系统,利用增量定理计算出原信息系统结构;最后,给出了计算不可分离信息系统属性粒结构的算法,分析了算法复杂度。与直接计算不可分离信息系统的粒结构相比,该计算方法可将计算复杂度从O(n×m×2ⁿ)降低到小于O(n×k×2ⁿ)(k1×m₁×2^n₁)+O(n₂×m₂×2^n₂)(n=n₁+n₂,m=m₁+m₂)。理论分析和实例计算表明,所提方法能有效降低不可分离信息系统属性粒结构的计算复杂度。     

A period-processor-time-minimal schedule for cubical meshalgorithms

Using a directed acyclic graph (dag) model of algorithms, we investigate precedence-constrained multiprocessor schedules for the n×n×n directed mesh. This cubical mesh is fundamental, representing the standard algorithm for square matrix product, as well as many other algorithms. Its completion requires at least 3^n-2 multiprocessor steps. Time-minimal multiprocessor schedules that use as few processors as possible are called processor-time-minimal. For the cubical mesh, such a schedule requires at least [3n²/4] processors. Among such schedules, one with the minimum period (i.e., maximum throughput) is referred to as a period-processor-time-minimal schedule. The period of any processor-time-minimal schedule for the cubical mesh is at least 3^n/2 steps. This lower bound is shown to be exact by constructing, for n a multiple of 6, a period-processor-time-minimal multiprocessor schedule that can be realized on a systolic array whose topology is a toroidally connected n/2×n/2×3 mesh     

Õ(Congestion + Dilation) Hot-Potato Routing on Leveled Networks

We study packet routing problems, in which we are given a set of N packets which will be sent on preselected paths with congestion C and dilation D. For store-and-forward routing, in which nodes have buffers for packets in transit, there are routing algorithms with a performance that matches the lower bound Ω(C+D). Motivated from optical networks, we study hot-potato routing in which the nodes are bufferless. Due to the lack of buffers, in hot-potato routing the packets may be delayed more than in store-and-forward routing. An interesting question is how much is the performance of routing algorithms affected by the absence of buffers. Here, we answer this question for the class of leveled networks, in which the nodes are partitioned into L+1 distinct levels. We present a randomized hot-potato routing algorithm for leveled networks, which routes the packets in O((C + L) ln⁹ (LN)) time with high probability. For routing problems with dilation Ω(L), and where N is a polynonial in L, this bound is within polylogarithmic factors of the lower bound Ω(C+L). Our algorithm demonstrates that for such routing problems the benefit from using buffers is no more than polylogarithmic; thus, hot-potato routing is an efficient way to route packets in leveled networks. In hot-potato routing, due to the lack of buffers, the packets may not be able to remain on their preselected paths during the course of routing (while in store-and-forward routing the packets remain on their preselected paths). However, in our algorithm the actual path that each packet follows contains its original preselected path; thus the lower bound Ω(C+L) is also a lower bound for the new paths. Our algorithm is distributed, that is, routing decisions are taken locally at each node while packets are routed in the network. To our knowledge, this is the first hot-potato algorithm designed and analyzed, in terms of congestion and dilation, for leveled networks.     

Work-efficient routing algorithms for rearrangeable symmetricalnetworks

The work performed by a parallel algorithm is the product of its running time and the number of processors it requires. This paper presents work-efficient (or cost-optimal) routing algorithms to determine the switch settings for realizing permutations on rearrangeable symmetrical networks such as Benes and the reduced Ω _NΩ_N^-1. These networks have 2n-1 stages with N=2ⁿ inputs/outputs, each stage consisting of N/2 crossbar switches of size (2×2). Previously known parallel routing algorithms for a rearrangeable network with N inputs determine the states of all switches recursively in O(n) iterations using N processors. Each iteration determines the switch settings of at most two stages of the network and requires at least O(n) time on a computer of N processors, regardless of the type of its interconnection network. Hence, the work of any previously known parallel routing algorithm equals at least O(Nn²) for setting up all the switches of a rearrangeable network. The new routing algorithms run on a computer of p processors, 1⩽p⩽N/n, and perform work O(Nn). Moreover, because the range of p is large, the new routing algorithms do not have to be changed in case some processors become faulty     

A fast parallel algorithm for routing unicast assignments in Benesnetworks

This paper presents a new parallel algorithm for routing unicast (one-to-one) assignments in Benes networks. Parallel routing algorithms for such networks were reported earlier, but these algorithms were designed primarily to route permutation assignments. The routing algorithm presented in this paper removes this restriction without an increase in the order of routing cost or routing time. We realize this new routing algorithm on two different topologies. The algorithm routes a unicast assignment involving O(k) pairs of inputs and outputs in O(lg ² k+lg n) time on a completely connected network of n processors and in O(lg⁴ k+lg² k lg n) time on an extended shuffle-exchange network of n processors. Using O(n lg n) professors, the same algorithm can be pipelined to route α unicast assignments each involving O(k) pairs of inputs and outputs, in O(lg² k+lg n+(α-1) lg k) time on a completely connected network and in O(lg⁴ k+lg² k lg n+(α-1)(lg ³ k+lg k lg n)) time on the extended shuffle-exchange network. These yield an average routing time of O(lg k) in the first case, and O(lg³ k+1g k lg n) in the second case, for all α⩾lg n. These complexities indicate that the algorithm given in this paper is as fast as Nassimi and Sahni's algorithm for unicast assignments, and with pipelining, it is faster than the same algorithm at least by a factor of O(lg n) on both topologies. Furthermore, for sparse assignments, i.e., when k=O(1), it is the first algorithm which has an average routing time of O(1g n) on a topology with O(n) links     

Optimal Deterministic Sorting and Routing on Grids and Tori with Diagonals

We present deterministic sorting and routing algorithms for grids and tori with additional diagonal connections. For large loads ( ), where each processor has at most h data packets in the beginning and in the end, the sorting problem can be solved in optimal hn/6+o(n) and hn/12+o(n) steps for grids and tori with diagonals, respectively. For smaller loads, we present a new concentration technique that yields very fast algorithms for h<12 . For a load of 1, the previously most studied case, sorting only takes 1.2n+o(n) steps and routing only 1.1n+o(n) steps. For tori, we can present optimal algorithms for all loads . The above algorithms all use a constant-size memory for all processors and never copy or split packets, a property that the corresponding lower bounds make use of. If packets may be copied, 1—1 sorting can be done in only 2n/3+o(n) on a torus with diagonals. Generally gaining a speedup of 3 by only doubling the number of communication links compared with a grid without diagonals, our work suggests building grids and tori with diagonals. Received August 18, 1997; revised December 28, 1997.     

An O((log log n)2) time algorithm to compute the convexhull of sorted points on reconfigurable meshes

The problem of computing the convex hull of a set of n sorted points in the plane is one of the fundamental tasks in image processing, pattern recognition, cellular network design, and robotics, among many others. Somewhat surprisingly, in spite of a great deal of effort, the best previously known algorithm to solve this problem on a reconfigurable mesh of size √n×√n was running in O(log2 n) time. It was open for more than ten years to obtain an algorithm for this important problem running in sublogarithmic time. Our main contribution is to provide the first breakthrough: we propose an almost optimal convex hull algorithm running in O((log log n)²) time on a reconfigurable mesh of size √n×√n. With slight modifications, this algorithm can be implemented to run in O((log log n)²) time on a reconfigurable mesh of size √n/loglogn×√n/loglogn. Clearly, the latter algorithm is work-optimal. We also show that any algorithm that computes the convex hull of a set of n sorted points on an n-processor reconfigurable mesh must take Ω(log log n) time. Our result opens the door to an entire slew of efficient convex-hull-based algorithms on reconfigurable meshes     

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     

Constructing Euclidean minimum spanning trees and all nearestneighbors on reconfigurable meshes

A reconfigurable mesh, R-mesh for short, is a two-dimensional array of processors connected by a grid-shaped reconfigurable bus system. Each processor has four I/O ports that can be locally connected during execution of algorithms. This paper considers the d-dimensional Euclidean minimum spanning tree (EMST) and the all nearest neighbors (ANN) problem. Two results are reported. First, we show that a minimum spanning tree of n points in a fixed d-dimensional space can be constructed in O(1) time on a √(n³)×√(n³) R-mesh. Second, all nearest neighbors of n points in a fixed d-dimensional space can be constructed in O(1) time on an n×n R-mesh. There is no previous O(1) time algorithm for the EMST problem; ours is the first such algorithm. A previous R-mesh algorithm exists for the two-dimensional ANN problem; we extend it to any d-dimensional space. Both of the proposed algorithms have a time complexity independent of n but growing with d. The time complexity is O(1) if d is a constant     

Packet routing on grids of processors

The problem of routing packets onn ₁×...×n _r mesh-connected arrays or grids of processors is studied. The focus of this paper is on permutation routing where each processor contains exactly one packet initially and finally. A slight modification of permutation routing called balanced routing is also discussed. For two-dimensional grids a determinisitc routing algorithm is given forn×n meshes where each processor has a buffer of size f(n) < n. It needs 2n + O(n/f(n)) steps on grids without wrap-arounds. Hence, it is asymptoticaliy nearly optimal, and as good as randomized algorithms routing data only with high probability. Furthermore, it is demonstrated that onr-dimensional cubes of processors permutation routing can be performed asymptotically by (2r–2)n steps, which is faster than the running times of so-far known randomized algorithms and of deterministic algorithms.Partially supported by Siemens AG, München.     

Optimal broadcast in all-port wormhole-routed hypercubes

We give an optimal algorithm that broadcasts on an n-dimensional hypercube in O(n/ log₂ (n+1)) routing steps with wormhole, e-cube routing and all-port communication. Previously, the best algorithm of P.K. McKinley and C. Trefftz (1993) requires [n/2] routing steps. We also give routing algorithms that achieve tight time bounds for n ⩽7     

Solving fundamental problems on sparse-meshes

A sparse-mesh, which has PUs on the diagonal of a two-dimensional grid only, is a cost effective distributed memory machine. Variants of this machine have been considered before, but none are as simple and pure as a sparse-mesh. Various fundamental problems (routing, sorting, list ranking) are analyzed, proving that sparse-meshes have great potential. It is shown that on a two-dimensional n×n sparse-mesh, which has n PUs, for h=ω(n^ϵ·log n), h-relations can be routed in (h+o(h))/ϵ steps. The results are extended for higher dimensional sparse-meshes. On a d-dimensional n x···x n sparse-mesh, with h=ω(n^ϵ ·log n), h-relations are routed in (6·(d-1)/ϵ-4)·(h+o(h)) steps     

Parallel display of objects represented by linear octrees

The storage, display, and manipulation of three dimensional volumetric information requires large amounts of computing resources, both in terms of memory, and processing power. Most existing serial algorithms that display 3-D objects on a 2-D screen are found to be too slow to process the large amounts of volume data in a reasonable time. Hence, one way to increase the performance of the display algorithm is to process individual volume elements (voxels) in parallel. The first part of this paper presents a brief over view of the linear octree data structure which represents 3-D objects by an eight-way branching tree, while the second part focusses on the parallel display of such objects. We have shown that, for an object represented by a linear octree and enclosed in a 2ⁿ×2ⁿ×2ⁿ universe, the maximum number of voxels that can be processed in parallel is 3ⁿ, and the maximum number of time steps required to display such an object is 4ⁿ. This paper presents a set of formulae which identify the processing element (PE) as well as the time step in which a given linear octree node is processed. Similarly, a procedure which determines the locational code of a linear octree node which must be processed by a given PE, at some specific time step, is presented, along with a strategy for determining whether a PE is active or idle     

Sorting n2 numbers on n×n meshes

We show that by folding data from an n×n mesh onto an n×(n/k) submesh, sorting on the submesh, and finally unfolding back onto the entire n×n mesh it is possible to sort on bidirectional and strict unidirectional meshes using a number of routing steps that is very close to the distance lower bound for these architectures     

Square meshes are not optimal for convex hull computation

Recently it has been noticed that for semigroup computations and for selection, rectangular meshes with multiple broadcasting yield faster algorithms than their square counterparts. The contribution of the paper is to provide yet another example of a fundamental problem for which this phenomenon occurs. Specifically, we show that the problem of computing the convex hull of a set of n sorted points in the plane can be solved in O(n^1/8 log ^3/4) time on a rectangular mesh with multiple broadcasting of size n^3/8 log^1/4 n×n^5/8/log^1/4n. The fastest previously known algorithms on a square mesh of size √n×√n run in O(n^1/6) time in case the n points are pixels in a binary image, and in O(n^1/6log^3/2 n) time for sorted points in the plane     

Potential Function Analysis of Greedy Hot-Potato Routing

We study the problem of packet routing in synchronous networks. We put forward a notion of greedy hot-potato routing algorithms and devise tech- niques for analyzing such algorithms. A greedy hot-potato routing algorithm is one where: • The processors have no buffer space for storing delayed packets. Therefore, each packet must leave any intermediate processor at the step following its arrival. • Packets always advance toward their destination if they can. Namely, a packet must leave its current intermediate node via a link which takes it closer to its destination, unless all these links are taken by other packets. Moreover, in this case all these other packets must advance toward their destinations. We use potential function analysis to obtain an upper bound of O(n k ^1/2 ) on the running time of a wide class of algorithms in the two-dimensional n × n mesh, for routing problems with a total of k packets. The same techniques can be generalized to obtain an upper bound of O(exp(d) n ^d-1 k ^1/d ) on the running time of a wide class of algorithms in the d -dimensional n ^d mesh, for routing problems with a total of k packets. Received December 1993, and in final form March 1997.     

An optimal algorithm for the angle-restricted all nearest neighborproblem on the reconfigurable mesh, with applications

Given a set S of n points in the plane and two directions r₁ and r₂, the Angle-Restricted All Nearest Neighbor problem (ARANN, for short) asks to compute, for every point p in S, the nearest point in S lying in the planar region bounded by two rays in the directions r₁ and r₂ emanating from p. The ARANN problem generalizes the well-known ANN problem and finds applications to pattern recognition, image processing, and computational morphology. Our main contribution is to present an algorithm that solves an instance of size n of the ARANN problem in O(1) time on a reconfigurable mesh of size n×n. Our algorithm is optimal in the sense that Ω(n²) processors are necessary to solve the ARANN problem in O(1) time. By using our ARANN algorithm, we can provide O(1) time solutions to the tasks of constructing the Geographic Neighborhood Graph and the Relative Neighborhood Graph of n points in the plane on a reconfigurable mesh of size n×n. We also show that, on a somewhat stronger reconfigurable mesh of size n×n², the Euclidean Minimum Spanning Tree of n points can be computed in O(1) time     

2D Mesh片上网络分区容错路由算法

为了减小路由表的规模且避免使用较多虚通道(VC),从而降低硬件资源用量,针对虫孔交换的2D Mesh片上网络提出了一种分区容错路由(RFTR)算法。该算法根据故障节点和链路的位置将2D Mesh网络划分为若干个相连的矩形区域,数据包在矩形区域内可使用确定性或自适应路由算法进行路由,而在区域间则按照up^*/down^*算法确定路由路径。此外,利用通道依赖图(CDG)模型,证明了该算法仅需两个虚通道就能避免死锁。在6×6 Mesh网络中,RFTR算法能减少25%的路由表资源用量。仿真结果表明,在队列缓存资源相同的情况下,RFTR算法能实现与up^*/down^*算法和segment算法相当甚至更优的性能。