Applying Sorting Networks to Synthesize Optimized Sorting Libraries

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Resumé

This paper presents 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 base case for small, fixed, numbers of inputs. Unrolling the code for the base case by ignoring loop conditions eliminates branching, resulting in code equivalent to a sorting network. This enables 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, the 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.
OriginalsprogEngelsk
TitelLogic-Based Program Synthesis and Transformation : 25th International Symposium, LOPSTR 2015, Siena, Italy, July 13-15, 2015. Revised Selected Papers
RedaktørerMoreno Falaschi
ForlagSpringer
Publikationsdatodec. 2015
Sider127-142
ISBN (Trykt)978-3-319-27435-5
ISBN (Elektronisk)978-3-319-27436-2
DOI
StatusUdgivet - dec. 2015
Begivenhed25th International Symposium on Logic-based Program Synthesis and Transformation - Siena, Italien
Varighed: 13. jul. 201515. jul. 2015

Konference

Konference25th International Symposium on Logic-based Program Synthesis and Transformation
LandItalien
BySiena
Periode13/07/201515/07/2015
NavnLecture Notes in Computer Science
Vol/bind9527
ISSN0302-9743

Fingeraftryk

Sorting
Program processors

Citer dette

Codish, M., Cruz-Filipe, L., Nebel, M., & Schneider-Kamp, P. (2015). Applying Sorting Networks to Synthesize Optimized Sorting Libraries. I M. Falaschi (red.), Logic-Based Program Synthesis and Transformation: 25th International Symposium, LOPSTR 2015, Siena, Italy, July 13-15, 2015. Revised Selected Papers (s. 127-142). Springer. Lecture Notes in Computer Science, Bind. 9527 https://doi.org/10.1007/978-3-319-27436-2_8
Codish, Michael ; Cruz-Filipe, Luís ; Nebel, Markus ; Schneider-Kamp, Peter. / Applying Sorting Networks to Synthesize Optimized Sorting Libraries. Logic-Based Program Synthesis and Transformation: 25th International Symposium, LOPSTR 2015, Siena, Italy, July 13-15, 2015. Revised Selected Papers. red. / Moreno Falaschi. Springer, 2015. s. 127-142 (Lecture Notes in Computer Science, Bind 9527).
@inproceedings{3d267ad4f25247b2a76e5dd2ad62c6d6,
title = "Applying Sorting Networks to Synthesize Optimized Sorting Libraries",
abstract = "This paper presents 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 base case for small, fixed, numbers of inputs. Unrolling the code for the base case by ignoring loop conditions eliminates branching, resulting in code equivalent to a sorting network. This enables 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, the 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.",
author = "Michael Codish and Lu{\'i}s Cruz-Filipe and Markus Nebel and Peter Schneider-Kamp",
year = "2015",
month = "12",
doi = "10.1007/978-3-319-27436-2_8",
language = "English",
isbn = "978-3-319-27435-5",
pages = "127--142",
editor = "Moreno Falaschi",
booktitle = "Logic-Based Program Synthesis and Transformation",
publisher = "Springer",
address = "Germany",

}

Codish, M, Cruz-Filipe, L, Nebel, M & Schneider-Kamp, P 2015, Applying Sorting Networks to Synthesize Optimized Sorting Libraries. i M Falaschi (red.), Logic-Based Program Synthesis and Transformation: 25th International Symposium, LOPSTR 2015, Siena, Italy, July 13-15, 2015. Revised Selected Papers. Springer, Lecture Notes in Computer Science, bind 9527, s. 127-142, 25th International Symposium on Logic-based Program Synthesis and Transformation, Siena, Italien, 13/07/2015. https://doi.org/10.1007/978-3-319-27436-2_8

Applying Sorting Networks to Synthesize Optimized Sorting Libraries. / Codish, Michael; Cruz-Filipe, Luís; Nebel, Markus; Schneider-Kamp, Peter.

Logic-Based Program Synthesis and Transformation: 25th International Symposium, LOPSTR 2015, Siena, Italy, July 13-15, 2015. Revised Selected Papers. red. / Moreno Falaschi. Springer, 2015. s. 127-142 (Lecture Notes in Computer Science, Bind 9527).

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

TY - GEN

T1 - Applying Sorting Networks to Synthesize Optimized Sorting Libraries

AU - Codish, Michael

AU - Cruz-Filipe, Luís

AU - Nebel, Markus

AU - Schneider-Kamp, Peter

PY - 2015/12

Y1 - 2015/12

N2 - This paper presents 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 base case for small, fixed, numbers of inputs. Unrolling the code for the base case by ignoring loop conditions eliminates branching, resulting in code equivalent to a sorting network. This enables 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, the 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.

AB - This paper presents 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 base case for small, fixed, numbers of inputs. Unrolling the code for the base case by ignoring loop conditions eliminates branching, resulting in code equivalent to a sorting network. This enables 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, the 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.

U2 - 10.1007/978-3-319-27436-2_8

DO - 10.1007/978-3-319-27436-2_8

M3 - Article in proceedings

SN - 978-3-319-27435-5

SP - 127

EP - 142

BT - Logic-Based Program Synthesis and Transformation

A2 - Falaschi, Moreno

PB - Springer

ER -

Codish M, Cruz-Filipe L, Nebel M, Schneider-Kamp P. Applying Sorting Networks to Synthesize Optimized Sorting Libraries. I Falaschi M, red., Logic-Based Program Synthesis and Transformation: 25th International Symposium, LOPSTR 2015, Siena, Italy, July 13-15, 2015. Revised Selected Papers. Springer. 2015. s. 127-142. (Lecture Notes in Computer Science, Bind 9527). https://doi.org/10.1007/978-3-319-27436-2_8