{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T21:39:19Z","timestamp":1648762759399},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:p> In general, efficient non-blocking interconnection networks can be derived from sorting networks, and to this end, one may either follow the merge-based or the radix-based sorting paradigm. Both paradigms require special modifications to handle partial permutations. In this article, we present a general lemma about half cleaner modules that were introduced as building blocks in Batcher\u2019s bitonic sorting network. This lemma is the key to prove the correctness of many known optimizations of interconnection networks. In particular, we first show how to use any ternary sorter and a half cleaner for implementing an efficient split module as required for radix-based sorting networks for partial permutations. Second, our lemma formally proves the correctness of another known optimization of the Batcher-Banyan network. <\/jats:p>","DOI":"10.1142\/s0129626418500019","type":"journal-article","created":{"date-parts":[[2018,4,2]],"date-time":"2018-04-02T01:56:24Z","timestamp":1522634184000},"page":"1850001","source":"Crossref","is-referenced-by-count":2,"title":["The Half Cleaner Lemma: Constructing Efficient Interconnection Networks from Sorting Networks"],"prefix":"10.1142","volume":"28","author":[{"given":"Tripti","family":"Jain","sequence":"first","affiliation":[{"name":"Department of Computer Science, TU Kaiserslautern, Germany"}]},{"given":"Klaus","family":"Schneider","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Kaiserslautern, Germany"}]}],"member":"219","published-online":{"date-parts":[[2018,4]]},"reference":[{"issue":"1","key":"S0129626418500019BIB001","volume":"3","author":"Agarwal A.","year":"2009","journal-title":"Journal of Engineering, Computing and Architecture"},{"key":"S0129626418500019BIB002","first-page":"1","volume-title":"Symposium on Theory of Computing (STOC)","author":"Ajtai M.","year":"1983"},{"key":"S0129626418500019BIB004","doi-asserted-by":"publisher","DOI":"10.1145\/1132952.1132953"},{"key":"S0129626418500019BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.09.004"},{"key":"S0129626418500019BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04921-2_19"},{"key":"S0129626418500019BIB009","doi-asserted-by":"publisher","DOI":"10.1109\/12.509917"},{"key":"S0129626418500019BIB010","doi-asserted-by":"publisher","DOI":"10.1109\/26.328986"},{"key":"S0129626418500019BIB011","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1979.tb02972.x"},{"key":"S0129626418500019BIB014","volume-title":"Principles and Practices of Interconnection Networks","author":"Dally W.","year":"2004"},{"key":"S0129626418500019BIB017","doi-asserted-by":"publisher","DOI":"10.1109\/C-M.1981.220290"},{"key":"S0129626418500019BIB019","doi-asserted-by":"publisher","DOI":"10.1109\/MEMCOD.2016.7797744"},{"key":"S0129626418500019BIB022","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90023-I"},{"key":"S0129626418500019BIB023","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1975.224157"},{"key":"S0129626418500019BIB024","doi-asserted-by":"publisher","DOI":"10.1109\/71.372780"},{"key":"S0129626418500019BIB025","doi-asserted-by":"publisher","DOI":"10.1109\/26.7538"},{"key":"S0129626418500019BIB026","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.1994.580197"},{"key":"S0129626418500019BIB027","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675960"},{"key":"S0129626418500019BIB028","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626492000337"},{"key":"S0129626418500019BIB031","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223205"},{"issue":"8","key":"S0129626418500019BIB032","first-page":"694","volume":"29","author":"Wu C.","year":"1980","journal-title":"IEEE Transactions on Computers (T-C)"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626418500019","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:02:03Z","timestamp":1565182923000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626418500019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3]]},"references-count":20,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2018,4]]},"published-print":{"date-parts":[[2018,3]]}},"alternative-id":["10.1142\/S0129626418500019"],"URL":"https:\/\/doi.org\/10.1142\/s0129626418500019","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3]]}}}