Computing Fast Fourier Transforms On Boolean Cubes And Related Networks

High performance architectures are using an ever increasing number of processors. The Boolean cube network has many independent paths between any pair of processors. It provides both a high communications bandwidth as well as the ability to emulate many other networks without contention for communication channels. Of particular interest for the Fast Fourier Transform (FFT) is the ability to emulate butterfly networks, which defines the communication pattern of the FFT. Each node of a Boolean cube network of N nodes has a degree of log2N . For a large number of nodes the number of channels required at the chip boundary may be unfeasibly large with several nodes to a chip, and a network with slightly lower connectivity, such as Cube Connected Cycles networks, may be preferable. The communication system is the most critical resource in many high performance architectures, and its effective use imperative. We describe FFT algorithms that use both the storage bandwidth and the communication sys-tem optimally for an architecture such as the Connection Machine that has 65536 processors interconnected in a Boolean cube related network. We also describe the necessary data allocation, and the allocation and use of the twiddle factors.