Efficient algorithms for parallel sorting on mesh multicomputers

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

Research output: Contribution to journalArticle

Abstract

We present two new parallel algorithms QSP1 and QSP2 based on sequential quicksort for sorting data on a mesh multicomputer, and analyze their scalability using the isoefficiency metric. We show that QSP2 matches the lower bound on the isoefficiency function for mesh multicomputers, while QSP1 is fairly close to optimal. Lang et al.(1) and Schnorr et al.(2) 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-perprocessor case. Both QSP1 and QSP2 have better scalability than the scaled-down variants of these algorithms (for the case in which there are more elements than processors). We also analyze a different variant of Lang's sort which is as scalable as QSP2. We briefly discuss another metric called "resource consumption." According to this metric, both QSP1 and QSP2 are superior to variants of Lang's sort.

Original languageEnglish (US)
Pages (from-to)95-131
Number of pages37
JournalInternational Journal of Parallel Programming
Volume20
Issue number2
DOIs
StatePublished - Apr 1 1991

Keywords

  • Parallel
  • algorithms
  • isoefficiency
  • mesh
  • multicomputer
  • quicksort
  • resource consumption
  • scalability
  • sorting

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems

Fingerprint Dive into the research topics of 'Efficient algorithms for parallel sorting on mesh multicomputers'. Together they form a unique fingerprint.

  • Cite this