Applying sorting networks to synthesize optimized sorting libraries

DOI10.1007/978-3-319-27436-2_8MaRDI QIDQ5743589zbMATH OpenOpenAlexFDO

Authors

Publication date 5 February 2016

Published in Logic-Based Program Synthesis and Transformation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Searching and sorting (68P10)

Abstract: This paper shows an application of the theory of sorting networks to facilitate the synthesis of optimized general purpose sorting libraries. Standard sorting libraries are often based on combinations of the classic Quicksort algorithm with insertion sort applied as the base case for small fixed numbers of inputs. Unrolling the code for the base case by ignoring loop conditions eliminates branching and results in code which is equivalent to a sorting network. This enables the application of further program transformations based on sorting network optimizations, and eventually the synthesis of code from sorting networks. We show that if considering the number of comparisons and swaps then theory predicts no real advantage of this approach. However, significant speed-ups are obtained when taking advantage of instruction level parallelism and non-branching conditional assignment instructions, both of which are common in modern CPU architectures. We provide empirical evidence that using code synthesized from efficient sorting networks as the base case for Quicksort libraries results in significant real-world speed-ups.

Recommendations

• Optimizing sorting algorithms by using sorting networks
• On the complexity of min-max sorting networks
• Using symmetry and evolutionary search to minimize sorting networks
• Optimal sorting networks
• On optimal parallelization of sorting networks

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 2155520 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• A computer-assisted optimal depth lower bound for nine-input sorting networks
• New Bounds on Optimal Sorting Networks
• Optimal sorting networks
• Quicksort
• Sorting networks: the end game
• The analysis of Quicksort programs

Cited in

(5)

• Using symmetry and evolutionary search to minimize sorting networks
• Sorting networks: to the end and back again
• On optimal parallelization of sorting networks
• Optimal-depth sorting networks
• Optimizing sorting algorithms by using sorting networks

Describes a project that uses

Uses Software

• Quicksort

This page was built for publication: Applying sorting networks to synthesize optimized sorting libraries

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