On evil twin networks and the value of limited randomized routing

A dynamic two-stage Delta network (N inputs and outputs) is introduced and analyzed for permutation routing. The notion of evil twins is introduced and a deterministic procedure is given to route any permutation in no more than 2⁴√N network cycles. Two limited randomized routing schemes are then analyzed. The first called Single Randomization yields on average at most N!+1 (N!=O(logN/loglogN)¹ and is the greatest integer such that (N!)!≤N) network cycles and the second called Multiple Randomization yields on average at most upper bound [log(logN+1)]+2+1/N network cycles for any input permutation. The probability of any permutation requiring at least c network cycles more than the above average bounds is then shown to be at most 1/(c+1) for Single Randomization and 1/N^r for Multiple Randomization, respectively. It is then shown how the dynamic two-stage network can be physically realized as a three-stage network. Both the evil twin and Multiple Randomization algorithms have been integrated into an off-the-shelf ASIC from PMC-Sierra, Inc. (PM-73488) which has been designed as a building block for such a three-stage implementation. These routing schemes are also adapted to run on a recirculating network. Recirculation is used to effect a reshuffling of data as in the dynamic network, but with a considerable reduction in network cost.