scientific article; zbMATH DE number 4049037
[For the entire collection see Zbl 0625.00019.] We present an optimal oblivious randomized algorithm for permutation routing on the MIMD version of mesh. Our routing algorithm routes \(n^ 2\) elements on an \(n\times n\) mesh in \(2n+O(\log n)\) parallel communication steps with very high probability. Further, the maximum queue length at any node at any time is at the most O(log n) with the same probability. Since 2n is the distance bound for the mesh, our algorithm is indeed optimal. Generalization of this result to k- dimensional (for any k) meshes yields an algorithm that runs in time equal to the diameter of the mesh. A lower bound result by \textit{C. P. Schnoor} and \textit{A. Shamir} [``An optimal sorting algorithm for mesh connected computers, Proc. ACM Symp. Theory Computing, 1986] states that sorting of \(n^ 2\) elements takes at least 3n steps on an \(n\times n\) MIMD mesh (for indexing schemes of practical interest). Thus our algorithm demonstrates that routing is easier than sorting on the MIMD mesh. We also identify a class of mesh-like networks (we call circular meshes) which have \(n^ 2\) nodes but less than 2n diameter. These meshes have the property that they can be laid out on a chip with a physical diameter same as the model diameter. Our routing algorithm runs on these networks to route \(n^ 2\) elements in \(d+O(\log n)\) steps (d being the diameter of the network) with a very high probability. These circular meshes also have the potential of being adopted to run existing sorting and routing algorithms (on the regular SIMD and MIMD meshes) with a corresponding reduction in their run times. And finally we present a (possibly) non optimal oblivious routing algorithm for the mesh that requires only O(1) queue size for any node at any time. In particular we present a randomized oblivious constant queue size routing algorithm that runs in time \(O(n^{1+\epsilon})\), for any \(\epsilon >0\).
- Optimal routing algorithms for mesh-connected processor arrays
- Mesh permutation routing with locality
- Constant queue routing on a mesh
- Packet Routing on grids of processors
- An optimal distributed algorithm for recognizing mesh-connected networks
- Packet routing and PRAM emulation on star graphs and leveled networks
- New bounds for oblivious mesh routing
- scientific article; zbMATH DE number 1003300 (Why is no real title available?)
- Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
- Constant queue routing on a mesh
- Efficient randomized routing algorithms on the two-dimensional mesh of buses
- Randomized Routing and Sorting on Fixed-Connection Networks
- Robust algorithms for packet routing in a mesh
- Diagonal and toroidal mesh networks
- k-k Routing, k-k Sorting, and Cut-Through Routing on the Mesh
- scientific article; zbMATH DE number 1419213 (Why is no real title available?)
- Optimal multi-packet routing on the torus
- Shorter queues for permutation routing on meshes
- Randomized Throughput-Optimal Oblivious Routing for Torus Networks
- Algorithms – ESA 2005
- Efficient randomized routing algorithms on the two-dimensional mesh of buses
- Randomized multipacket routing and sorting on meshes
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3785933)