COMPUTER SCIENCE COLLOQUIUM

The Quest for Optimal Sorting Networks (Part 2: Size)

Peter Schneider-Kamp Department of Mathematics and Computer Science University of Southern Denmark, Denmark

Tuesday, 26 August, 2014 at 13:15 IMADA's Seminar Room

ABSTRACT

This talk is the second of two talks on optimal sorting networks and deals with the problem of optimal size. We present a computer-assisted non-existence proof of nine-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found by Floyd in 1964 is optimal. As a corollary, we obtain that the 29-comparator network found by Waksman in 1969 is optimal when sorting ten inputs. This closes the two smallest open instances of the optimal size sorting network problem, which have been open since the results of Floyd and Knuth from 1966 proving optimality for sorting networks of up to eight inputs.

The entire implementation is written in SWI-Prolog and was run on a cluster of 12 nodes with 12 cores each, able to run a total of 288 concurrent threads, making extensive use of SWI-Prolog’s built-in predicate concurrency/3. The search space of 2.2×10 37 comparator networks was exhausted after just under 10 days of computation. This shows the ability of logic programming to provide a scalable parallel implementation while at the same time instilling a high level of trust in the correctness of the proof.

Host:

---

SDU HOME | IMADA HOME | Previous Page

---

Daniel Merkle