Optimal book embeddings of the FFT, benes, and barrel shifter networks

Abstract

This paper gives 3-page book embeddings of three important interconnection networks: the FFT network, the Benes rearrangeable permutation network, and the barrel shifter network. Since all three networks are eventually nonplanar, they require three pages and the present embeddings are optimal. Also, the embeddings have pages of comparable widths.

The embeddings of the FFT and barrel shifter networks are obtained by decomposing these recursively defined networks into smaller copies of themselves and using induction. The embedding of the Benes network uses a novel decomposition of the network into eight copies of a smaller FFT network.