World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

The Half Cleaner Lemma: Constructing Efficient Interconnection Networks from Sorting Networks

    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. A.  Agarwal, C.  Iskander and R.  Shankar, Survey of network on chip (NoC) architectures and contributions, Journal of Engineering, Computing and Architecture 3(1), 2009. Google Scholar
    • 2. M.  Ajtai, J.  Komlos and E.  Szemeredi, An O(nlog(n)) sorting network, in Symposium on Theory of Computing (STOC), ACM, 1983, pages 1–9. Google Scholar
    • 3. K.  Batcher, Sorting networks and their applications, in AFIPS Spring Joint Computer Conference, Vol. 32, pages 307–314, 1968. Google Scholar
    • 4. T.  Bjerregaard and S.  Mahadevan, A survey of research and practices of network-on-chip, ACM Computing Surveys (CSUR ), 38(1) :1–51, March 2006. Crossref, ISIGoogle 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. D.  Bundala, M.  Codish, L.  Cruz-Filipe, P.  Schneider-Kamp and J.  Závodný, Optimal-depth sorting networks, Journal of Computer and System Sciences 84 :185–204, 2017. Crossref, ISIGoogle Scholar
    • 7. D.  Bundala and J.  Zavodny, 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. CrossrefGoogle Scholar
    • 8. D. Bundala and J. Závodný, Optimal sorting networks, arXiv Report arXiv:1310.6271, Cornell University Library, 2013. Google Scholar
    • 9. W.-J. Cheng and W.-T. Chen, A new self-routing permutation network, IEEE Transactions on Computers, 45(5) :630–636, May 1996. Crossref, ISIGoogle Scholar
    • 10. M.  Chien and A.  Oruç, High performance concentrators and superconcentrators using multiplexing schemes, IEEE Transactions on Communications, 42(11) :3045–3050, November 1994. Crossref, ISIGoogle Scholar
    • 11. F.  Chung, On concentrators, superconcentrators, generalizers, and nonblocking networks, The Bell Systems Technical Journal, 58(8) :1765–1777, October 1978. CrossrefGoogle 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. W.  Dally and B.  Towles, 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. T.  Feng, A survey of interconnection networks, IEEE Computer, 14(12) :12–27, December 1981. Crossref, ISIGoogle Scholar
    • 18. A.  Huang and S.  Knauer, Starlite: A wideband digital switch, in Global Telecommunications Conference (GLOBECOM ), pages 121–125, 1984. Google Scholar
    • 19. T.  Jain and K.  Schneider, 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. CrossrefGoogle Scholar
    • 20. T.  Jain, K.  Schneider and A.  Jain, Deriving concentrators from binary sorters using half cleaners, in Reconfigurable Computing and FPGAs (ReConFig ), Cancun, Mexico, 2017, IEEE Computer Society. Google Scholar
    • 21. T.  Jain, K.  Schneider and A.  Jain, 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. D.  Koppelman and A.  Oruç, A self-routing permutation network, Journal of Parallel and Distributed Computing, 10(2) :140–151, 1990. Crossref, ISIGoogle Scholar
    • 23. D.  Lawrie, Access and alignment of data in an array processor, IEEE Transactions on Computers (T-C), 24 :1145–1155, 1975. Crossref, ISIGoogle Scholar
    • 24. C.-Y. Lee and A.  Oruç, 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, ISIGoogle Scholar
    • 25. M.  Narasimha, The Batcher-Banyan self-routing network: universality and simplification, IEEE Transactions on Communications, 36(10) :1175–1178, October 1988. Crossref, ISIGoogle Scholar
    • 26. M.  Narasimha, 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, ISIGoogle Scholar
    • 27. D.  Nassimi and S.  Sahni, Parallel algorithms to set up the Beneš permutation network, IEEE Transactions on Computers (T-C), 31(2) :148–154, February 1982. Crossref, ISIGoogle Scholar
    • 28. I.  Parberry, The pairwise sorting network, Parallel Processing Letters, 2(2–3) :205–211, 1992. LinkGoogle Scholar
    • 29. M.  Pinsker, On the complexity of a concentrator, in International Teletraffic Conference (ITC ), Stockholm, Sweden, 1973, pages 318:1–318:4. Google Scholar
    • 30. H.  Siegel and S.  Smith, Study of multistage SIMD interconnection networks, in International Symposium on Computer Architecture (ISCA ), ACM, 1978, pages 223–229. Google Scholar
    • 31. H.  Stone, Parallel processing with the perfect shuffle, IEEE Transactions on Computers (T-C), 20 :153–161, 1971. Crossref, ISIGoogle Scholar
    • 32. C.  Wu and T.  Feng, On a class of multistage interconnection networks, IEEE Transactions on Computers (T-C), 29(8) :694–702, August 1980. ISIGoogle Scholar