Applying sorting networks to synthesize optimized sorting libraries

DOI10.1007/978-3-319-27436-2_8zbMATH Open1362.68062arXiv1505.01962OpenAlexW1518055973MaRDI QIDQ5743589FDOQ5743589

Authors:

Publication date: 5 February 2016

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

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.

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

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

Mathematics Subject Classification ID

Searching and sorting (68P10)

Cites Work

• Quicksort
• Title not available (Why is that?)
• The analysis of Quicksort programs
• Title not available (Why is that?)
• Sorting networks: the end game
• New Bounds on Optimal Sorting Networks
• A computer-assisted optimal depth lower bound for nine-input sorting networks
• Optimal sorting networks
• Title not available (Why is that?)

Cited In (5)

• 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
• Using symmetry and evolutionary search to minimize sorting networks

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)