A comparison based parallel sorting algorithm

Laxmikant V. Kale; Sanjeev Krishnan

doi:10.1109/ICPP.1993.17

A comparison based parallel sorting algorithm

Laxmikant V. Kale, Sanjeev Krishnan

Computer Science

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

Abstract

We present a fast comparison based parallel sorting algorithm that can handle arbitrary key types. Data movement is the major portion of sorting time for most algorithms in the literature. Our algorithm is parameterized so that is can be tuned to control data movement time, especially for large data sets. Parallel histograms are used to partition the key set exactly. The algorithm is architecture independent, and has been implemented in the CHARM portable parallel programming system, allowing it to be efficiently run on virtually any MIMD computer. Performance results for sorting different data sets are presented.

Original language	English (US)
Title of host publication	Algorithms and Applications
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	196-200
Number of pages	5
ISBN (Electronic)	0849389836
DOIs	https://doi.org/10.1109/ICPP.1993.17
State	Published - 1993
Event	1993 International Conference on Parallel Processing, ICPP 1993 - Syracuse, United States Duration: Aug 16 1993 → Aug 20 1993

Publication series

Name	Proceedings of the International Conference on Parallel Processing
Volume	3
ISSN (Print)	0190-3918

Conference

Conference	1993 International Conference on Parallel Processing, ICPP 1993
Country/Territory	United States
City	Syracuse
Period	8/16/93 → 8/20/93

ASJC Scopus subject areas

Software
Mathematics(all)
Hardware and Architecture

Online availability

10.1109/ICPP.1993.17

Library availability

Discover UIUC Full Text

Cite this

Kale, LV & Krishnan, S 1993, A comparison based parallel sorting algorithm. in Algorithms and Applications., 4134268, Proceedings of the International Conference on Parallel Processing, vol. 3, Institute of Electrical and Electronics Engineers Inc., pp. 196-200, 1993 International Conference on Parallel Processing, ICPP 1993, Syracuse, United States, 8/16/93. https://doi.org/10.1109/ICPP.1993.17

@inproceedings{f28c71a38a4541f0b13920dbf18d5a1c,

title = "A comparison based parallel sorting algorithm",

abstract = "We present a fast comparison based parallel sorting algorithm that can handle arbitrary key types. Data movement is the major portion of sorting time for most algorithms in the literature. Our algorithm is parameterized so that is can be tuned to control data movement time, especially for large data sets. Parallel histograms are used to partition the key set exactly. The algorithm is architecture independent, and has been implemented in the CHARM portable parallel programming system, allowing it to be efficiently run on virtually any MIMD computer. Performance results for sorting different data sets are presented.",

author = "Kale, {Laxmikant V.} and Sanjeev Krishnan",

note = "Funding Information: 'This teat& WM supported in part by the National Science Foundation vanla CCR-SO7195 md CCR-91-06608. Publisher Copyright: {\textcopyright} 1993 IEEE. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.; 1993 International Conference on Parallel Processing, ICPP 1993 ; Conference date: 16-08-1993 Through 20-08-1993",

year = "1993",

doi = "10.1109/ICPP.1993.17",

language = "English (US)",

series = "Proceedings of the International Conference on Parallel Processing",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "196--200",

booktitle = "Algorithms and Applications",

address = "United States",

}

TY - GEN

T1 - A comparison based parallel sorting algorithm

AU - Kale, Laxmikant V.

AU - Krishnan, Sanjeev

N1 - Funding Information: 'This teat& WM supported in part by the National Science Foundation vanla CCR-SO7195 md CCR-91-06608. Publisher Copyright: © 1993 IEEE. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.

PY - 1993

Y1 - 1993

N2 - We present a fast comparison based parallel sorting algorithm that can handle arbitrary key types. Data movement is the major portion of sorting time for most algorithms in the literature. Our algorithm is parameterized so that is can be tuned to control data movement time, especially for large data sets. Parallel histograms are used to partition the key set exactly. The algorithm is architecture independent, and has been implemented in the CHARM portable parallel programming system, allowing it to be efficiently run on virtually any MIMD computer. Performance results for sorting different data sets are presented.

AB - We present a fast comparison based parallel sorting algorithm that can handle arbitrary key types. Data movement is the major portion of sorting time for most algorithms in the literature. Our algorithm is parameterized so that is can be tuned to control data movement time, especially for large data sets. Parallel histograms are used to partition the key set exactly. The algorithm is architecture independent, and has been implemented in the CHARM portable parallel programming system, allowing it to be efficiently run on virtually any MIMD computer. Performance results for sorting different data sets are presented.

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

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

U2 - 10.1109/ICPP.1993.17

DO - 10.1109/ICPP.1993.17

M3 - Conference contribution

AN - SCOPUS:0344612072

T3 - Proceedings of the International Conference on Parallel Processing

SP - 196

EP - 200

BT - Algorithms and Applications

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 1993 International Conference on Parallel Processing, ICPP 1993

Y2 - 16 August 1993 through 20 August 1993

ER -

A comparison based parallel sorting algorithm

Abstract

Publication series

Conference

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this