Optimal-depth sorting networks

Daniel Bundala, Michael Codish, Luís Cruz-Filipe, Peter Schneider-Kamp, Jakub Závodný

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

92 Downloads (Pure)

Resumé

We solve a 40-year-old open problem on depth optimality of sorting networks. In 1973, Donald E. Knuth detailed sorting networks of the smallest depth known for n≤16 inputs, quoting optimality for n≤8 (Volume 3 of “The Art of Computer Programming”). In 1989, Parberry proved optimality of networks with 9≤n≤10 inputs. We present a general technique for obtaining such results, proving optimality of the remaining open cases of 11≤n≤16 inputs. Exploiting symmetry, we construct a small set Rn of two-layer networks such that: if there is a depth-k sorting network on n inputs, then there is one whose first layers are in Rn. For each network in Rn, we construct a propositional formula whose satisfiability is necessary for the existence of a depth-k sorting network. Using an off-the-shelf SAT solver we prove optimality of the sorting networks listed by Knuth. For n≤10 inputs, our algorithm is orders of magnitude faster than prior ones.
OriginalsprogEngelsk
TidsskriftJournal of Computer and System Sciences
Vol/bind84
Sider (fra-til)185-204
ISSN0022-0000
DOI
StatusUdgivet - 2017

Fingeraftryk

Sorting Networks
Sorting
Optimality
Network layers
Computer programming
Open Problems
Programming
Symmetry
Necessary

Citer dette

Bundala, Daniel ; Codish, Michael ; Cruz-Filipe, Luís ; Schneider-Kamp, Peter ; Závodný, Jakub. / Optimal-depth sorting networks. I: Journal of Computer and System Sciences. 2017 ; Bind 84. s. 185-204.
@article{017e73f5eca64a369596fe3610d6d81b,
title = "Optimal-depth sorting networks",
abstract = "We solve a 40-year-old open problem on depth optimality of sorting networks. In 1973, Donald E. Knuth detailed sorting networks of the smallest depth known for n≤16 inputs, quoting optimality for n≤8 (Volume 3 of “The Art of Computer Programming”). In 1989, Parberry proved optimality of networks with 9≤n≤10 inputs. We present a general technique for obtaining such results, proving optimality of the remaining open cases of 11≤n≤16 inputs. Exploiting symmetry, we construct a small set Rn of two-layer networks such that: if there is a depth-k sorting network on n inputs, then there is one whose first layers are in Rn. For each network in Rn, we construct a propositional formula whose satisfiability is necessary for the existence of a depth-k sorting network. Using an off-the-shelf SAT solver we prove optimality of the sorting networks listed by Knuth. For n≤10 inputs, our algorithm is orders of magnitude faster than prior ones.",
author = "Daniel Bundala and Michael Codish and Lu{\'i}s Cruz-Filipe and Peter Schneider-Kamp and Jakub Z{\'a}vodn{\'y}",
year = "2017",
doi = "10.1016/j.jcss.2016.09.004",
language = "English",
volume = "84",
pages = "185--204",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Heinemann",

}

Optimal-depth sorting networks. / Bundala, Daniel; Codish, Michael; Cruz-Filipe, Luís; Schneider-Kamp, Peter; Závodný, Jakub.

I: Journal of Computer and System Sciences, Bind 84, 2017, s. 185-204.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - Optimal-depth sorting networks

AU - Bundala, Daniel

AU - Codish, Michael

AU - Cruz-Filipe, Luís

AU - Schneider-Kamp, Peter

AU - Závodný, Jakub

PY - 2017

Y1 - 2017

N2 - We solve a 40-year-old open problem on depth optimality of sorting networks. In 1973, Donald E. Knuth detailed sorting networks of the smallest depth known for n≤16 inputs, quoting optimality for n≤8 (Volume 3 of “The Art of Computer Programming”). In 1989, Parberry proved optimality of networks with 9≤n≤10 inputs. We present a general technique for obtaining such results, proving optimality of the remaining open cases of 11≤n≤16 inputs. Exploiting symmetry, we construct a small set Rn of two-layer networks such that: if there is a depth-k sorting network on n inputs, then there is one whose first layers are in Rn. For each network in Rn, we construct a propositional formula whose satisfiability is necessary for the existence of a depth-k sorting network. Using an off-the-shelf SAT solver we prove optimality of the sorting networks listed by Knuth. For n≤10 inputs, our algorithm is orders of magnitude faster than prior ones.

AB - We solve a 40-year-old open problem on depth optimality of sorting networks. In 1973, Donald E. Knuth detailed sorting networks of the smallest depth known for n≤16 inputs, quoting optimality for n≤8 (Volume 3 of “The Art of Computer Programming”). In 1989, Parberry proved optimality of networks with 9≤n≤10 inputs. We present a general technique for obtaining such results, proving optimality of the remaining open cases of 11≤n≤16 inputs. Exploiting symmetry, we construct a small set Rn of two-layer networks such that: if there is a depth-k sorting network on n inputs, then there is one whose first layers are in Rn. For each network in Rn, we construct a propositional formula whose satisfiability is necessary for the existence of a depth-k sorting network. Using an off-the-shelf SAT solver we prove optimality of the sorting networks listed by Knuth. For n≤10 inputs, our algorithm is orders of magnitude faster than prior ones.

U2 - 10.1016/j.jcss.2016.09.004

DO - 10.1016/j.jcss.2016.09.004

M3 - Journal article

VL - 84

SP - 185

EP - 204

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

ER -