Improved bounds for routing and sorting on multi-dimensional meshes

Torsten Suel

doi:10.1145/181014.181022

Improved bounds for routing and sorting on multi-dimensional meshes

Torsten Suel

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
Publisher	Association for Computing Machinery, Inc
Pages	26-35
Number of pages	10
ISBN (Electronic)	0897916719, 9780897916714
DOIs	https://doi.org/10.1145/181014.181022
State	Published - Aug 1 1994
Event	6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994 - Cape May, United States Duration: Jun 27 1994 → Jun 29 1994

Publication series

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

Other

Other	6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
Country/Territory	United States
City	Cape May
Period	6/27/94 → 6/29/94

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture

Access to Document

10.1145/181014.181022

Cite this

Suel, T. (1994). Improved bounds for routing and sorting on multi-dimensional meshes. In Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994 (pp. 26-35). (Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994). Association for Computing Machinery, Inc. https://doi.org/10.1145/181014.181022

Improved bounds for routing and sorting on multi-dimensional meshes. / Suel, Torsten.
Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994. Association for Computing Machinery, Inc, 1994. p. 26-35 (Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Suel, T 1994, Improved bounds for routing and sorting on multi-dimensional meshes. in Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994. Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994, Association for Computing Machinery, Inc, pp. 26-35, 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994, Cape May, United States, 6/27/94. https://doi.org/10.1145/181014.181022

@inproceedings{ad9f89c2222c41b3b23a1a271e6e0aaa,

title = "Improved bounds for routing and sorting on multi-dimensional meshes",

abstract = "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.",

author = "Torsten Suel",

note = "Publisher Copyright: {\textcopyright} 1994 ACM.; 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994 ; Conference date: 27-06-1994 Through 29-06-1994",

year = "1994",

month = aug,

day = "1",

doi = "10.1145/181014.181022",

language = "English (US)",

series = "Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994",

publisher = "Association for Computing Machinery, Inc",

pages = "26--35",

booktitle = "Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994",

}

TY - GEN

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

AU - Suel, Torsten

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 -

Improved bounds for routing and sorting on multi-dimensional meshes

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this