Time lower bounds for parallel sorting on a mesh-connected processor array (Q1112618): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q329621 |
||
Property / reviewed by | |||
Property / reviewed by: Yanchang Han / rank | |||
Revision as of 02:58, 13 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Time lower bounds for parallel sorting on a mesh-connected processor array |
scientific article |
Statements
Time lower bounds for parallel sorting on a mesh-connected processor array (English)
0 references
1989
0 references
We prove that \((1+\sqrt{6}/2)n\approx 2.22 n\) is a time lower bound independent of indexing schemes for sorting \(n^ 2\) items on an \(n\times n\) mesh-connected processor array. We distinguish between indexing schemes by showing that there exists an indexing scheme which is provably worse than a snake-like row-major indexing for sorting. We also derive lower bounds for various indexing schemes. All these results are obtained by using the chain argument which we provide in this paper.
0 references
time lower bound
0 references
sorting
0 references
mesh-connected processor array
0 references
indexing schemes
0 references
chain argument
0 references
parallel algorithm
0 references