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

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Proceedings of the 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
Redaktører	Franz Winkler, Viorel Negru, Tetsuo Ida, Tudor Jebelean, Dana Petcu, Stephen M. Watt, Daniela Zaharie
Antal sider	8
Udgivelsessted	United States
Forlag	IEEE
Publikationsdato	2014
Sider	359-366
ISBN (Trykt)	978-1-4799-8447-3
DOI	https://doi.org/10.1109/SYNASC.2014.55
Status	Udgivet - 2014
Udgivet eksternt	Ja
Begivenhed	International Symposium on Symbolic and Numeric Algorithms for Scientific Computing - West University of Timisoara, Timisoara, Rumænien Varighed: 22 sep. 2014 → 25 sep. 2014 Konferencens nummer: 16 https://synasc.ro/2014/

Symposium

Symposium	International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
Nummer	16
Lokation	West University of Timisoara
Land/Område	Rumænien
By	Timisoara
Periode	22/09/2014 → 25/09/2014
Internetadresse	https://synasc.ro/2014/

Adgang til dokumentet

10.1109/SYNASC.2014.55

Citationsformater

Codish, M., Cruz-Filipe, L., & Schneider-Kamp, P. (2014). The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes. I F. Winkler, V. Negru, T. Ida, T. Jebelean, D. Petcu, S. M. Watt, & D. Zaharie (red.), Proceedings of the 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (s. 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. red. / Franz Winkler ; Viorel Negru ; Tetsuo Ida ; Tudor Jebelean ; Dana Petcu ; Stephen M. Watt ; Daniela Zaharie. United States : IEEE, 2014. s. 359-366

@inproceedings{e2270abcbc514003bf774d33b049b396,

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",

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

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",

url = "https://synasc.ro/2014/",

}

Codish, M, Cruz-Filipe, L & Schneider-Kamp, P 2014, The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes. i F Winkler, V Negru, T Ida, T Jebelean, D Petcu, SM Watt & D Zaharie (red), Proceedings of the 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. IEEE, United States, s. 359-366, International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Rumænien, 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. red. / Franz Winkler; Viorel Negru; Tetsuo Ida; Tudor Jebelean; Dana Petcu; Stephen M. Watt; Daniela Zaharie. United States: IEEE, 2014. s. 359-366.

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

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

AU - Codish, Michael

AU - Cruz-Filipe, Luís

AU - Schneider-Kamp, Peter

N1 - Conference code: 16

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

CY - United States

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

Y2 - 22 September 2014 through 25 September 2014

ER -

Codish M, Cruz-Filipe L, Schneider-Kamp P. The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes. I Winkler F, Negru V, Ida T, Jebelean T, Petcu D, Watt SM, Zaharie D, red., Proceedings of the 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. United States: IEEE. 2014. s. 359-366 doi: 10.1109/SYNASC.2014.55

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

Abstract

Symposium

Adgang til dokumentet

Fingeraftryk

Citationsformater