Sorting networks

To the end and back again

Michael Codish, Luis Cruz-Filipe, Thorsten Ehlers, Mike Müller, Peter Schneider-Kamp

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

81 Downloads (Pure)

Resumé

New properties of the front and back ends of sorting networks are studied, illustrating their utility when searching for bounds on optimal networks. Search focuses first on the "out-sides" of the network and then on the inner part. Previous works focused on properties of the front end to break symmetries in the search. The new, out-side-in, properties shed understanding on how sorting networks sort, and facilitate the computation of new bounds on optimality. We present new, faster, parallel sorting networks for 17-20 inputs. For 17 inputs, we show that no sorting network using less layers exists.

OriginalsprogEngelsk
TidsskriftJournal of Computer and System Sciences
Vol/bind104
Sider (fra-til)184-201
Antal sider18
ISSN0022-0000
DOI
StatusUdgivet - sep. 2019

Fingeraftryk

Sorting Networks
Sorting
Sort
Optimality
Symmetry

Citer dette

Codish, Michael ; Cruz-Filipe, Luis ; Ehlers, Thorsten ; Müller, Mike ; Schneider-Kamp, Peter. / Sorting networks : To the end and back again. I: Journal of Computer and System Sciences. 2019 ; Bind 104. s. 184-201.
@article{db1c661966d745bd9b8620cb2a15fc3c,
title = "Sorting networks: To the end and back again",
abstract = "New properties of the front and back ends of sorting networks are studied, illustrating their utility when searching for bounds on optimal networks. Search focuses first on the {"}out-sides{"} of the network and then on the inner part. Previous works focused on properties of the front end to break symmetries in the search. The new, out-side-in, properties shed understanding on how sorting networks sort, and facilitate the computation of new bounds on optimality. We present new, faster, parallel sorting networks for 17-20 inputs. For 17 inputs, we show that no sorting network using less layers exists.",
keywords = "SAT-solving, Sorting networks",
author = "Michael Codish and Luis Cruz-Filipe and Thorsten Ehlers and Mike M{\"u}ller and Peter Schneider-Kamp",
year = "2019",
month = "9",
doi = "10.1016/j.jcss.2016.04.004",
language = "English",
volume = "104",
pages = "184--201",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Heinemann",

}

Sorting networks : To the end and back again. / Codish, Michael; Cruz-Filipe, Luis; Ehlers, Thorsten; Müller, Mike; Schneider-Kamp, Peter.

I: Journal of Computer and System Sciences, Bind 104, 09.2019, s. 184-201.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - Sorting networks

T2 - To the end and back again

AU - Codish, Michael

AU - Cruz-Filipe, Luis

AU - Ehlers, Thorsten

AU - Müller, Mike

AU - Schneider-Kamp, Peter

PY - 2019/9

Y1 - 2019/9

N2 - New properties of the front and back ends of sorting networks are studied, illustrating their utility when searching for bounds on optimal networks. Search focuses first on the "out-sides" of the network and then on the inner part. Previous works focused on properties of the front end to break symmetries in the search. The new, out-side-in, properties shed understanding on how sorting networks sort, and facilitate the computation of new bounds on optimality. We present new, faster, parallel sorting networks for 17-20 inputs. For 17 inputs, we show that no sorting network using less layers exists.

AB - New properties of the front and back ends of sorting networks are studied, illustrating their utility when searching for bounds on optimal networks. Search focuses first on the "out-sides" of the network and then on the inner part. Previous works focused on properties of the front end to break symmetries in the search. The new, out-side-in, properties shed understanding on how sorting networks sort, and facilitate the computation of new bounds on optimality. We present new, faster, parallel sorting networks for 17-20 inputs. For 17 inputs, we show that no sorting network using less layers exists.

KW - SAT-solving

KW - Sorting networks

U2 - 10.1016/j.jcss.2016.04.004

DO - 10.1016/j.jcss.2016.04.004

M3 - Journal article

VL - 104

SP - 184

EP - 201

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

ER -