We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The Half Cleaner Lemma: Constructing Efficient Interconnection Networks from Sorting Networks.
- Authors
Jain, Tripti; Schneider, Klaus
- 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.
- Subjects
MULTIPROCESSORS; CONCENTRATORS (Telecommunications equipment); COMPUTER networks; ALGORITHMS; PARALLEL processing
- Publication
Parallel Processing Letters, 2018, Vol 28, Issue 1, p-1
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626418500019