{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T02:32:49Z","timestamp":1725762769090},"reference-count":0,"publisher":"EasyChair","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Sorting networks are sorting algorithms that execute a sequence of operations indepen- dently of the input. Since they can be implemented directly as circuits, sorting networks are easy to implement in hardware \u2013 but they are also used often in software to improve performance of base cases of standard recursive sorting algorithms. For this purpose, they are translated into machine-code instructions in a systematic way.<\/jats:p><jats:p>Recently, a deep-learning system discovered better implementations than previously known of some sorting networks with up to 8 inputs. In this article, we show that all these examples are instances of a general pattern whereby some instructions are removed. We show that this removal can be done when a particular set of constraints on integers is satisfiable, and identify conditions where we can reduce this problem to propositional satisfiability. We systematically apply this general construction to improve the best-known implementations of sorting networks of size up to 128, which are the ones most commonly found in software implementations.<\/jats:p>","DOI":"10.29007\/lzks","type":"proceedings-article","created":{"date-parts":[[2024,5,27]],"date-time":"2024-05-27T22:10:10Z","timestamp":1716847810000},"page":"36-20","source":"Crossref","is-referenced-by-count":0,"title":["Minimizing Sorting Networks at the Sub-Comparator Level"],"prefix":"10.29007","volume":"100","author":[{"given":"Lu\u00eds","family":"Cruz-Filipe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Schneider-Kamp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"11545","event":{"name":"Proceedings of 25th Conference on Logic for Programming, Artificial Intelligence and Reasoning"},"container-title":["EPiC Series in Computing"],"original-title":[],"deposited":{"date-parts":[[2024,5,27]],"date-time":"2024-05-27T22:10:19Z","timestamp":1716847819000},"score":1,"resource":{"primary":{"URL":"https:\/\/easychair.org\/publications\/paper\/v6QM6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":0,"URL":"https:\/\/doi.org\/10.29007\/lzks","relation":{},"ISSN":["2398-7340"],"issn-type":[{"type":"print","value":"2398-7340"}],"subject":[]}}