Share Email Print

Proceedings Paper

Computing Fast Fourier Transforms On Boolean Cubes And Related Networks
Author(s): S.Lennart Johnsson; Ching-Tien Ho; Michel Jacquemin; Alan Ruttenberg
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

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.

Paper Details

Date Published: 21 January 1988
PDF: 9 pages
Proc. SPIE 0826, Advanced Algorithms and Architectures for Signal Processing II, (21 January 1988); doi: 10.1117/12.942036
Show Author Affiliations
S.Lennart Johnsson, Thinking Machines Corp. (United States)
Ching-Tien Ho, Thinking Machines Corp. (United States)
Michel Jacquemin, Thinking Machines Corp. (United States)
Alan Ruttenberg, Thinking Machines Corp. (United States)

Published in SPIE Proceedings Vol. 0826:
Advanced Algorithms and Architectures for Signal Processing II
Franklin T. Luk, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?