(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

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