 |
The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes
Michael Codish, Luis Cruz-Filipe and Peter Schneider-Kamp
Technical Report (unpublished);
September 2014.
Abstract:
Previous work identifying depth-optimal $n$-channel sorting networks for 9 leq n leq 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$.Available: bibtex entry
Related sites: e-print from arXiv.org
Michael Codish
The Department of Computer Science
Ben-Gurion University of the Negev
PoB 653, Beer-Sheva, 84105, Israel
mcodish@cs.bgu.ac.il