Deriving concentrators from binary sorters using half cleaners

Many non-blocking and self-routing interconnection networks are based on the radix sorting paradigm which requires the design of concentrator modules to distribute the given inputs to subnetworks for the recursive calls. To that end, binary sorters are often used that sort the inputs in each recursive call by one bit of their destination addresses starting with the most significant bit down to the least significant one. It is well-known that the use of more general concentrators instead of binary sorters may lead to more efficient circuits. However, the design of concentrators turned out to be a challenging task for many decades. In this paper, we construct from any binary sorter a corresponding concentrator by means of Batcher's half cleaner circuit. This way, we can improve many interconnection networks that are based on binary radix sorting in that we replace their binary sorters by the corresponding concentrators obtained by our optimization. We have implemented various binary sorters and their corresponding concentrators and demonstrate by experimental results the improvements we achieved this way.