COMPUTER SCIENCE COLLOQUIUM
The Quest for Optimal Sorting Networks (Part 1: Depth)
Luís Cruz-Filipe
Department of Mathematics and Computer Science
University of Southern Denmark, Denmark
Auditorium U49C
IMADA's Seminar Room
ABSTRACT
This talk is the first of two talks on optimal sorting networks and deals with the problem of optimal depth. The second talk will address the related, but surprisingly different, optimal size problem.
Previous work identifying depth-optimal n-channel sorting networks for 9 ≤ n is based on exploiting symmetries of the first two layers. However, the naive generate-and-test approach typically applied does not scale beyond n = 13.
In this talk we revisit the problem of generating two-layer prefixes modulo symmetries. We provide an improved notion of symmetry and a novel technique based on regular languages and graph isomorphism 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. We show that using this approach, we can obtain computer-assisted proofs of the optimal depth for n ≤ 16.
Host:
SDU HOME |
IMADA HOME |
Previous Page
Daniel Merkle