Scalability of parallel sorting on mesh multicomputers

V. Singh, V. Kumar, G. Agha, C. Tomlinson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations


This paper presents two new parallel algorithms QSPl and QSP2 based on sequential quicksort for sorting data on a mesh multicomputer, and analyzes their scalability using the isoefficiency metric. We show that QSP2 matches the lower bound on the isoefficiency function for mesh multicomputer. The isoefficiency of QSPl is also fairly close to optimal. Lang et al. and Schnorr et al. have developed parallel sorting algorithms for the mesh architecture that have either optimal (Schnorr) or close to optimal (Lang) run-time complexity for the one-element-per-processor case. Both QSPl and QSP2 have worse performance than these algorithms for the one-element-perprocessor case. But QSPl and QSP2 have better scalability than the scaled-down variants of these algorithms (for the case in which there are more elements than processors). As a result, our new parallel formulations are better than these scaled-down variants in terms of speedup w.r.t the best sequential algorithms. We also present a different variant of Lang's sort which is asymptotically as scalable as QSP2 (for the multiple-element-per-processor case). We briefly discuss another metric called "resource consumption metric". According to this metric, both QSPl and QSP2 are strictly superior to Lang's sort and its variations.

Original languageEnglish (US)
Title of host publicationProceedings - 5th International Parallel Processing Symposium, IPPS 1991
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Electronic)0818691670, 9780818691676
StatePublished - Jan 1 1991
Event5th International Parallel Processing Symposium, IPPS 1991 - Anaheim, United States
Duration: Apr 30 1991May 2 1991

Publication series

NameProceedings - 5th International Parallel Processing Symposium, IPPS 1991


Conference5th International Parallel Processing Symposium, IPPS 1991
Country/TerritoryUnited States


Dive into the research topics of 'Scalability of parallel sorting on mesh multicomputers'. Together they form a unique fingerprint.

Cite this