TY - GEN
T1 - Duplicating keys to streamline sorting on a mesh-connected computer
AU - Chlebus, B. S.
PY - 1991/1/1
Y1 - 1991/1/1
N2 - Introduces a model of a mesh-connected computer in which multiple-key packets can be exchanged between processors in single routing steps. The author develops a sorting algorithm for such an enhanced model, which has time performance better than optimal algorithms in the traditional model. The technical contributions of this paper are as follows. The first is a new 5n-o(n) lower bound for sorting in a row-major ordering. This improves the best previously known bound of 4n-4. The second contribution is a new sorting algorithm utilizing multiple-packet routing capabilities. The time complexity of this algorithm, measured in the number of concurrent routing steps, can be arbitrarily close to the absolute distance lower bound of 2n-2, provided the number of keys that fit in one routing packet is sufficiently large.
AB - Introduces a model of a mesh-connected computer in which multiple-key packets can be exchanged between processors in single routing steps. The author develops a sorting algorithm for such an enhanced model, which has time performance better than optimal algorithms in the traditional model. The technical contributions of this paper are as follows. The first is a new 5n-o(n) lower bound for sorting in a row-major ordering. This improves the best previously known bound of 4n-4. The second contribution is a new sorting algorithm utilizing multiple-packet routing capabilities. The time complexity of this algorithm, measured in the number of concurrent routing steps, can be arbitrarily close to the absolute distance lower bound of 2n-2, provided the number of keys that fit in one routing packet is sufficiently large.
UR - http://www.scopus.com/inward/record.url?scp=3042876690&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=3042876690&partnerID=8YFLogxK
U2 - 10.1109/SPDP.1991.218266
DO - 10.1109/SPDP.1991.218266
M3 - Conference contribution
T3 - Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing 1991
SP - 296
EP - 300
BT - Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing 1991
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 3rd IEEE Symposium on Parallel and Distributed Processing, PDPS 1991
Y2 - 2 December 1991 through 5 December 1991
ER -