Using the LCP based Decomposition for Permutation Routing on (2 log N -1) Stage Interconnection Networks

In this paper we describe a routing algorithm that routes any permutation on a (2 log N − 1) stage interconnection network in O(N log N) time. The proposed algorithm works on any multistage interconnection network, MIN, belonging to the equivalence class represented by the concatenation of a Reverse Butterfly and a Butterfly whose first and second stages are swapped. Both the routing algorithm and the definition of equivalence classes are based on the decomposition in factors of MINs obtained using the Layered Cross Product. The interest of this result is its approach, that is based on the use of only one factor of the studied MIN. Moreover, the algorithm provides a proof that all (2 log N − 1) stage MINs obtained concatenating two log N stage Butterfly equivalent MINs, with N = 8 inputs are rearrangeable.