Permuting data with the Omega network (Q2265809)

Introduced by D. H. Lawrie, the Omega network is a powerful device to connect processing elements in a SIMD computer or in a multiprocessor architecture. Unfortunately it is not rearrangeable and some permutations that are frequently used to align data in a SIMD computer cannot be performed in one pass. Such is the case with the class of permutations induced by a permutation of index digits (PIPID) which includes the perfect shuffle, the bit reversal, etc.... Using the techniques of linear algebra over the two-element field, we show that PIPIDs can be achieved by the Omega network through which the vector of data is routed twice.