An efficient parallel sorting algorithm (Q1199552)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An efficient parallel sorting algorithm |
scientific article |
Statements
An efficient parallel sorting algorithm (English)
0 references
16 January 1993
0 references
We consider the merge-based sorting on the EREW PRAM multiprocessor with private caches. We propose a parallel sorting algorithm that achieves linear speedup in both the number of comparisons and the number of data accesses, using a novel partition algorithm which splits an arbitrary number of sorted runs among all the processors evenly, independent of the sort-key value. The percentile point for each sorted run is found efficiently and only one merge pass is required. The processing and access costs are \(O(t_ p((N/P)\log N+P\log(N/(2P))))\) and \(O(t_ a((N/P)(\log(NM/P)/\log M)+P\log(N/(2P))))\), where \(N\) is the number of data elements, \(P\) is the number of processors, \(M\) is the size of the cache, \(t_ p\) is the time needed to execute an instruction using cache memory and \(t_ a\) is the time needed for a data access from shared memory.
0 references
partitioning
0 references
merging
0 references
EREW PRAM
0 references