TY - GEN

T1 - Improved bounds for routing and sorting on multi-dimensional meshes

AU - Suel, Torsten

N1 - Funding Information:
“Email: torstenQcs .ut*xax. edu. Supported by the Texas Advanced Research Program under Grant Nos. 00365S-4S0 and 00365S-461, and by a Schlumberger Graduate Fellowship.

PY - 1994/8/1

Y1 - 1994/8/1

N2 - We show improved bounds for 1-1 routing and sorting on multi-dimensional meshes and tori. In particular, we give a fairly simple deterministic algorithm for sorting on the (/-dimensional mesh of side length n that achieves a running time of 3dn/2+o(n) without making any copies of the elements. We give deterministic algorithms with running times of 5dn/4 + o(n) and Zdn/4 + o(n) for the d-dimensional mesh and torus, respectively, that make one copy of each element. We also show lower bounds for sorting with respect to a large class of indexing schemes, under a model of the mesh where each processor can hold an arbitrary number of packets. Finally, we describe algorithms for permutation routing whose running times come very close to the diameter lower bound.

AB - We show improved bounds for 1-1 routing and sorting on multi-dimensional meshes and tori. In particular, we give a fairly simple deterministic algorithm for sorting on the (/-dimensional mesh of side length n that achieves a running time of 3dn/2+o(n) without making any copies of the elements. We give deterministic algorithms with running times of 5dn/4 + o(n) and Zdn/4 + o(n) for the d-dimensional mesh and torus, respectively, that make one copy of each element. We also show lower bounds for sorting with respect to a large class of indexing schemes, under a model of the mesh where each processor can hold an arbitrary number of packets. Finally, we describe algorithms for permutation routing whose running times come very close to the diameter lower bound.

UR - http://www.scopus.com/inward/record.url?scp=0039755757&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0039755757&partnerID=8YFLogxK

U2 - 10.1145/181014.181022

DO - 10.1145/181014.181022

M3 - Conference contribution

AN - SCOPUS:0039755757

T3 - Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994

SP - 26

EP - 35

BT - Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994

PB - Association for Computing Machinery, Inc

T2 - 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994

Y2 - 27 June 1994 through 29 June 1994

ER -