scientific article; zbMATH DE number 4049037

From MaRDI portal
Publication:3785933





[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\).











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)