Computing Fast Fourier Transforms On Boolean Cubes And Related Networks

S.Lennart Johnsson; Ching-Tien Ho; Michel Jacquemin; Alan Ruttenberg

doi:10.1117/12.942036

21 January 1988 Computing Fast Fourier Transforms On Boolean Cubes And Related Networks

S.Lennart Johnsson, Ching-Tien Ho, Michel Jacquemin, Alan Ruttenberg

Proceedings Volume 0826, Advanced Algorithms and Architectures for Signal Processing II; (1988) https://doi.org/10.1117/12.942036
Event: 31st Annual Technical Symposium on Optical and Optoelectronic Applied Sciences and Engineering, 1987, San Diego, CA, United States

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.

Citation Download Citation

S.Lennart Johnsson, Ching-Tien Ho, Michel Jacquemin, and Alan Ruttenberg "Computing Fast Fourier Transforms On Boolean Cubes And Related Networks", Proc. SPIE 0826, Advanced Algorithms and Architectures for Signal Processing II, (21 January 1988); https://doi.org/10.1117/12.942036

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available