Abstract

The perfect shuffle (PS) [1] is one of the most studied interconnection patterns for multiprocessor architectures. PS links are coupled to arrays of local 2×2 exchange/bypass switches to form shuffle/exchange networks. These networks perform arbitrary permutations of the elements in multistage interconnection networks for applications such as routing and sorting [2,3]. The PS of a 1-D array results by interleaving the elements of the first half of the array with those of the second half, with the first and last elements remaining unchanged in their position. For example, the PS of the 8 element array, {1,2,3,4,5,6,7,8}, is {1,5,2,6,3,7,4,8}. For a processing element (PE) array of size N, a single stage of a shuffle-exchange network contains a PS of size N followed by N/2 exchange/bypass units. Recently the sufficient number of stages required for an arbitrary permutation was proved to be no greater than 31og(N)-3 [4]. Therefore, the total number of active switches required in such permutation networks grows as Nlog(N). Thus, multistage permutation networks are appropriate for applications in which the number of elements is large enough to preclude the use of a crossbar switch, whose complexity would grow as N².

© 1991 Optical Society of America