Optimizing the Fast Fourier Transform on a many-core architecture.

The rapid revolution in microprocessor chip architecture due to multi-core and many-core technology is presenting an unprecedented challenge to the application developers as well as system software designers: how to exploit the performance potential due to such architectures effectively and efficiently?;In this thesis, an in-depth study on optimizing the Fast Fourier Transform (FFT) on a many-core architecture is presented. The IBM Cyclops-64 (C64) chip architecture, the case study in this thesis, is a many-core chip architecture consisting of 160 thread units, associated memory banks and an interconnection network that connects them together in a shared memory organization.;The study presented in this thesis demonstrates how many-core architectures, like the C64, could be used to achieve a scalable high-performance implementation of FFT both in 1D and 2D cases. The thesis also analyzes the optimization challenges and opportunities, including problem decomposition, load balancing, work distribution, and data-reuse, together with the exploiting of the C64 architecture features such as the massive parallelism, explicit multi-level memory hierarchy and large register files.;The main contributions of this thesis include: (1) the development of scalable high-performance parallel FFT implementation on C64; (2) the study demonstrates that successful optimization for C64-like many-core architectures requires a careful analysis that can identify certain domain-specific features of a target application (e.g. FFT) and match them well with some key many-core architecture features; (3) the optimization procedure, assisted with the hand-tuned process, provides quantitative evidence on the importance of each optimization identified in (2) and valuable experience toward establishing an effective programming methodology for C64-like many-core architectures.