The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes

Michael Codish; Luís Cruz-Filipe; Peter Schneider-Kamp

doi:10.1109/SYNASC.2014.55

The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes

Michael Codish, Luís Cruz-Filipe, Peter Schneider-Kamp

Department of Mathematics and Computer Science

Ben-Gurion University of the Negev

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

Previous work identifying depth-optimal n-channel sorting networks for 9 ≤ n ≤ 16 is based on exploiting symmetries of the first two layers. However, the naive generate-and-test approach typically applied does not scale. This paper revisits the problem of generating two-layer prefixes modulo symmetries. An improved notion of symmetry is provided and a novel technique based on regular languages and graph isomorphism is shown to generate the set of non-symmetric representations. An empirical evaluation demonstrates that the new method outperforms the generate-and-test approach by orders of magnitude and easily scales until n = 40.

Original language	English
Title of host publication	Proceedings of the 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
Editors	Franz Winkler, Viorel Negru, Tetsuo Ida, Tudor Jebelean, Dana Petcu, Stephen M. Watt, Daniela Zaharie
Publisher	IEEE
Publication date	2014
Pages	359-366
ISBN (Print)	978-1-4799-8447-3
ISBN (Electronic)	9781479984480
DOIs	https://doi.org/10.1109/SYNASC.2014.55
Publication status	Published - 2014
Event	16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing - Timisoara, Timis, Romania Duration: 22. Sep 2014 → 25. Sep 2014

Conference

Conference	16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
Country/Territory	Romania
City	Timisoara, Timis
Period	22/09/2014 → 25/09/2014

Documents & Links

10.1109/SYNASC.2014.55

Cite this

Codish, M., Cruz-Filipe, L., & Schneider-Kamp, P. (2014). The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes. In F. Winkler, V. Negru, T. Ida, T. Jebelean, D. Petcu, S. M. Watt, & D. Zaharie (Eds.), Proceedings of the 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (pp. 359-366). IEEE. https://doi.org/10.1109/SYNASC.2014.55

Codish, Michael ; Cruz-Filipe, Luís ; Schneider-Kamp, Peter. / The Quest for Optimal Sorting Networks : Efficient Generation of Two-Layer Prefixes. Proceedings of the 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. editor / Franz Winkler ; Viorel Negru ; Tetsuo Ida ; Tudor Jebelean ; Dana Petcu ; Stephen M. Watt ; Daniela Zaharie. IEEE, 2014. pp. 359-366

@inproceedings{71c96e92670b475eb2bbd934c8f1c6e0,

title = "The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes",

abstract = "Previous work identifying depth-optimal n-channel sorting networks for 9 ≤ n ≤ 16 is based on exploiting symmetries of the first two layers. However, the naive generate-and-test approach typically applied does not scale. This paper revisits the problem of generating two-layer prefixes modulo symmetries. An improved notion of symmetry is provided and a novel technique based on regular languages and graph isomorphism is shown to generate the set of non-symmetric representations. An empirical evaluation demonstrates that the new method outperforms the generate-and-test approach by orders of magnitude and easily scales until n = 40.",

author = "Michael Codish and Lu{\'i}s Cruz-Filipe and Peter Schneider-Kamp",

year = "2014",

doi = "10.1109/SYNASC.2014.55",

language = "English",

isbn = "978-1-4799-8447-3",

pages = "359--366",

editor = "Franz Winkler and Viorel Negru and Tetsuo Ida and Tudor Jebelean and Dana Petcu and Watt, {Stephen M.} and Daniela Zaharie",

booktitle = "Proceedings of the 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing",

publisher = "IEEE",

address = "United States",

note = "16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC ; Conference date: 22-09-2014 Through 25-09-2014",

}

Codish, M, Cruz-Filipe, L & Schneider-Kamp, P 2014, The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes. in F Winkler, V Negru, T Ida, T Jebelean, D Petcu, SM Watt & D Zaharie (eds), Proceedings of the 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. IEEE, pp. 359-366, 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Timis, Romania, 22/09/2014. https://doi.org/10.1109/SYNASC.2014.55

The Quest for Optimal Sorting Networks : Efficient Generation of Two-Layer Prefixes. / Codish, Michael; Cruz-Filipe, Luís ; Schneider-Kamp, Peter.

Proceedings of the 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. ed. / Franz Winkler; Viorel Negru; Tetsuo Ida; Tudor Jebelean; Dana Petcu; Stephen M. Watt; Daniela Zaharie. IEEE, 2014. p. 359-366.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - The Quest for Optimal Sorting Networks

T2 - 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

AU - Codish, Michael

AU - Cruz-Filipe, Luís

AU - Schneider-Kamp, Peter

PY - 2014

Y1 - 2014

N2 - Previous work identifying depth-optimal n-channel sorting networks for 9 ≤ n ≤ 16 is based on exploiting symmetries of the first two layers. However, the naive generate-and-test approach typically applied does not scale. This paper revisits the problem of generating two-layer prefixes modulo symmetries. An improved notion of symmetry is provided and a novel technique based on regular languages and graph isomorphism is shown to generate the set of non-symmetric representations. An empirical evaluation demonstrates that the new method outperforms the generate-and-test approach by orders of magnitude and easily scales until n = 40.

AB - Previous work identifying depth-optimal n-channel sorting networks for 9 ≤ n ≤ 16 is based on exploiting symmetries of the first two layers. However, the naive generate-and-test approach typically applied does not scale. This paper revisits the problem of generating two-layer prefixes modulo symmetries. An improved notion of symmetry is provided and a novel technique based on regular languages and graph isomorphism is shown to generate the set of non-symmetric representations. An empirical evaluation demonstrates that the new method outperforms the generate-and-test approach by orders of magnitude and easily scales until n = 40.

U2 - 10.1109/SYNASC.2014.55

DO - 10.1109/SYNASC.2014.55

M3 - Article in proceedings

SN - 978-1-4799-8447-3

SP - 359

EP - 366

BT - Proceedings of the 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

A2 - Winkler, Franz

A2 - Negru, Viorel

A2 - Ida, Tetsuo

A2 - Jebelean, Tudor

A2 - Petcu, Dana

A2 - Watt, Stephen M.

A2 - Zaharie, Daniela

PB - IEEE

Y2 - 22 September 2014 through 25 September 2014

ER -

The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes

Abstract

Conference

Documents & Links

Fingerprint

Cite this