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

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 languageEnglish
Title of host publicationProceedings of the 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
EditorsFranz Winkler, Viorel Negru, Tetsuo Ida, Tudor Jebelean, Dana Petcu, Stephen M. Watt, Daniela Zaharie
PublisherIEEE
Publication date2014
Pages359-366
ISBN (Print)978-1-4799-8447-3
ISBN (Electronic)9781479984480
DOIs
Publication statusPublished - 2014
Event16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing - Timisoara, Timis, Romania
Duration: 22. Sept 201425. Sept 2014

Conference

Conference16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
Country/TerritoryRomania
CityTimisoara, Timis
Period22/09/201425/09/2014

Fingerprint

Dive into the research topics of 'The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes'. Together they form a unique fingerprint.

Cite this