Routing Partial Permutations in General Interconnection Networks based on Radix Sorting

Abstract

In general, sorting networks can be used as interconnection networks in that the inputs are simply sorted according to their target addresses. If the target addresses form a permutation of the addresses, this is obviously correct since the sorting algorithm routes each message to the output with the desired target address. However, if not all inputs need a connection to one of the outputs, partial permutations are obtained since then some input addresses are not mapped to any output address at all. In this case, sorting networks work no longer correctly as interconnection networks since the addresses larger than the missing addresses will be routed to the wrong outputs. For merge-based sorting networks, there is a well-known general solution called the Batcher-Banyan network. However, for the bigger class of radix-based sorting networks, there is only one solution known for a particular permutation network. In this paper, we present a general construction to transform any radix-based sorting network into one that can cope with partial permutations. While our solution roughly doubles the number of gates, it still maintains the depth of the circuit.