Layouts for the Shuffle-Exchange Graph Based on the Complex Plane Diagram
Frank Thomson Leighton, Margaret A. Lepley, Gary Lee Miller · SIAM Journal on Algebraic and Discrete Methods · 1984
The shuffle-exchange graph is one of the best structures known for parallel computation. Among the things, a shuffle-exchange computer can be used to compute discrete Fourier transforms, multiply matrices, evaluate polynomials, perform permutations and sort lists. The algorithms needed for these operations are quite simple and many require no more than logarithmic time and space per processor. In this paper, we analyze the algebraic structure of the shuffle-exchange graph in order to find area-efficient embeddings of the graph in a two-dimensional grid. The results are applicable to the design of Very Large Scale Integration (VLSI) circuit layouts for a shuffle-exchange computer.