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.
|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|
|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||16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing|
|Period||22/09/2014 → 25/09/2014|