The Half Cleaner Lemma: Constructing Efficient Interconnection Networks from Sorting Networks
Abstract
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’s 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.
References
- 1. , Survey of network on chip (NoC) architectures and contributions, Journal of Engineering, Computing and Architecture 3(1), 2009. Google Scholar
- 2. ,
An sorting network , in Symposium on Theory of Computing (STOC), ACM, 1983, pages 1–9. Google Scholar - 3. , Sorting networks and their applications, in AFIPS Spring Joint Computer Conference, Vol. 32, pages 307–314, 1968. Google Scholar
- 4. , A survey of research and practices of network-on-chip, ACM Computing Surveys (CSUR ), 38(1) :1–51, March 2006. Crossref, ISI, Google Scholar
- 5. D. Bundala, M. Codish, L. Cruz-Filipe, P. Schneider-Kamp and J. Závodný, Optimal-depth sorting networks, arXiv Report arXiv:1412.5302, Cornell University Library, 2014. Google Scholar
- 6. , Optimal-depth sorting networks, Journal of Computer and System Sciences 84 :185–204, 2017. Crossref, ISI, Google Scholar
- 7. ,
Optimal sorting networks , in A.-H. DediuC. Martin-VideJ.-L. Sierra-RodríguezB. Truthe (editors), Language and Automata Theory and Applications (LATA ), Volume 8370 of LNCS (Springer, Madrid, Spain, 2014), pages 236–247. Crossref, Google Scholar - 8. D. Bundala and J. Závodný, Optimal sorting networks, arXiv Report arXiv:1310.6271, Cornell University Library, 2013. Google Scholar
- 9. , A new self-routing permutation network, IEEE Transactions on Computers, 45(5) :630–636, May 1996. Crossref, ISI, Google Scholar
- 10. , High performance concentrators and superconcentrators using multiplexing schemes, IEEE Transactions on Communications, 42(11) :3045–3050, November 1994. Crossref, ISI, Google Scholar
- 11. , On concentrators, superconcentrators, generalizers, and nonblocking networks, The Bell Systems Technical Journal, 58(8) :1765–1777, October 1978. Crossref, Google Scholar
- 12. M. Codish, L. Cruz-Filipe, T. Ehlers, M. Müller and P. Schneider-Kamp, Sorting networks: to the end and back again, arXiv Report arXiv:1507.01428v1, Cornell University Library, July 2015. Google Scholar
- 13. M. Codish, L. Cruz-Filipe, M. Frank and P. Schneider-Kamp, Twenty-five comparators is optimal when sorting nine inputs (and twenty-nine for ten), arXiv.org Report arXiv:1405.5754v3, Cornell University Library, 2014. Google Scholar
- 14. , Principles and Practices of Interconnection Networks, Morgan Kaufmann, 2004. Google Scholar
- 15. T. Ehlers and M. Müller, Faster sorting networks for 17, 19 and 20 inputs, arXiv Report arXiv:1410.2736, Cornell University Library, October 2014. Google Scholar
- 16. T. Ehlers and M. Müller, New bounds on optimal sorting networks, arXiv Report arXiv:1501.06946v1, Cornell University Library, January 2015. Google Scholar
- 17. , A survey of interconnection networks, IEEE Computer, 14(12) :12–27, December 1981. Crossref, ISI, Google Scholar
- 18. , Starlite: A wideband digital switch, in Global Telecommunications Conference (GLOBECOM ), pages 121–125, 1984. Google Scholar
- 19. ,
Verifying the concentration property of permutation networks by BDDs , in E. LeonardK. Schneider (editors), Formal Methods and Models for Codesign (MEMOCODE ) (IEEE Computer Society, Kanpur, India, 2016), pages 43–53. Crossref, Google Scholar - 20. , Deriving concentrators from binary sorters using half cleaners, in Reconfigurable Computing and FPGAs (ReConFig ),
Cancun, Mexico ,2017 , IEEE Computer Society. Google Scholar - 21. , An efficient self-routing and non-blocking interconnection network on chip, in Network on Chip Architectures (NoCArc ),
Boston, MA, USA ,2017 , pages 4:1–4:6, ACM. Google Scholar - 22. , A self-routing permutation network, Journal of Parallel and Distributed Computing, 10(2) :140–151, 1990. Crossref, ISI, Google Scholar
- 23. , Access and alignment of data in an array processor, IEEE Transactions on Computers (T-C), 24 :1145–1155, 1975. Crossref, ISI, Google Scholar
- 24. , A fast parallel algorithm for routing unicast assignments in Beneš networks, IEEE Transactions on Parallel and Distributed Systems, 6(3) :329–334, March 1995. Crossref, ISI, Google Scholar
- 25. , The Batcher-Banyan self-routing network: universality and simplification, IEEE Transactions on Communications, 36(10) :1175–1178, October 1988. Crossref, ISI, Google Scholar
- 26. , A recursive concentrator structure with applications to self-routing switching networks, IEEE Transactions on Communications, 42(2–4) :896–898, February/March/April 1994. Crossref, ISI, Google Scholar
- 27. , Parallel algorithms to set up the Beneš permutation network, IEEE Transactions on Computers (T-C), 31(2) :148–154, February 1982. Crossref, ISI, Google Scholar
- 28. , The pairwise sorting network, Parallel Processing Letters, 2(2–3) :205–211, 1992. Link, Google Scholar
- 29. , On the complexity of a concentrator, in International Teletraffic Conference (ITC ),
Stockholm, Sweden ,1973 , pages 318:1–318:4. Google Scholar - 30. , Study of multistage SIMD interconnection networks, in International Symposium on Computer Architecture (ISCA ), ACM, 1978, pages 223–229. Google Scholar
- 31. , Parallel processing with the perfect shuffle, IEEE Transactions on Computers (T-C), 20 :153–161, 1971. Crossref, ISI, Google Scholar
- 32. , On a class of multistage interconnection networks, IEEE Transactions on Computers (T-C), 29(8) :694–702, August 1980. ISI, Google Scholar


