Abstract

The "perfect shuffle" (PS) is a well-known concept for global interconnection networks in parallel computers. It performs a certain permutation of N = 2^k elements. Fig. 1 shows two different graphical representations of the PS-operation. In Fig. 1a the actual pathways of the N elements in one PS-step are drawn. If the addresses (positions) of the elements are represented by binary numbers, ranging from 0 to N-1, it is apparent that the PS can be described as a cyclical rotation (to the left) of the address bits (Fig. 1b).

© 1985 Optical Society of America