Resource oblivious sorting on multicores

DOI10.1007/978-3-642-14165-2_20MaRDI QIDQ3587382zbMATH OpenOpenAlexFDO

Authors Vijaya Ramachandran, Richard Cole

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.01504

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Searching and sorting (68P10)

Abstract: We present a deterministic sorting algorithm, SPMS (Sample, Partition, and Merge Sort), that interleaves the partitioning of a sample sort with merging. Sequentially, it sorts $n$ elements in $O(nlogn)$ time cache-obliviously with an optimal number of cache misses. The parallel complexity (or critical path length) of the algorithm is $O(logncdotloglogn)$, which improves on previous bounds for optimal cache oblivious sorting. The algorithm also has low false sharing costs. When scheduled by a work-stealing scheduler in a multicore computing environment with a global shared memory and $p$ cores, each having a cache of size $M$ organized in blocks of size $B$, the costs of the additional cache misses and false sharing misses due to this parallel execution are bounded by the cost of $O(ScdotM/B)$ and $O(ScdotB)$ cache misses respectively, where $S$ is the number of steals performed during the execution. Finally, SPMS is resource oblivious in Athat the dependence on machine parameters appear only in the analysis of its performance, and not within the algorithm itself.

Recommendations

• Oblivious algorithms for multicores and networks of processors
• An efficient parallel sorting algorithm
• A benchmark parallel sort for shared memory multiprocessors
• Parallel sorting by regular sampling
• scientific article; zbMATH DE number 4064478

Cited in

(4)

• Complexity analysis and performance of double hashing sort algorithm
• Scalable Suffix Sorting on a Multicore Machine
• Oracle-guided scheduling for controlling granularity in implicitly parallel languages
• Oblivious algorithms for multicores and networks of processors

This page was built for publication: Resource oblivious sorting on multicores

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587382)