Scalability of parallel sorting on mesh multicomputers

摘要

The paper presents two new parallel algorithms QSP1 and QSP2 basedon sequential quicksort for sorting data on a mesh multicomputer, andanalyzes their scalability using the isoefficiency metric. It shows thatQSP2 matches the lower bound on the isoefficiency function for meshmulticomputers. The isoefficiency of QSP1 is also fairly close tooptimal. Lang et al. (1985) and Schnorr et al. (1986) have developedparallel sorting algorithms for the mesh architecture that have eitheroptimal (Schnorr) or close to optimal (Lang) run-time complexity for theone-element-per-processor case. Both QSP1 and QSP2 have worseperformance than these algorithms for the one-element-per-processorcase. But QSP1 and QSP2 have better scalability than the scaled-downvariants of these algorithms (for the case in which there are moreelements than processors). As a result, the new parallel formulationsare better than these scaled-down variants in terms of speedup w.r.t thebest sequential algorithms. The paper also presents a different variantof Lang's sort which is asymptotically as scalable as QSP2 (for themultiple-element-per-processor case). It briefly discusses anothermetric called `resource consumption metric'. According to this metric,both QSP1 and QSP2 are strictly superior to Lang's sort and itsvariations