Compact Layouts of Banyan/FFT Networks

A two-layer pattern is presented for the crossover pattern that appears as the FFT signal flow graph and in many switching networks like the banyan, delta, or omega nets. It is characterized by constant path length and a regular pattern, providing uniform propagation delay and capacitance, and ameliorating design problems for VLSI implementation. These are important issues since path length grows linearly with the number of inputs to such networks, even though switching delay seems to grow only logarithmically.Independent of that pattern, an arrangement for stacking planes of such planar crossover patterns in three dimensions is described. Whereas a planar crossover pattern of 0(m) inputs and outputs has at best 0(m) path length, the stacked pattern allows 0($$ \sqrt {m} $$) path length. The scheme provides for stacking 2k planar nets (perhaps VLSI chips), each with k inputs/outputs into a network of k2 inputs/outputs. Using this pattern, all such paths would have length (propagation delays) = 0(k).