Routing Partial Permutations in Interconnection Networks based on Radix Sorting
Tripti Jain, Klaus Schneider · 2018
In general, sorting networks can be used as interconnection networks in that inputs are sorted according to their target addresses. However, if not all inputs need a connection to one of the outputs, partial permutations have to be implemented which cannot be directly done with sorting networks. For radix-based sorting networks, only one solution is known by Narasimha's permutation network that has unfortunately an inefficient configuration logic. In this paper, we prove that the same idea also works for more efficient ways to configure the same permutation network. We also present general alternatives for routing partial permutations in radix-based networks.