International Parallel and Distributed Processing Symposium (IPDPS'03) Routing on Meshes in Optimum Time and with Really Small Queues Nice, France April 22-April 26 ISBN: 0-7695-1926-1
We consider permutation routing problems on 2D and 3D mesh-connected computers with side lenth n. Our main result is a deterministic on-line algorithm routing on 2D meshes, operating in worst-case time T = 2n + O(1) and with queue size Q = 3. We also develop off-line routing algorithms with performance bounds T = 2n + O(1) and with queue size Q = 3. We also develop off-line routing algorithms with performance bounds T = 2n - 1 and Q = 2 for 2D meshes, and T = 3n - 2 and Q = 4 for 3D meshes. We also show that is it possible to route most of the permutations on 2D meshes off-line in time T = 2n - 2 with Q = 1.
Citation:
Bogdan S. Chlebus, Jop F. Sibeyn, "Routing on Meshes in Optimum Time and with Really Small Queues," ipdps, pp.56a, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb